Summary

We select the cards to be kept as a subsequence of \(S\) and determine whether the card sequences between them can all be erased.
By normalizing the operation “erase adjacent cards of the same color” on the color sequence using a stack, we perform dynamic programming in \(O(NL)\) time.

Analysis

On the Written Integers

For the cards to be kept, we can write \(Q_1,Q_2,\ldots,Q_L\) on them from left to right.

On the other hand, we can write the integer \(1\) on all cards to be erased. Then, the condition “the integers are equal” is always satisfied between any pair of cards to be erased, so whether a range can be erased depends solely on its colors.

Also, operations can be terminated at any time. Therefore, even if the remaining cards at the end share the same color and integer, there is no need to erase them further.

Consequently, the values of \(M\) and \(Q\) do not affect the erasability in this problem.

The Ranges Between Kept Cards Must Be Erased Independently

Let the indices of the cards to be kept be

\[ i_0 < i_1 < \cdots < i_{L-1} \]

In this case, all of the following intervals must be completely erased:

• Before \(i_0\)
• Between \(i_j\) and \(i_{j+1}\)
• After \(i_{L-1}\)

Since cards across a kept card can never become adjacent, each interval can be considered independently.

Determining Whether a Color Sequence Can Be Erased

We push colors into a stack from left to right and perform the following:

• If the current color is the same as the top of the stack, pop the top.
• If it is different, push the new color.

For example, for ABBA:

\[ [] \to [A] \to [A,B] \to [A] \to [] \]

so it can be completely erased.

On the other hand, ABAB has the same count of each color, but the stack does not end up empty. Therefore, erasability cannot be determined solely by the counts of each color, and the order of elements must be taken into account.

We define the sequence remaining in the stack after processing as the “state” of the color sequence. Let \(\mathrm{state}[k]\) be the state after processing the prefix of length \(k\) of the color sequence \(P\). The half-open interval \(P[l:r]\) being completely erasable is equivalent to

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

This is because the canonical form obtained by repeatedly erasing adjacent identical colors is unique, and the state being identical before and after adding an interval means that the entire interval can be erased.

Accelerating the DP

Consider the following DP:

\[ dp[j][i] \]

defined as “whether we can construct \(T_0, \ldots, T_j\) such that the card at index \(i\) is kept as the card corresponding to \(T_j\).”

Let \(k\) be the index of the previously kept card. The transition conditions are as follows:

• \(k < i\)
• \(dp[j-1][k]\) is true
• \(S_i = T_j\)
• The range between \(k\) and \(i\), i.e., \(P[k+1:i]\), can be erased.

The last condition can be rephrased as

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

Checking all \(k\) for each \(i\) would take \(O(LN^2)\) time, which is too slow. Instead, by scanning from left to right and recording all valid \(\mathrm{state}[k+1]\) encountered so far in seen, each transition can be checked in \(O(1)\) time, reducing the total DP complexity to \(O(LN)\).

Algorithm

1. Convert colors A, B, C into \(0, 1, 2\), respectively.
2. Scan \(P\) from left to right and find the stack state \(\mathrm{state}[k]\) for each prefix \(k\).
   • If the top color of the stack is equal to the current color, pop by moving back to parent.
   • If different, transition to a new state.
   • Assign the same state ID to identical stack contents.
3. Find candidates for the first kept card:
   • \(S_i = T_0\)
   • The prefix before it can be erased, i.e., \(\mathrm{state}[i] = 0\).
4. Update the DP for \(j = 1, 2, \ldots, L-1\):
   • Scan position \(i\) from left to right.
   • If position \(i-1\) is valid as a previously kept card, record \(\mathrm{state}[i]\) into seen.
   • If \(S_i = T_j\) and \(\mathrm{state}[i]\) is in seen, then position \(i\) can be used as the current kept card.
5. If there is at least one candidate for the last kept card position \(i\) that satisfies the condition for erasing the suffix:

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

then output Yes; otherwise, output No.

Complexity

• Time Complexity: \(O(NL)\)
• Space Complexity: \(O(N)\)

Implementation Notes

• state[k] represents the state after processing the first \(k\) colors.

• Copying the entire stack every time is slow, so we represent each state as a persistent stack defined by its “parent state” and “top color”.

• By reusing transition[(state, color)], identical stack contents are guaranteed to be assigned the same state ID.

• Instead of re-initializing seen at each DP step, a timestamp technique recording the step number mark can be used.

• When \(L=1\), skip the DP transitions and simply check if both the prefix and suffix intervals can be erased.

  Source Code

import sys

input = sys.stdin.readline

N, M, L = map(int, input().split())
S = input().strip()
P = input().strip()
T = input().strip()
Q = list(map(int, input().split()))

color_id = {'A': 0, 'B': 1, 'C': 2}

parent = [-1]
top = [-1]
transition = {}
state = [0] * (N + 1)
cur = 0

for i, ch in enumerate(P):
    c = color_id[ch]
    if top[cur] == c:
        cur = parent[cur]
    else:
        key = cur * 3 + c
        nxt = transition.get(key)
        if nxt is None:
            nxt = len(parent)
            transition[key] = nxt
            parent.append(cur)
            top.append(c)
        cur = nxt
    state[i + 1] = cur

prev = [False] * N
for i in range(N):
    if S[i] == T[0] and state[i] == 0:
        prev[i] = True

seen = [0] * len(parent)

for j in range(1, L):
    mark = j
    cur_dp = [False] * N
    target = T[j]

    for i in range(N):
        if i > 0 and prev[i - 1]:
            seen[state[i]] = mark
        if S[i] == target and seen[state[i]] == mark:
            cur_dp[i] = True

    prev = cur_dp

goal_state = state[N]
answer = any(prev[i] and state[i + 1] == goal_state for i in range(N))
print("Yes" if answer else "No")

---

This editorial was generated by gpt-5.6-sol-high.