/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
0, 1, ? のみからなる長さ N の文字列 S=S_1S_2\dots S_N が与えられます。
これから S に含まれるすべての ? を 0, 1 のいずれかに置き換えることで、以下の条件がすべて満たされるようにしたいです。
- S は
1をちょうど K 個含む。 - K 個の
1は連続している。すなわち、ある i\ (1 \leq i \le N-K+1) があって、S_i=S_{i+1}=\dots=S_{i+K-1}=1が成り立つ。
条件を満たすような ? の置き換え方がちょうど 1 通りであるか判定してください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \leq T \leq 10^5
- 1 \leq K < N \leq 3 \times 10^5
- S は
0,1,?のみからなる長さ N の文字列 - 全テストケースに対する N の総和は 3 \times 10^5 以下
入力
入力は以下の形式で標準入力から与えられます。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各ケースは以下の形式で与えられます。
N K S
出力
T 行出力してください。i 行目には i 番目のテストケースについて、条件を満たすような ? の置き換え方がちょうど 1 通りである場合は Yes を、そうでない場合は No を出力してください。
入力例 1
4 3 2 1?? 4 2 ?1?0 6 3 011?1? 10 5 00?1???10?
出力例 1
Yes No No Yes
1 個目のテストケースについて、例えば S を 101 に変えることができますが、この場合は 1 が連続していないため、条件を満たしません。 S が条件を満たすようにするには S を 110 に変えるしかありません。
2 個目のテストケースについて、 S が条件を満たすようにするには S を 1100, または 0110 に変えればよく、条件を満たすような ? の置き換え方は 2 通りあります。
3 個目のテストケースについて、S が条件を満たすよう ? を置き換える方法は存在しません。
Score : 300 points
Problem Statement
You are given a string of length N, S=S_1S_2\dots S_N, consisting of 0, 1, and ?.
We like to replace every ? with 0 or 1 so that all of the following conditions are satisfied.
- S contains exactly K occurrences of
1. - These K occurrences of
1are consecutive. That is, there is an i\ (1 \leq i \le N-K+1) such that S_i=S_{i+1}=\dots=S_{i+K-1}=1.
Determine whether there is exactly one way to replace the characters to satisfy the conditions.
You have T test cases to solve.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq K < N \leq 3 \times 10^5
- S is a string of length N consisting of
0,1, and?. - The sum of N across the test cases is at most 3 \times 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each case is in the following format:
N K S
Output
Print T lines. The i-th line should contain Yes if, for the i-th test case, there is exactly one way to replace the characters to satisfy the conditions, and No otherwise.
Sample Input 1
4 3 2 1?? 4 2 ?1?0 6 3 011?1? 10 5 00?1???10?
Sample Output 1
Yes No No Yes
For the first test case, turning S into 101, for instance, does not satisfy the conditions since the 1s will not be consecutive. The only way to satisfy the conditions is to turn S into 110.
For the second test case, we may turn S into 1100 or 0110 to satisfy the conditions, so there are two ways to satisfy them.
For the third test case, there is no way to replace the characters to satisfy the conditions.