/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 1400 点
問題文
N \times N のマス盤面があります。 あなたは、隣接する（辺を共有する）どの二つのマスも同じ色にならないように、すべてのマスを 3 色で塗ろうとしています。
盤面の最も外側は、すでに塗ってしまいました。盤面の残りを意図通りに塗ることができるか判定してください。
より正確には、文字 1, 2, 3 からなる長さ 4N-4 の文字列 S が与えられます。この文字列は、盤面の最も外側のマスの色を、(1, 1) から始めて時計回りに表します。
厳密には、S の i 文字目は次のマスの色を表します。
- 1 \le i \le N-1 のとき、(1, i)
- N \le i \le 2N-2 のとき、(i - (N-1), N)
- 2N-1 \le i \le 3N-3 のとき、(N, 3N - 1 - i)
- 3N-2 \le i \le 4N-4 のとき、(4N-2 - i, 1)
ここで、(r,c) は r 行 c 列目のマスを指します。
盤面の最も外側では、隣接するどの二つのマスも同じ色でないことが保証されます。
各入力ファイルについて、T 個のテストケースを解いてください。
制約
- 1 \le T \le 5 \cdot 10^4
- 3 \le N \le 2 \cdot 10^5
- S は文字
1,2,3からなる長さ 4N-4 の文字列である。 - 1 \le i \le 4N-5 のとき S_i \neq S_{i+1} であり、また S_{4N-4} \neq S_1 である。
- 各入力ファイル内の N の総和は 2\cdot 10^5 を超えない。
- 入力中のすべての数は整数である。
入力
入力は標準入力から以下の形式で与えられる。
T case_1 case_2 \vdots case_T
各ケースは以下の形式である。
N S
出力
各テストケースについて、盤面の残りを意図通りに 3 色で塗る方法があれば YES と、なければ NO と出力せよ。出力中の各文字は英大文字・小文字のいずれでもよい。
入力例 1
4 3 12312312 4 121212121212 7 321312312312121212121321 7 321312312312121312121321
出力例 1
NO YES NO YES
一つ目と三つ目のテストケースでは、盤面の残りを意図通りに塗る方法がないことが示せます。二つ目と四つ目のテストケースで盤面の残りを意図通りに塗る方法を以下に示します。
Score : 1400 points
Problem Statement
You have an N \times N grid board. You want to color all cells in 3 colors so that no two adjacent (edge-sharing) cells have the same color.
You have already painted the border of the board. Determine if you can color the rest of the board properly.
More precisely, you are given a string S of length 4N-4 consisting of characters 1, 2, and 3. The string denotes the colors of the cells on the border, starting from the cell (1, 1), in clockwise order.
Strictly speaking, the i-th character of S denotes the color of the cell:
- (1, i) for 1 \le i \le N-1
- (i - (N-1), N) for N \le i \le 2N-2
- (N, 3N - 1 - i) for 2N-1 \le i \le 3N-3
- (4N-2 - i, 1) for 3N-2 \le i \le 4N-4.
Here, (r,c) denotes the cell in the r-th row and the c-th column.
It is guaranteed that no two adjacent cells on the border have the same color.
Solve T test cases for each input file.
Constraints
- 1 \le T \le 5 \cdot 10^4
- 3 \le N \le 2 \cdot 10^5
- S is a string of length 4N-4 consisting of characters
1,2, and3. - S_i \neq S_{i+1} for 1 \le i \le 4N-5, and S_{4N-4} \neq S_1.
- The sum of N in one input file doesn't exceed 2\cdot 10^5.
- All numbers in the input are integers.
Input
Input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is in the following format:
N S
Output
For each test case, output YES if there is a way to color the rest of the board in 3 colors properly, and NO otherwise. You can output each letter in any case (upper or lower).
Sample Input 1
4 3 12312312 4 121212121212 7 321312312312121212121321 7 321312312312121312121321
Sample Output 1
NO YES NO YES
It can be shown that there is no way to properly color the rest of the board in the first and the third test cases. The proper colorings for the second and fourth test cases are shown below.