概要

\(N\) 枚のカードから「同じ色かつ同じ整数」の隣り合うペアを消去していく操作を繰り返し、最終的に残ったカードの文字が \(T\) と一致するようにできるかを判定する問題です。

適切な考察により、書く整数の条件（\(M\) や \(Q\)）は無視でき、「カードの色 \(P\) のスタック操作による消去可能性」と「文字列 \(T\) とのマッチング」を動的計画法（DP）で判定する問題に帰着できます。

---

考察

1. 整数 \(M\) と目標整数列 \(Q\) は無視できる

一見すると、カードに書き込む整数や \(Q\) との一致を考慮する必要があるように見えます。しかし、以下のように考えることができます。

• 残したいカードには、目標の整数列 \(Q_1, Q_2, \ldots, Q_L\) をあらかじめ書き込んでおけばよいです。
• 消去したいカードのペアには、残すカードに影響を与えないように適切に整数を割り当てることができます（例えば、内側から消去するペアごとに同じ整数を割り当てる）。

したがって、「色の消去ルールに従って消去できるか」だけを考えればよく、書き込む整数 \(M\) や数列 \(Q\) の制約は常に満たすことができます。

2. 色の消去可能性とスタック

2枚のカードを消去する操作は、「色のカッコ列のマッチング」とみなすことができます。 カードの色を左から順にスタックに入れていき、「スタックの最上位と同じ色が入ってきたら取り除く（pop）」という操作を考えます。

このとき、区間 \([a, b]\) のカード列をすべて消去できるための必要十分条件は、「位置 \(a\) の直前のスタック状態」と「位置 \(b\) の直後のスタック状態」が完全に一致することです。

具体例として、\(P = \text{`ABBAC`}\) の各プレフィックス処理後のスタック状態を見てみましょう： - 初期状態 (\(0\) 枚処理): () - \(1\) 枚目 (A): ('A',) - \(2\) 枚目 (B): ('A', 'B') - \(3\) 枚目 (B): ('A',) （B が重なったので pop） - \(4\) 枚目 (A): () （A が重なったので pop） - \(5\) 枚目 (C): ('C',)

インデックス \(0\) の直前（初期状態）とインデックス \(4\) の直後がともに () で一致しているため、区間 \([0, 3]\)（ABBA）は完全に消去可能であることが分かります。

3. 目標文字列 \(T\) とのマッチング

目標文字列 \(T\) の \(j\) 番目の文字 \(T_j\) を、元のカードの \(S[i_j]\) に対応させるとします。 カードを残した結果 \(T\) と一致させるためには、以下の条件を満たす必要があります：

1. 各 \(j\) について、\(S[i_j] == T_j\) である。
2. 残すカードとカードの間の区間（\([0, i_1-1]\), \([i_1+1, i_2-1]\), \(\dots\), \([i_L+1, N-1]\)）がすべて消去可能である。

条件 2 はスタック状態を用いれば、「\(S[i_{j-1}]\) の直後のスタック状態」と「\(S[i_j]\) の直前のスタック状態」が一致していることと言い換えられます。

---

アルゴリズム

DP（動的計画法）を用いて、\(T\) の何文字目までマッチできたかを順に更新していきます。

Step 1: スタック状態の事前計算

各位置 \(k\) (\(0 \le k \le N\)) におけるプレフィックス \(P[0 \dots k-1]\) を処理した後のスタック状態（色のタプル）を求め、各状態に固有の ID (stack_ids[k]) を割り当てます。

Step 2: DP によるマッチング判定

• dp[i] : \(T\) の現在の文字までをマッチさせ、その最後の文字を \(S[i]\) に割り当てることが可能かを表すフラグ（True / False）。

1. 初期化 (\(T[0]\) のマッチング):

   • \(S[i] == T[0]\) かつ stack_ids[i] == stack_ids[0]（空スタックのID）を満たす位置 \(i\) について dp[i] = True とします。

2. 遷移 (\(T[j]\) のマッチング (\(1 \le j < L\))):

   • \(i\) を \(0\) から \(N-1\) まで走査しながら、直前のステップで有効だった DP 位置の直後のスタック状態（stack_ids[i]）を記録しておきます (seen_stack)。
   • \(S[i] == T[j]\) であり、かつ seen_stack[stack_ids[i]] が True であれば、新たな dp[i] = True と更新します。

3. 最終判定:

   • \(T[L-1]\) までマッチさせた後、dp[i] == True かつ stack_ids[i+1] == stack_ids[N]（末尾の区間も消去可能）を満たす \(i\) が存在すれば Yes、存在しなければ No と出力します。

---

計算量

• 時間計算量: \(O(N \cdot L + N^2)\)

  • 各プレフィックスのスタック状態の計算に \(O(N^2)\)（色の種類数が 3 のためスタックの長さは高々 \(N\)）。
  • DPの更新は \(L\) 回行われ、各回で \(N\) 個の要素を走査するため \(O(N \cdot L)\)。
  • \(N, L \le 1000\) であるため、十分実行時間制限内に収まります。

• 空間計算量: \(O(N^2)\)

  • スタック状態（タプル）の保存に高々 \(O(N^2)\) のメモリを使用します。

---

実装のポイント

• DP遷移の高速化: seen_stack 配列を用意し、インデックス \(i\) を進めながら「\(i-1\) で dp が True だった直後のスタックID」を保持しておくことで、遷移のチェックを \(O(1)\) で行うことができます。これにより \(1\) ステップあたりの DP 更新を \(O(N)\) に抑えています。

• 入力の無視: 問題文で与えられる \(M\) や \(Q_1, \ldots, Q_L\) は判定ロジックには使用しませんが、入力としては正しく読み飛ばす必要があります。

  ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    L = int(input_data[2])

    S = input_data[3]
    P = input_data[4]
    T = input_data[5]

    # Compute stack state IDs for each prefix of P
    stack_ids = [0] * (N + 1)
    stack_map = {(): 0}
    cur_stack = []

    for k in range(N):
        if cur_stack and cur_stack[-1] == P[k]:
            cur_stack.pop()
        else:
            cur_stack.append(P[k])
        t = tuple(cur_stack)
        if t not in stack_map:
            stack_map[t] = len(stack_map)
        stack_ids[k + 1] = stack_map[t]

    num_stacks = len(stack_map)

    # DP to find if T can be matched
    # dp[i] is True if T[0...j-1] can be matched ending at S[i]
    dp = [False] * N
    T0 = T[0]
    target_stack_0 = stack_ids[0]
    for i in range(N):
        if S[i] == T0 and stack_ids[i] == target_stack_0:
            dp[i] = True

    if not any(dp):
        print("No")
        return

    for j in range(1, L):
        T_j = T[j]
        next_dp = [False] * N
        seen_stack = [False] * num_stacks

        for i in range(N):
            if i > 0 and dp[i - 1]:
                seen_stack[stack_ids[i]] = True

            if S[i] == T_j and seen_stack[stack_ids[i]]:
                next_dp[i] = True

        dp = next_dp
        if not any(dp):
            print("No")
            return

    # Final check: after matching T[L-1] at index i,
    # the suffix P[i+1...N-1] must be reducible to empty.
    target_stack_N = stack_ids[N]
    for i in range(N):
        if dp[i] and stack_ids[i + 1] == target_stack_N:
            print("Yes")
            return

    print("No")


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.6-flash-high によって生成されました。