概要

最終的に残すカードを \(S\) の部分列として選び、その間にあるカード列がすべて消去可能かを判定します。
色列に対する「同じ色が隣接したら消す」という操作をスタックで正規化し、動的計画法を \(O(NL)\) で行います。

考察

書き込む整数について

残すカードには、左から順に \(Q_1,Q_2,\ldots,Q_L\) を書けばよいです。

一方、消すカードにはすべて整数 \(1\) を書くことができます。すると、消すカード同士では「整数が同じ」という条件を常に満たすため、消去可能性は色だけで決まります。

また、操作は好きなタイミングで終了できます。そのため、最後に残ったカード同士の色と整数が同じでも、追加で消す必要はありません。

したがって、この問題では \(M\) や \(Q\) の値は消去可能性に影響しません。

残すカードの間は独立に消す必要がある

最終的に残すカードの位置を

\[ i_0 < i_1 < \cdots < i_{L-1} \]

とします。このとき、次の区間はすべて完全に消去できなければなりません。

• \(i_0\) より前
• \(i_j\) と \(i_{j+1}\) の間
• \(i_{L-1}\) より後

残すカードをまたいで左右のカードが隣接することはないため、それぞれの区間は独立に考えられます。

色列が消去可能かの判定

色列を左から順にスタックへ入れ、次の処理をします。

• スタックの先頭と同じ色なら先頭を取り除く
• 異なる色なら新しく積む

例えば ABBA なら、

\[ [] \to [A] \to [A,B] \to [A] \to [] \]

となるため、すべて消去できます。

一方、ABAB は同じ色数を持ちますが、スタックは空になりません。したがって、色ごとの枚数だけでは判定できず、並び順まで考える必要があります。

このスタック処理後の列を、その色列の「状態」とします。色列 \(P\) の先頭 \(k\) 文字を処理した状態を \(\mathrm{state}[k]\) とすると、半開区間 \(P[l:r]\) がすべて消去可能であることと

\[ \mathrm{state}[l]=\mathrm{state}[r] \]

は同値です。

これは、同じ色を隣接して消す操作によって得られる正規形が一意であり、区間を追加する前後で状態が変わらないことが、その区間全体を消せることを表すためです。

DPの高速化

次の DP を考えます。

\[ dp[j][i] \]

を、「位置 \(i\) のカードを \(T_j\) に対応するカードとして残し、\(T_0,\ldots,T_j\) までを作れる」とします。

直前に残すカードの位置を \(k\) とすると、遷移条件は次の通りです。

• \(k<i\)
• \(dp[j-1][k]\) が真
• \(S_i=T_j\)
• \(k\) と \(i\) の間、すなわち \(P[k+1:i]\) が消去可能

最後の条件は

\[ \mathrm{state}[k+1]=\mathrm{state}[i] \]

と言い換えられます。

各 \(i\) に対してすべての \(k\) を調べると \(O(LN^2)\) となり、間に合いません。そこで左から走査し、これまでに現れた有効な \(\mathrm{state}[k+1]\) を seen に記録します。すると、各遷移を \(O(1)\) で判定でき、DP 全体が \(O(LN)\) になります。

アルゴリズム

1. 色 A, B, C をそれぞれ \(0,1,2\) に変換する。
2. \(P\) を左から走査し、各接頭辞のスタック状態 \(\mathrm{state}[k]\) を求める。
   • 先頭の色と現在の色が同じなら parent へ戻ってポップする。
   • 異なるなら新しい状態へ遷移する。
   • 同じスタック内容には同じ状態番号を割り当てる。
3. 最初に残すカードの候補を求める。
   • \(S_i=T_0\)
   • その前の区間が消せる、すなわち \(\mathrm{state}[i]=0\)
4. \(j=1,2,\ldots,L-1\) について DP を更新する。
   • 左から位置 \(i\) を走査する。
   • 位置 \(i-1\) が直前のカードとして有効なら、\(\mathrm{state}[i]\) を seen に登録する。
   • \(S_i=T_j\) かつ \(\mathrm{state}[i]\) が seen にあれば、位置 \(i\) を今回のカードとして使える。
5. 最後に残すカードの位置を \(i\) としたとき、後ろの区間が消せる条件

\[ \mathrm{state}[i+1]=\mathrm{state}[N] \]

を満たす候補が一つでもあれば Yes、なければ No とする。

計算量

• 時間計算量: \(O(NL)\)
• 空間計算量: \(O(N)\)

実装のポイント

• state[k] は、先頭から \(k\) 枚の色を処理した後の状態です。

• スタック全体を毎回コピーすると遅いため、各状態を「親状態」と「先頭の色」で表す永続的なスタックとして管理します。

• transition[(状態, 色)] を再利用することで、同じスタック内容には必ず同じ状態番号が割り当てられます。

• seen は DP の各段階で初期化する代わりに、段階番号 mark を記録するタイムスタンプ方式を使っています。

• \(L=1\) の場合は DP 遷移を行わず、先頭と末尾の区間が消去可能かだけを確認します。

  ソースコード

import sys

input = sys.stdin.readline

N, M, L = map(int, input().split())
S = input().strip()
P = input().strip()
T = input().strip()
Q = list(map(int, input().split()))

color_id = {'A': 0, 'B': 1, 'C': 2}

parent = [-1]
top = [-1]
transition = {}
state = [0] * (N + 1)
cur = 0

for i, ch in enumerate(P):
    c = color_id[ch]
    if top[cur] == c:
        cur = parent[cur]
    else:
        key = cur * 3 + c
        nxt = transition.get(key)
        if nxt is None:
            nxt = len(parent)
            transition[key] = nxt
            parent.append(cur)
            top.append(c)
        cur = nxt
    state[i + 1] = cur

prev = [False] * N
for i in range(N):
    if S[i] == T[0] and state[i] == 0:
        prev[i] = True

seen = [0] * len(parent)

for j in range(1, L):
    mark = j
    cur_dp = [False] * N
    target = T[j]

    for i in range(N):
        if i > 0 and prev[i - 1]:
            seen[state[i]] = mark
        if S[i] == target and seen[state[i]] == mark:
            cur_dp[i] = True

    prev = cur_dp

goal_state = state[N]
answer = any(prev[i] and state[i + 1] == goal_state for i in range(N))
print("Yes" if answer else "No")

---

この解説は gpt-5.6-sol-high によって生成されました。