概要

\(N\) 枚のカードから隣接する同色・同整数のペアを消していき、残りをちょうど文字列 \(T\)・整数列 \(Q\) に一致させられるか判定する問題です。実は「整数は自由に書ける」ため、判定は色の並びだけで決まる区間削除の可否に帰着します。

考察

整数（\(Q\), \(M\)）は答えに影響しない

まず重要な気づきです。消去操作では「消すペアの整数が等しい」ことが必要ですが、整数は高橋君が自由に書き込めます。

• 消えるカード同士は 1 対 1 のペアを作って消えます。各ペアに同じ整数（例えば \(1\)）を割り当てればよく、\(M \geq 1\) なので必ず割り当て可能です。
• 最後に残るカードには目標の \(Q_i\) をそのまま書き込めばよく、\(Q_i \leq M\) は制約で保証されています。残るカードは消去されないので整数に関する追加の制約はありません。

したがって、\(Q\) や \(M\) は判定に一切影響せず、「色の条件だけで区間を消しきれるか」と「文字の並びが \(T\) に一致するか」 だけを考えればよいのです。

区間を「消しきれる」条件

ある連続区間を全部消せるかどうかを考えます。カードを消すのは「隣接する同色ペア」なので、これは括弧のマッチングとよく似ています。

区間 \([a, b)\)（左端 \(a\) から右端 \(b-1\) まで）を完全に消せることを \(R[a][b]\) とします。区間の左端カード \(a\) に注目すると、\(a\) はいつか同色のカード \(k\) とペアになって消えます。そのためには、

• カード \(a\) とカード \(k\) の色が同じ、
• \(a\) と \(k\) の間 \([a+1, k)\) が先に消しきれる（\(R[a+1][k]\)）、
• \(k\) の右側 \([k+1, b)\) も消しきれる（\(R[k+1][b]\)）、

が必要十分です。よって次の区間 DP が立ちます（長さは必ず偶数）。

\[R[a][b] = \bigvee_{a<k<b,\ \text{col}[a]=\text{col}[k]} \big(R[a+1][k] \land R[k+1][b]\big)\]

\(R[a][a] = \text{true}\)（空区間）です。

文字列 \(T\) を残す条件

次に、消し残すカードを左から選んでいき、その文字列が \(T\) に一致するようにできるかを考えます。

\(j\) 番目の目標文字 \(T[j]\) まで一致させたとき、「直前に選んだカードの直後の位置」を状態として持ちます。位置 \(a\) から次に選ぶカード \(v\)（\(S[v] = T[j]\)）へ進めるのは、間の区間 \([a, v)\) を全部消しきれるとき、すなわち \(R[a][v]\) が真のときです。

• 最初は位置 \(0\) からスタート（先頭より前は空）。
• 各文字を選ぶたびに、到達可能な「次の開始位置 \(v+1\)」の集合を更新。
• 最後に、選び終えた位置 \(a\) から末尾 \(N\) まで \(R[a][N]\) が真であれば、残りも全部消せて完成です。

アルゴリズム

1. 区間削除 DP: 上記の \(R[a][b]\) を、区間長 \(2, 4, \dots\) の順に埋める。
2. 到達可能位置の DP: 「今どの位置に境界があり得るか」を集合 reach として管理する。\(T\) を先頭から 1 文字ずつ処理し、reach を更新していく。
   • reach の各ビット \(a\) は「開始位置 \(a\) から進める」ことを表す。
   • 文字が一致するカード \(v\) について、(reach & colR[v]) が空でなければ（\(R[a][v]\) が真になる \(a\) が存在すれば）、新しい位置 \(v+1\) を立てる。
   • ここで colR[v] は「\(R[a][v]\) が真になる \(a\) の集合」を表すビット列。
3. 最後に reach & colR[N] が空でなければ Yes。

集合演算を bitset で行うことで、AND とその判定を高速化しています。

計算量

• 時間計算量: 区間 DP が \(O(N^3)\)、到達判定 DP が bitset により \(O(L \cdot N^2 / w)\)（\(w\) はワード長）。全体で \(O(N^3)\)。
• 空間計算量: \(R\) の表が \(O(N^2)\)、bitset 群が \(O(N^2 / w)\)。全体で \(O(N^2)\)。

\(N \le 1000\) なので \(O(N^3)\) は約 \(10^9\) ですが、区間長のループを偶数刻みにしていること、内部が単純な論理演算であることから、C++ では十分間に合います。

実装のポイント

• \(Q\), \(M\) を読み込むが判定には使わない：前述の通り、整数は自由に割り当てられるため色と文字だけで決まります。惑わされないようにしましょう。

• 区間長は偶数のみ：奇数枚は消しきれないので、len += 2 として計算量を半減できます。

• 列ごとのビット列 colR[b]：\(R[a][b]\) を「右端 \(b\) ごとに、真になる左端 \(a\) の集合」として bitset に詰め替えておくと、reach との AND 一発で「進めるか」を判定できます。これがこの解法の高速化の要です。

• 到達不能なら早期終了：ある文字の処理後に reach が空になったら以降は決して満たせないので、fail を立てて打ち切ります。

  ソースコード

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

int main(){
    int N,M,L;
    scanf("%d %d %d",&N,&M,&L);
    static char buf[3000];
    scanf("%s",buf); string S=buf;
    scanf("%s",buf); string P=buf;
    scanf("%s",buf); string T=buf;
    vector<int> Q(L);
    for(int i=0;i<L;i++) scanf("%d",&Q[i]);

    vector<int> col(N);
    for(int i=0;i<N;i++) col[i]=P[i]-'A';

    // R[a][b] : cards a..b-1 are fully reducible (by same-color adjacent removal)
    vector<vector<char>> R(N+1, vector<char>(N+1, 0));
    for(int a=0;a<=N;a++) R[a][a]=1;
    for(int len=2; len<=N; len+=2){
        for(int a=0; a+len<=N; a++){
            int b=a+len;
            char ok=0;
            for(int k=a+1;k<b;k++){
                if(col[k]==col[a] && R[a+1][k] && R[k+1][b]){ ok=1; break; }
            }
            R[a][b]=ok;
        }
    }

    // column bitsets: colR[b] has bit a set iff R[a][b]
    vector<bitset<1001>> colR(N+1);
    for(int b=0;b<=N;b++){
        for(int a=0;a<=b;a++) if(R[a][b]) colR[b].set(a);
    }

    bitset<1001> reach;
    reach.set(0); // gap starts at index 0
    bool fail=false;
    for(int j=0;j<L && !fail;j++){
        bitset<1001> nxt;
        char tc=T[j];
        for(int v=0;v<N;v++){
            if(S[v]!=tc) continue;
            if((reach & colR[v]).any()) nxt.set(v+1);
        }
        reach=nxt;
        if(reach.none()) fail=true;
    }

    bool ans=false;
    if(!fail){
        ans = (reach & colR[N]).any();
    }
    printf(ans?"Yes\n":"No\n");
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。