概要

\(N\) 枚のカードから、印字された文字が目標文字列 \(T\) に一致するように \(L\) 枚のカードを残し、残りのカードをすべて消去できるかを判定する問題です。整数は自由に割り当てられるため、「カードの消去可能性」は色の並びによってのみ決定されます。

考察

• カードを消去する条件は「隣り合う2枚が同じ色かつ同じ整数」です。高橋君は最初に自由に整数を書き込めるため、「あるカードの列をすべて消去できるか」は「その列の色の並びが、隣り合う同じ色のペアを繰り返し取り除くことで空にできるか」にのみ依存します。具体的には、消去したいペア同士に同じ整数を割り当て、異なるペアには異なる整数を割り当てることで確実に消去できます。
• たとえば、色の列が A B B A なら、真ん中の B B を消去して A A となり、それを消去して空にできます。逆に A B A B はどうやっても消去できません。これはスタックを用いたシミュレーションで判定可能です（同じ文字が来たらスタックから pop、違うなら push し、最後にスタックが空かどうかを見る）。
• 最終的に残したいカードの文字列が \(T\) に一致するように \(L\) 枚のカードを選ぶことを考えます。残りのカードをすべて消去するには、選んだカードと選んだカードの間（および両端の外側）にあるカードの列がすべて「空にできる色の並び」でなければなりません。
• したがって、\(T\) に一致する部分列を探しつつ、その間の区間がすべて消去可能（ reducible ）であるかを判定するDP（動的計画法）を行えばよいと気づきます。

アルゴリズム

1. 消去可能性の事前計算: 区間 \([i, j]\) の色の列が空にできるか（ reducible か）を reducible[i][j] として求めます。各区間の左端 \(i\) を固定し、右端 \(j\) を伸ばしながらスタックを模倣することで \(O(N^2)\) で計算できます。
2. 遷移可能な位置の事前計算: valid_prev[k] というビット集合を用意します。これは \(S\) の \(k\) 番目のカードを次の文字のマッチに使うとき、直前のマッチとして使えるインデックス \(i\) （\(i < k\) かつ区間 \([i+1, k-1]\) が reducible）の集合をビットで表したものです。
3. ビットDP:
   • 初期状態（\(T\) の \(1\) 文字目）: \(S[k] == T[0]\) かつ区間 \([0, k-1]\) が reducible なら、DP配列 dp の \(k\) ビット目を立てます。
   • 遷移（\(T\) の \(2\) 文字目以降）: 新しいDP配列 next_dp において、\(S[k] == T[\text{現在の文字}]\) かつ (dp & valid_prev[k]).any() （過去の到達点と現在位置への遷移可能点の共通部分が存在する）が真なら \(k\) ビット目を立てます。
4. 最終判定: 最後の dp に含まれるインデックス \(i\) で、かつ区間 \([i+1, N-1]\) が reducible なものが1つでもあれば Yes、なければ No となります。

計算量

• 時間計算量: \(O(N^2)\)
  • 事前計算が \(O(N^2)\)、ビットDPの遷移が bitset を用いることで \(O(N^2 / 64)\) となります。
• 空間計算量: \(O(N^2)\)
  • reducible と valid_prev を保持するための配列・ビット集合に \(O(N^2)\) のメモリを必要とします。

実装のポイント

• 問題文で与えられる目標の整数列 \(Q\) や上限 \(M\) は、実は判定に直接関与しません。消去可能な色の並びに対しては、対応するペアに同じ整数を割り当てることで必ず消去できるためです。残すカードには単に \(Q\) の値を書き込めばよいので、文字列 \(S\) と色 \(P\) そして \(T\) のみが実質的な条件となります。

• DPの遷移を「過去に到達可能な位置の集合 dp」と「現在位置への遷移可能な位置の集合 valid_prev[k]」のビット単位のAND演算で一気に処理することで、定数倍を大幅に削減できます。

  ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <bitset>

using namespace std;

const int MAXN = 1005;

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 i = 0; i < L; ++i) cin >> Q[i];

    // reducible[i][j] is true if P[i..j] is reducible to empty
    vector<vector<bool>> reducible(N, vector<bool>(N, false));
    for (int i = 0; i < N; ++i) {
        vector<char> stk;
        for (int j = i; j < N; ++j) {
            if (!stk.empty() && stk.back() == P[j]) {
                stk.pop_back();
            } else {
                stk.push_back(P[j]);
            }
            reducible[i][j] = stk.empty();
        }
    }

    // valid_prev[k] has bit i set if i < k and (i + 1 == k || reducible[i+1][k-1])
    vector<bitset<MAXN>> valid_prev(N);
    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < k; ++i) {
            if (i + 1 == k || reducible[i + 1][k - 1]) {
                valid_prev[k].set(i);
            }
        }
    }

    bitset<MAXN> dp;
    // l = 1
    for (int k = 0; k < N; ++k) {
        if (S[k] == T[0]) {
            if (k == 0 || reducible[0][k - 1]) {
                dp.set(k);
            }
        }
    }

    for (int l = 2; l <= L; ++l) {
        bitset<MAXN> next_dp;
        for (int k = 0; k < N; ++k) {
            if (S[k] == T[l - 1]) {
                if ((dp & valid_prev[k]).any()) {
                    next_dp.set(k);
                }
            }
        }
        dp = next_dp;
        if (dp.none()) break;
    }

    bool ans = false;
    for (int i = 0; i < N; ++i) {
        if (dp.test(i)) {
            if (i == N - 1 || reducible[i + 1][N - 1]) {
                ans = true;
                break;
            }
        }
    }

    cout << (ans ? "Yes" : "No") << "\n";

    return 0;
}

この解説は or-glm5.2-high によって生成されました。