概要

残すカードを文字列 \(T\) に対応する部分列として選び、その前後および間にあるカード列がすべて消去可能かを判定します。
色列の消去可能性をスタックで正規化し、動的計画法を用いて \(O(NL)\) で判定します。

考察

書き込む整数について

残すことにした \(k\) 枚目のカードには、指定どおり \(Q_k\) を書き込みます。一方、消去するカードにはすべて整数 \(1\) を書けば十分です。

すると、消去するカード同士では「整数が同じ」という条件が必ず満たされるため、消去可能かどうかは色だけで決まります。また、条件を満たす隣接カードがあっても消去は強制ではないため、残すカードが誤って消えることもありません。

したがって、\(M\) や \(Q\) は消去可能性の判定には影響しません。

色列が消去可能か

色列に対して、隣り合う同じ色を取り除く操作を考えます。これは次のスタック操作で正規化できます。

• スタックの先頭と現在の色が同じなら、先頭を取り除く
• そうでなければ、現在の色を追加する

例えば ABBA は

• A
• AB
• A（BB が消える）
• 空（AA が消える）

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

一方、ABAB は各色が偶数回登場しますが、同じ色が隣り合わないため消去できません。単に色ごとの枚数を見るだけでは不十分です。

色列 \(P\) の先頭から \(x\) 枚をスタックで正規化した状態を \(\mathrm{state}[x]\) とします。ここで \(\mathrm{state}[0]\) は空の状態です。

このとき、半開区間 \([l,r)\) のカードをすべて消去できることと

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

は同値です。

各色を読む操作は、同じ色がスタックの先頭なら取り除き、そうでなければ追加するという可逆な操作です。そのため、区間を読む前後で状態が同じなら、その区間は全体として空に正規化できます。

残すカードの選択

残すカードの位置を

\[ a_0<a_1<\cdots<a_{L-1} \]

とします。当然、各 \(k\) について

\[ S_{a_k}=T_k \]

が必要です。

さらに、残すカードをまたいでカードを消去することはできません。したがって、次の各区間がそれぞれ独立にすべて消える必要があります。

• 最初のカードより前
• 隣り合う残存カードの間
• 最後のカードより後

状態を使うと、条件は次のように表せます。

\[ \mathrm{state}[a_0]=\mathrm{state}[0] \]

\[ \mathrm{state}[a_{k-1}+1]=\mathrm{state}[a_k] \quad (1\leq k<L) \]

\[ \mathrm{state}[a_{L-1}+1]=\mathrm{state}[N] \]

素朴な方法の問題点

\(T\) に対応する部分列をすべて列挙すると、候補数は指数的になります。

また、DPで直前に残した位置をすべて試すと、各遷移に \(O(N)\) かかり、全体で \(O(LN^2)\) となります。\(N,L\leq 1000\) では最大 \(10^9\) 回程度になり、間に合いません。

そこで、直前の位置そのものではなく、必要な状態 \(\mathrm{state}[j+1]\) が到達済みかだけを管理します。これにより、各DP段階を \(O(N)\) で処理できます。

アルゴリズム

1. 各接頭辞の正規化状態を求める

正規化されたスタックを、永続的な木のノードとして表します。

各ノードは次を持ちます。

• parent: スタックの先頭を取り除いた後の状態
• topColor: スタック先頭の色
• child[color]: その色を追加した後の状態

色 \(c\) を読むときは、

• 現在の先頭色が \(c\) なら parent へ移動
• そうでなければ child[c] へ移動

します。child[c] がまだ存在しない場合だけ、新しいノードを作ります。

これにより、同じ正規化結果には必ず同じ状態番号が割り当てられます。
\(\mathrm{state}[x]\) を、先頭 \(x\) 枚を読んだ後の状態番号とします。

2. 残すカードをDPで選ぶ

\(k\) 文字目まで選んだ後について、

• dp[i] = true
  \(T_0,\ldots,T_k\) に対応するカードを選べて、最後に選んだ位置が \(i\)

と定義します。

初期化

最初に残すカードより前がすべて消える必要があるため、

\[ S_i=T_0 \quad\text{かつ}\quad \mathrm{state}[i]=\mathrm{state}[0] \]

を満たす位置 \(i\) を true にします。

遷移

直前に残した位置を \(j\)、新しく残す位置を \(i\) とすると、\(j<i\) であり、その間の区間 \([j+1,i)\) が消える必要があります。

したがって、

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

が必要です。

位置 \(i\) を左から順に走査し、到達可能な \(j<i\) についての \(\mathrm{state}[j+1]\) を reachableState に記録します。すると、

\[ S_i=T_k \quad\text{かつ}\quad \mathrm{reachableState}[\mathrm{state}[i]] \]

なら、位置 \(i\) を次の残存カードにできます。

これにより、各 \(k\) の遷移を \(O(N)\) で処理できます。

3. 最後のカードより後を確認する

最後に残した位置が \(i\) のとき、後ろの区間 \([i+1,N)\) が消える条件は

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

です。

この条件を満たす dp[i] が1つでもあれば Yes、なければ No です。

計算量

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

実装のポイント

• state[x] は先頭 \(x\) 枚、すなわち区間 \([0,x)\) を処理した状態です。カード位置との添字のずれに注意します。

• 永続スタックの状態を整数IDで管理するため、文字列やハッシュを比較する必要がなく、衝突もありません。

• DPの遷移では、位置 \(i\) を判定する前に dp[i-1] に対応する state[i] を reachableState に追加します。これにより、直前の位置が必ず \(i\) より小さくなります。

• \(M\) と \(Q\) を判定に使用していないのは意図的です。残すカードには \(Q\) を、消すカードにはすべて \(1\) を書けばよいためです。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, L;
    cin >> N >> M >> L;

    string S, P, T;
    cin >> S >> P >> T;

    vector<int> Q(L);
    for (int &q : Q) cin >> q;

    vector<int> parent(1, -1), topColor(1, -1);
    vector<array<int, 3>> child(1, array<int, 3>{-1, -1, -1});
    vector<int> state(N + 1, 0);

    int current = 0;
    for (int i = 0; i < N; ++i) {
        int color = P[i] - 'A';

        if (topColor[current] == color) {
            current = parent[current];
        } else {
            int next = child[current][color];
            if (next == -1) {
                next = static_cast<int>(parent.size());
                child[current][color] = next;
                parent.push_back(current);
                topColor.push_back(color);
                child.push_back(array<int, 3>{-1, -1, -1});
            }
            current = next;
        }
        state[i + 1] = current;
    }

    const int stateCount = parent.size();
    vector<char> dp(N, false), nextDp(N, false);

    for (int i = 0; i < N; ++i) {
        if (S[i] == T[0] && state[i] == state[0]) {
            dp[i] = true;
        }
    }

    for (int k = 1; k < L; ++k) {
        fill(nextDp.begin(), nextDp.end(), false);
        vector<char> reachableState(stateCount, false);

        for (int i = 0; i < N; ++i) {
            if (i > 0 && dp[i - 1]) {
                reachableState[state[i]] = true;
            }

            if (S[i] == T[k] && reachableState[state[i]]) {
                nextDp[i] = true;
            }
        }

        dp.swap(nextDp);
    }

    for (int i = 0; i < N; ++i) {
        if (dp[i] && state[i + 1] == state[N]) {
            cout << "Yes\n";
            return 0;
        }
    }

    cout << "No\n";
    return 0;
}

---

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