/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
N 枚のカードが横一列に並んでいます。左から i 番目のカードには英小文字 S_i が印字されており、色 P_i で塗られています。ここで A, B, C は互いに異なる 3 色を表し、P_i はそのいずれかです。カードに印字された文字と色は変更できません。
高橋君は、はじめに N 枚すべてのカードに対して、各カードにちょうど 1 つずつ、1 以上 M 以下の整数を書き込みます。異なるカードに同じ整数を書き込んでもかまいません。
整数の書き込みが完了した後、高橋君は次の操作を好きな回数（0 回でもよい）繰り返し行い、好きなタイミングで終了できます。
- 現在残っているカード列の中から、隣り合う 2 枚のカードであって、色が同じかつ書き込まれた整数も同じであるものを 1 組選び、その 2 枚を取り除く。印字された文字は一致していなくてもよい。取り除いた後、残ったカードは隙間を詰めて一列に並べ直す（相対的な順序は保たれる）。
長さ L の英小文字からなる文字列 T と、長さ L の整数列 Q が与えられます。
整数の書き込み方と操作の手順を適切に選ぶことで、操作終了時に残っているカードがちょうど L 枚であり、かつそれらを左から順に見たとき、印字された文字の列が T に一致し、書き込まれた整数の列が Q に一致するようにできるか判定してください。
制約
- 1 \leq L \leq N \leq 1000
- 1 \leq M \leq N
- S は長さ N の英小文字からなる文字列
- P は長さ N の文字列であり、各文字は
A,B,Cのいずれか - T は長さ L の英小文字からなる文字列
- 1 \leq Q_i \leq M (1 \leq i \leq L)
- 入力はすべて整数または文字列である
入力
N M L S P T Q_1 Q_2 \cdots Q_L
1 行目にはカードの枚数 N、書き込める整数の上限 M、目標の列の長さ L がスペース区切りで与えられます。2 行目には各カードに印字された文字を並べた文字列 S が、3 行目には各カードの色を並べた文字列 P が与えられます。4 行目には目標の文字列 T が、5 行目には目標の整数列 Q_1, Q_2, \ldots, Q_L がスペース区切りで与えられます。
出力
条件を満たせるなら Yes を、そうでないなら No を出力せよ。
入力例 1
4 3 2 abcd AABC cd 2 3
出力例 1
Yes
入力例 2
4 2 1 abca AABB a 1
出力例 2
No
入力例 3
12 3 4 abcdefghijkl AACBBACCBAAC cfil 1 2 1 3
出力例 3
Yes
入力例 4
30 30 10 abcdefghijklmnopqrstuvwxyzabcd AABBCCAABBCCAABBCCAAABCABCABCA uvwxyzabcd 30 1 30 2 29 3 28 4 27 5
出力例 4
Yes
入力例 5
1 1 1 z C z 1
出力例 5
Yes
Score : 466 pts
Problem Statement
There are N cards arranged in a row from left to right. The i-th card from the left has a lowercase English letter S_i printed on it and is painted with a color P_i. Here, A, B, and C represent 3 distinct colors, and P_i is one of them. The letters and colors printed on the cards cannot be changed.
First, Takahashi writes an integer between 1 and M, inclusive, on each of the N cards. He may write the same integer on different cards.
After writing the integers, Takahashi can repeat the following operation any number of times (possibly zero) and end the process at any time:
- Choose 1 pair of adjacent cards from the currently remaining cards that have the same color and the same written integer, and remove those 2 cards. The printed letters do not need to match. After removing them, close the gaps and rearrange the remaining cards into a single row (their relative order is preserved).
You are given a string T of length L consisting of lowercase English letters, and a sequence of integers Q of length L.
Determine whether it is possible to choose how to write the integers and the sequence of operations such that, when the operations end, exactly L cards remain, and when viewed from left to right, the sequence of printed letters matches T and the sequence of written integers matches Q.
Constraints
- 1 \leq L \leq N \leq 1000
- 1 \leq M \leq N
- S is a string of length N consisting of lowercase English letters.
- P is a string of length N where each character is
A,B, orC. - T is a string of length L consisting of lowercase English letters.
- 1 \leq Q_i \leq M (1 \leq i \leq L)
- All inputs are integers or strings.
Input
N M L S P T Q_1 Q_2 \cdots Q_L
The first line contains the number of cards N, the upper bound M for the integers that can be written, and the target length L, separated by spaces. The second line contains a string S representing the letters printed on the cards. The third line contains a string P representing the colors of the cards. The fourth line contains the target string T. The fifth line contains the target integer sequence Q_1, Q_2, \ldots, Q_L, separated by spaces.
Output
If the condition can be satisfied, print Yes; otherwise, print No.
Sample Input 1
4 3 2 abcd AABC cd 2 3
Sample Output 1
Yes
Sample Input 2
4 2 1 abca AABB a 1
Sample Output 2
No
Sample Input 3
12 3 4 abcdefghijkl AACBBACCBAAC cfil 1 2 1 3
Sample Output 3
Yes
Sample Input 4
30 30 10 abcdefghijklmnopqrstuvwxyzabcd AABBCCAABBCCAABBCCAAABCABCABCA uvwxyzabcd 30 1 30 2 29 3 28 4 27 5
Sample Output 4
Yes
Sample Input 5
1 1 1 z C z 1
Sample Output 5
Yes