概要

カード列から「同じ色かつ同じ整数」の隣り合うペアを消去していき、残ったカードの文字・整数列を目標の \(T, Q\) に一致させられるかを判定する問題です。

整数は自由に書き込めるため、本質的には「色のスタック消去ルールのみで、残すカード以外の区間をすべて消去できるか」という判定問題に帰着され、動的計画法 (DP) を用いて効率的に解くことができます。

---

考察

1. 整数 \(M\) および \(Q\) の無関係性

問題文では各カードに書き込む整数や目標の整数列 \(Q\) が与えられますが、書き込む整数は \(1\) 以上 \(M\) 以下の範囲で自由に選ぶことができます。 消去したいカード同士には同じ整数を、残したいカードには目標通りの整数 \(Q_k\) を適切に割り当てれば、整数の条件は常に満たせます。したがって、整数 \(M\) や \(Q\) の値は判定に影響せず、「各カードの色 \(P\) と文字 \(S\) のみ」を考慮すればよいことがわかります。

2. 区間の消去可能性とスタック状態

色 \(A, B, C\) を持つカードのペア消去は、括弧の対応関係（スタック）と全く同じ構造をしています。 カード列の先頭から順に色を見ていき、スタックのトップと同じ色ならポップ（消去）、違う色ならプッシュする操作を考えます。

\(i\) 枚目までのプレフィックスに対するスタックの状態を \(\text{Stack}[i]\) とします。 このとき、区間 \([l, r]\)（\(l\) 番目から \(r\) 番目のカード群）がすべて消去可能であるための必要十分条件は \(\text{Stack}[l-1] == \text{Stack}[r]\) となることです。

3. 目標の達成条件

目標の文字列 \(T\)（長さ \(L\)）を残すために、元配列から選ぶカードの位置を \(1 \le i_1 < i_2 < \dots < i_L \le N\) とします。 これが有効な選び方である条件は以下の通りです：

1. 文字の一致: 各 \(k \in [1, L]\) について \(S_{i_k} = T_k\)
2. 間のカードがすべて消去可能:
   • 先頭から \(i_1\) の直前まで: \(\text{Stack}[0] == \text{Stack}[i_1 - 1]\)
   • \(i_k\) の直後から \(i_{k+1}\) の直前まで: \(\text{Stack}[i_k] == \text{Stack}[i_{k+1} - 1]\)
   • \(i_L\) の直後から末尾まで: \(\text{Stack}[i_L] == \text{Stack}[N]\)

---

アルゴリズム

1. スタック状態の事前計算と ID 化（座標圧縮）

   • 各 \(i \ (0 \le i \le N)\) について、プレフィックス \(P[0 \dots i-1]\) に対するスタック文字列 \(\text{Stack}[i]\) を計算します。
   • 文字列比較を高速化するため、ユニークなスタック文字列に整数 ID（\(0, 1, 2, \dots\)）を割り当てます。

2. 動的計画法 (DP)

   • DP 状態: dp[j] ＝ \(T\) の \(k\) 文字目までをマッチさせ、その \(k\) 文字目として \(S_{j-1}\) を選ぶことが可能かを表すブール値。
   • 遷移:
     • \(k = 1 \dots L\) の順にループします。
     • 前のステップで可能だったカード位置 \(p\) の直後のスタック ID（\(\text{Stack}[p]\)）の集合を保持しておきます（\(k=1\) のときは \(\text{Stack}[0]\) のみ）。
     • 各 \(j \ (1 \le j \le N)\) について、\(S_{j-1} == T_{k-1}\) かつ \(\text{Stack}[j-1]\) が上記の集合に含まれていれば、next_dp[j] = true とします。
   • 最終判定:
     • \(k = L\) 完了後、dp[j] == true かつ \(\text{Stack}[j] == \text{Stack}[N]\) となる \(j\) が存在すれば Yes、存在しなければ No と出力します。

---

計算量

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

  • 各位置のスタック文字列の長さは最大 \(N\) であり、\(N+1\) 個のスタック文字列構築と ID 化（std::map）に \(O(N^2 \log N)\) または \(O(N^2)\)。
  • DP の更新は外側 \(L\) 回、内側 \(N\) 回のループで、各要素の更新は \(O(1)\) です。
  • \(L \le N\) であるため、全体として十分高速に動作します。

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

  • 長さ最大 \(N\) のスタック文字列を \(N+1\) 個保持するために \(O(N^2)\) のメモリを使用します。

---

実装のポイント

• スタック文字列の ID 化: スタック状態は文字列のままDP内で比較すると1回の比較に \(O(N)\) かかってしまいます。事前に map<string, int> を用いて整数 ID に圧縮しておくことで、DP 内の判定を \(O(1)\) で行えるようにしています。

• インデックスの対応関係: 1-based インデックスと 0-based インデックスの対応（特に \(S[j-1]\) や \(\text{Stack}[j-1]\) と \(\text{Stack}[j]\) の関係）を正しく管理することが重要です。

  ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, L;
    if (!(cin >> N >> M >> L)) return 0;

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

    vector<int> Q(L);
    for (int i = 0; i < L; ++i) {
        cin >> Q[i];
    }

    // Precompute stack state strings for P[0...i-1] for i = 0...N
    vector<string> Stack(N + 1);
    Stack[0] = "";
    for (int i = 1; i <= N; ++i) {
        string cur = Stack[i - 1];
        char c = P[i - 1];
        if (!cur.empty() && cur.back() == c) {
            cur.pop_back();
        } else {
            cur.push_back(c);
        }
        Stack[i] = cur;
    }

    // Compress Stack strings to integer IDs
    map<string, int> stack_to_id;
    vector<int> stack_id(N + 1);
    int num_ids = 0;
    for (int i = 0; i <= N; ++i) {
        if (stack_to_id.find(Stack[i]) == stack_to_id.end()) {
            stack_to_id[Stack[i]] = num_ids++;
        }
        stack_id[i] = stack_to_id[Stack[i]];
    }

    // DP state: dp[j] indicates if T[0...k-1] can be matched ending at S[j-1]
    vector<bool> dp(N + 1, false);

    for (int k = 1; k <= L; ++k) {
        vector<bool> next_dp(N + 1, false);
        vector<bool> valid(num_ids, false);

        for (int j = 1; j <= N; ++j) {
            int p = j - 1;
            if (k == 1) {
                if (p == 0) {
                    valid[stack_id[0]] = true;
                }
            } else {
                if (p >= 1 && dp[p]) {
                    valid[stack_id[p]] = true;
                }
            }

            if (S[j - 1] == T[k - 1] && valid[stack_id[j - 1]]) {
                next_dp[j] = true;
            }
        }
        dp = next_dp;
    }

    // Final answer check
    bool ok = false;
    for (int j = 1; j <= N; ++j) {
        if (dp[j] && stack_id[j] == stack_id[N]) {
            ok = true;
            break;
        }
    }

    if (ok) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}

---

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