Overview

This problem asks whether it is possible to keep \(L\) cards out of \(N\) cards such that the printed characters match the target string \(T\), while erasing all the remaining cards. Since integers can be assigned freely, the “erasability of cards” is determined solely by the sequence of colors.

Analysis

• The condition for erasing cards is that “two adjacent cards have the same color and the same integer”. Since Takahashi can write integers freely at the beginning, whether “a sequence of cards can be completely erased” depends solely on whether “its sequence of colors can be reduced to empty by repeatedly removing adjacent pairs of the same color”. Specifically, by assigning the same integer to pairs we want to erase together and different integers to different pairs, we can guarantee their erasure.
• For example, if the sequence of colors is A B B A, we can erase the middle B B to get A A, and then erase that to make it empty. On the other hand, A B A B can never be made empty. This can be determined by a stack-based simulation (if the same character arrives, pop from the stack; otherwise push, and check if the stack is empty at the end).
• Consider choosing \(L\) cards such that the string formed by the kept cards matches \(T\). To erase all remaining cards, the sequence of cards between any two chosen cards (as well as outside both ends) must all be “color sequences that can be reduced to empty”.
• Therefore, we realize that we can solve this with dynamic programming (DP) by searching for subsequences matching \(T\) while checking whether the intervals between them are all erasable (reducible).

Algorithm

1. Precomputing erasability: Determine whether the sequence of colors in the interval \([i, j]\) can be reduced to empty (is reducible) as reducible[i][j]. By fixing the left endpoint \(i\) of each interval and expanding the right endpoint \(j\) while simulating the stack, this can be computed in \(O(N^2)\).
2. Precomputing valid transitions: Prepare a bitset valid_prev[k]. This represents the set of indices \(i\) (\(i < k\) and interval \([i+1, k-1]\) is reducible) that can serve as the previous matched index when using the \(k\)-th card of \(S\) for the next character match.
3. Bit DP:
   • Initial state (1st character of \(T\)): If \(S[k] == T[0]\) and interval \([0, k-1]\) is reducible, set the \(k\)-th bit of the DP array dp.
   • Transitions (2nd character of \(T\) and onwards): In a new DP array next_dp, set the \(k\)-th bit if \(S[k] == T[\text{current character}]\) and (dp & valid_prev[k]).any() (meaning there is an intersection between previously reachable points and valid transition points to the current position) is true.
4. Final judgment: Output Yes if there is at least one index \(i\) set in the final dp such that the interval \([i+1, N-1]\) is reducible; otherwise, output No.

Complexity

• Time complexity: \(O(N^2)\)
  • The precomputations take \(O(N^2)\), and the bit DP transitions take \(O(N^2 / 64)\) using bitset.
• Space complexity: \(O(N^2)\)
  • Requires \(O(N^2)\) memory for arrays/bitsets to store reducible and valid_prev.

Implementation Details

• The target integer sequence \(Q\) and the upper limit \(M\) given in the problem statement actually do not directly affect the feasibility judgment. This is because for any erasable sequence of colors, we can always erase them by assigning the same integer to corresponding pairs. Since we can simply write the values of \(Q\) on the kept cards, only the string \(S\), colors \(P\), and target \(T\) act as substantial conditions.

• By computing the DP transitions all at once using bitwise AND operations between “the set of previously reachable positions dp” and “the set of positions valid_prev[k] from which transition to the current position is possible”, the constant factor can be significantly reduced.

  Source Code

#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;
}

---

This editorial was generated by or-glm5.2-high.