/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
0 と 1 からなる長さ 2 以上の整数列 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_M) が与えられます。
A に対し、以下の操作を何回でも行うことができます。
- 1 \leq i \leq |A|-1 を満たす整数 i を選ぶ。
- A_i と A_{i+1} の間に 1-A_i と 1-A_{i+1} をこの順で挿入する。
A を B に一致させることができるかどうかを判定してください。
1 つの入力につき、T 個のテストケースを解いてください。
制約
- 1 \leq T \leq 10^5
- 2 \leq N \leq M \leq 2 \times 10^5
- A_i,B_i \in \{0,1\}
- すべてのテストケースにおける N+M の総和は 4 \times 10^5 以下
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケース \mathrm{case}_t は以下の形式で与えられる。
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_M
出力
答えを合計 T 行で出力せよ。
t 行目には、t 番目のテストケースについて A を B に一致させることができるならば Yes を、できないならば No を出力せよ。
入力例 1
3 3 7 0 1 1 0 1 0 1 1 0 1 2 4 0 1 0 1 0 1 3 4 0 0 0 0 0 0 1
出力例 1
Yes Yes No
1 つ目のテストケースについて、最初、A=(0,1,1) です。
まず、i として 2 を選ぶと、A=(0,1,0,0,1) となります。
次に、i として 3 を選ぶと、A=(0,1,0,1,1,0,1) となります。
Score : 700 points
Problem Statement
You are given integer sequences A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_M) of length 2 or more, consisting of 0s and 1s.
You can perform the following operation on A any number of times:
- Choose an integer i satisfying 1 \leq i \leq |A|-1.
- Insert 1-A_i and 1-A_{i+1} in this order between A_i and A_{i+1}.
Determine whether it is possible to make A equal to B.
Solve T test cases per input.
Constraints
- 1 \leq T \leq 10^5
- 2 \leq N \leq M \leq 2 \times 10^5
- A_i, B_i \in \{0,1\}
- The sum of N+M over all test cases is at most 4 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case \mathrm{case}_t is given in the following format:
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_M
Output
Output the answers over a total of T lines.
The t-th line should contain Yes if it is possible to make A equal to B for the t-th test case, and No otherwise.
Sample Input 1
3 3 7 0 1 1 0 1 0 1 1 0 1 2 4 0 1 0 1 0 1 3 4 0 0 0 0 0 0 1
Sample Output 1
Yes Yes No
For the first test case, initially A=(0,1,1).
First, choosing i=2 gives A=(0,1,0,0,1).
Next, choosing i=3 gives A=(0,1,0,1,1,0,1).