B - Pair Guessing

Contest Duration: 2024-11-24(Sun) 12:00 - 2024-11-24(Sun) 15:00 (local time) (180 minutes) Back to Home

B - Pair Guessing Editorial

Time Limit: 2 sec / Memory Limit: 2048 MB

配点 : $1000$ 点

問題文

$N$ 個の、長さ $N$ の $01$ 文字列 $S_1,\ldots,S_N$ が与えられます。 $S_i$ の $j$ 文字目を $S_{i,j}$ と表します。ここで、 $S_{i,j}=\$ 1 を満たす整数組 $(i,j)$ が少なくとも一つ存在することが制約より保証されています。

高橋君と青木君が以下のようなゲームを行います。

高橋君が $1 \leq i,j \leq N, S_{i,j}=\$ 1 を満たす整数組 $(i,j)$ を $1$ つ選ぶ。
$0$ 回以上 $N$ 回以下、青木君が高橋君に質問を行う。各質問では青木君が $1\leq i',j' \leq N$ を満たす整数組 $(i',j')$ を選び、「 $i=i'$ と $j=j'$ のうち少なくとも一方が成り立つ」の真偽を高橋君から教えてもらう。
青木君が $(i,j)$ を予想する。予想が当たっていれば青木君の勝ち、そうでなければ負けとなる。

青木君は高橋君が選ぶ $(i,j)$ の候補、すなわち $S_1,\ldots,S_N$ を知った状態でゲームを行います。また、上記2では以前の質問に対する返事を聞いたうえで $(i', j')$ を選ぶことができます。

青木君が適切な戦略を取った場合、高橋君の $(i,j)$ の選び方や運によらず必ずゲームに勝てるかどうかを判定してください。

$1$ つの入力につきテストケースは $T$ 個あります。

制約

$1 \leq T \leq 2 \times 10^5$
$1 \leq N \leq 500$
$1$ つの入力の中のテストケースすべてにわたる $N^2$ の総和は $500^2$ 以下である
$S_i$ は長さ $N$ の $01$ 文字列
$S_{i,j}=\$ 1 を満たす整数組 $(i,j)$ が少なくとも一つ存在する

入力

入力は以下の形式で標準入力から与えられる。

 $T$ 
 $case_1$ 
 $\vdots$ 
 $case_T$

各テストケースは以下の形式で与えられる。

 $N$ 
 $S_1$ 
 $\vdots$ 
 $S_N$

出力

各テストケースに対し、青木君が必ずゲームに勝てるならば Yes と、そうでなければ No と出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

Yes
No
Yes

$1$ 番目のテストケースに対するゲームの一例を以下に示します。

高橋君が $S_{i,j}=\$ 1 を満たす $(i,j)$ として $(2,2)$ を選ぶ。
青木君が $2$ 回質問を行う。 $1$ 回目の質問では $(i',j')=(1,1)$ として、高橋君から「 $i=1$ と $j=1$ のうち少なくとも一方が成り立つ」が偽であると教えてもらう。 $2$ 回目の質問では $(i',j')=(2,2)$ として、高橋君から「 $i=2$ と $j=2$ の少なくとも一方が成り立つ」が真であると教えてもらう。
青木君が $(i,j)=(2,2)$ と予想する。この予想は当たっているため、青木君の勝ちである。

これはあくまでゲームの一例であり、青木君の戦略が適切とは限りません。しかし、青木君が適切な戦略を取った場合には必ず青木君がゲームに勝つため、 $1$ 番目のテストケースに対する出力は Yes になります。

Score : $1000$ points

Problem Statement

You are given $N$ strings $S_1, \ldots, S_N$ , each of length $N$ , consisting only of 0 and 1. Let $S_{i,j}$ denote the $j$ -th character of $S_i$ . It is guaranteed by the constraints that there exists at least one integer pair $(i, j)$ satisfying $S_{i,j} =$ 1.

Takahashi and Aoki play the following game:

Takahashi chooses one integer pair $(i, j)$ satisfying $1 \leq i, j \leq N$ and $S_{i,j} =$ 1.
Aoki asks Takahashi at least $0$ and at most $N$ questions. In each question, Aoki chooses an integer pair $(i', j')$ satisfying $1 \leq i', j' \leq N$ , and Takahashi tells Aoki whether "At least one of $i = i'$ or $j = j'$ holds" is true or false.
Aoki guesses $(i, j)$ . If his guess is correct, Aoki wins; otherwise, he loses.

Aoki knows the possible choices of $(i, j)$ that Takahashi can choose, that is, he knows $S_1, \ldots, S_N$ before playing the game. Also, in step 2, Aoki can choose $(i', j')$ based on the answers to previous questions.

Determine whether Aoki can always win the game regardless of Takahashi's choice of $(i, j)$ and randomness, if he uses an appropriate strategy.

There are $T$ test cases in each input.

Constraints

$1 \leq T \leq 2 \times 10^5$
$1 \leq N \leq 500$
The sum of $N^2$ over all test cases in each input is at most $500^2$ .
$S_i$ is a string of length $N$ consisting of 0 and 1.
There is at least one integer pair $(i, j)$ satisfying $S_{i,j} =$ 1.

Input

The input is given from Standard Input in the following format:

 $T$ 
 $case_1$ 
 $\vdots$ 
 $case_T$

Each test case is given in the following format:

 $N$ 
 $S_1$ 
 $\vdots$ 
 $S_N$

Output

For each test case, print Yes if Aoki can always win the game, and No otherwise.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Yes
No
Yes

In the first test case, an example of the game is as follows:

Takahashi chooses $(i, j) = (2, 2)$ satisfying $S_{i,j}=\$ 1.
Aoki asks two questions. In the first question, he chooses $(i', j') = (1, 1)$ . Takahashi tells him that "At least one of $i = 1$ or $j = 1$ holds" is false. In the second question, he chooses $(i', j') = (2, 2)$ . Takahashi tells him that "At least one of $i = 2$ or $j = 2$ holds" is true.
Aoki guesses $(i, j) = (2, 2)$ . Since his guess is correct, Aoki wins.

This is just an example of the game, and Aoki's strategy might not be optimal. However, if Aoki uses an appropriate strategy, he can always win the game, so the output for the first test case is Yes.