https://codeforces.com/contest/1509/problem/D
시간 1초, 메모리 256MB

input :

• t (1 ≤ t ≤ 103)
• n (1 ≤ n ≤ 105)
• a bitstring of length 2n

output :

• For each test case, print a single line containing a bitstring of length at most 3n that has at least two of the given bitstrings as subsequences.
  각 테스트케이스에서 입력된 두 문자열을 포함하는 최대 길이 3n짜리의 문자열을 출력하시오.

조건 :

---

최대길이가 3n이다.
물론 두 문자열을 이어 붙인다면 4n의 길이로 만들 수 있지만 이를 더 줄여야 한다.

문제의 예시를 통해서 알 수 있는 조건으로 입력 받은 두 문자열을 겹칠 수 있고 떨어져 있어도 된다.
LCS(가장 긴 공통 부분 수열)를 찾는 것과 동일한 조건으로 문자열을 만들 수 있다.

공통

세개의 문자열이 '0'과 '1'로 이루어져 있기 때문에 각 위치에서 최소한 2개의 문자열은 동일한 문자를 가지고 있을 것이다.
그렇기 때문에 동일한 문자를 가지고 있는 경우 이를 정답 문자열에 추가를 해준다.

이렇게 동일한 문자들을 계속 넣다보면 어느 한 포인터는 문자열의 끝에 도달해 있을 것이다.
그렇게 되면 정답 문자열에 들어가 있는 길이를 k라고 할 때(2n이 아닐 수도 있다. 중간에 다른 두 문자열이 동일해서 문자를 추가할 수도 있기 때문)

포인터 3개가 전부 다 움직일 수 있는 횟수는 6n이라고 볼수 있다. 근데 지금 하나는 2n까지 이동을 했고 이 때 길이가 k이다. 3개의 포인터의 이동을 합했을 때 2k만큼 움직였다고 볼 수 있다.

현재 마지막에 위치한 포인터는 2n번 움직였으니까 나머지 두 포인터의 이동의 합이 2k - 2n이라고 볼 수 있고 그러므로 최소한 두 포인터들 중 하나는 k - n보다 같거나 클것이다.
그러면 이 때 둘 중 남아있는 문자가 더 작은 놈을 뒤에 붙여준다.

혹시나 긴 놈이라면 문제에서 원하는 3n을 충족시키지 못할 수도 있다.

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    data1 = sys.stdin.readline().rstrip()
    data2 = sys.stdin.readline().rstrip()
    data3 = sys.stdin.readline().rstrip()
    p1, p2, p3 = 0, 0, 0
    ans = []

    while p1 < 2 * n and p2 < 2 * n and p3 < 2 * n:
        if data1[p1] == data2[p2]:
            ans.append(data1[p1])
            p1 += 1
            p2 += 1
        elif data1[p1] == data3[p3]:
            ans.append(data1[p1])
            p1 += 1
            p3 += 1
        else:
            ans.append(data2[p2])
            p2 += 1
            p3 += 1

    if p1 == 2 * n:
        if p2 > p3:
            ans.append(data2[p2:])
        else:
            ans.append(data3[p3:])
    elif p2 == 2 * n:
        if p1 > p3:
            ans.append(data1[p1:])
        else:
            ans.append(data3[p3:])
    else:
        if p1 > p2:
            ans.append(data1[p1:])
        else:
            ans.append(data2[p2:])

    print("".join(ans))