Educational Codeforces Round 82 - E Erase Subsequences

解説ACした

絶対思いつかない天才解法だったのでメモ

ngtkana.hatenablog.com

これ通りに書いただけ。丁寧な説明なのに結構実装にも手間取った。 以下は実装。O(N³)の計算量。6.4*10⁷でpypyでは厳しいのでは？と思ったが余裕で通った。 こういうの本番では不安で出したくない。

T = int(input())
for ti in range(T):
    s, t = input().strip(), input().strip()
    N = len(t)
    for i in range(1, N+1):
        # t1 : [0,i), t2 : [i,N)に分割
        dp = [0]+[-1]*i
        for l, c in enumerate(s):
            for j in range(i, -1, -1):
                # dp[j] : cまで見てt1[:j]、t2[:k]を作るとしてkの最大値
                tmp = dp[j]
                # cをt2に使う
                if dp[j] != -1 and i+dp[j] < N and t[i+dp[j]] == c:
                    tmp = dp[j]+1
                # cをt1に使う
                if j != 0 and t[j-1] == c:
                    tmp = max(tmp, dp[j-1])
                dp[j] = tmp
        if dp[i] == N-i:
            print("YES")
            break
    else:
        print("NO")