https://codeforces.com/contest/1509/problem/D
1秒、256 MBメモリ
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.
各テストケースに入力された2つの文字列の最大長3nを含む文字列を出力します.

条件:
最大長さは3 nです.
もちろん、2つの文字列を接続すると、4 nの長さにすることができますが、さらに小さくする必要があります.
問題の例では、入力された2つの文字列を重ねたり、分けたりすることができます.
文字列は、最も長い共通部分数列(LCS)を検索するのと同じ条件で作成できます.

共通

3つの文字列は「0」と「1」で構成されているため、各位置には少なくとも2つの文字列が同じ文字を有している.
したがって、同じ文字を持つ場合は、正解文字列に追加できます.
このまま同じ文字を入れ続けると、ポインタが文字列の末尾に達します.
これにより、答え文字列の長さがkの場合(2 nではないかもしれませんが、真ん中の2つの文字列が同じなので文字を追加できます).
3つのポインタがすべて移動できる回数は6 nと見なすことができる.でも今は2 nに移動した時の長さはkです3つのポインタの移動を合わせると、2 k移動したと言えるでしょう.
最後のポインタが2 n回移動したので、残りの2つのポインタの合計は2 k−2 nと見なすことができ、したがって、少なくとも2つのポインタのうちの1つはk−n以上であるべきである.
このとき、残りのメールはもっと小さい人を後ろに貼ります.
目上の人であれば、問題の中で3 nの要求を満たすことができないかもしれません.

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))