B - Unique XOR Path

Contest Duration: 2022-12-25(Sun) 12:00 - 2022-12-25(Sun) 15:00 (local time) (180 minutes) Back to Home

B - Unique XOR Path Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $700$ 点

問題文

$N$ 行 $M$ 列のグリッドがあります．あなたはグリッドの各マスに $0$ 以上 $2^K-1$ 以下の整数を書き込み，以下の条件を満たしたいです．

左上のマスを出発し，右または下に隣接するマスへの移動を繰り返して，右下のマスへと至るパスを考える．ここで，通ったマス (始点終点を含む) に書かれた整数の総 $\mathrm{XOR}$ が $0$ になるパスを，よいパスと呼ぶことにする．
よいパスはちょうど $1$ つだけ存在し，それは文字列 $S$ が表すパスである．文字列 $S$ が表すパスとは，各 $i$ ( $1 \leq i \leq N+M-2$ ) について， $i$ 回目の移動の際， $S$ の $i$ 文字目が R なら右，D なら下に進むようなパスである．

条件を満たす整数の書き込み方が存在するかどうか判定してください．

$1$ つの入力ファイルにつき， $T$ 個のテストケースを解いてください．

ビット単位 $\mathrm{XOR}$ 演算とは

非負整数 $A, B$ のビット単位 $\mathrm{XOR}$ 、 $A \oplus B$ は、以下のように定義されます。

$A \oplus B$ を二進表記した際の $2^k$ ( $k \geq 0$ ) の位の数は、 $A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である。

例えば、 $3 \oplus 5 = 6$ となります (二進表記すると: $011 \oplus 101 = 110$ )。
一般に $k$ 個の非負整数 $p_1, p_2, p_3, \dots, p_k$ のビット単位 $\mathrm{XOR}$ は $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$ と定義され、これは $p_1, p_2, p_3, \dots, p_k$ の順番によらないことが証明できます。

制約

$1 \leq T \leq 100$
$2 \leq N,M \leq 30$
$1 \leq K \leq 30$
$S$ はちょうど $N-1$ 個の D と $M-1$ 個の R からなる文字列
入力される数はすべて整数

入力

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

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

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

 $N$   $M$   $K$ 
 $S$

出力

各ケースに対し，条件を満たす整数の書き込み方が存在する場合は Yes を，存在しないならば No を出力せよ．出力中の各文字は英大文字・小文字のいずれでもよい．

入力例 1Copy

Copy

4
2 2 1
RD
4 3 1
RDDDR
15 20 18
DDRRRRRRRDDDDRRDDRDRRRRDDRDRDDRRR
20 15 7
DRRDDDDDRDDDRRDDRRRDRRRDDDDDRRRDD

出力例 1Copy

Copy

Yes
No
Yes
No

例えば $1$ ケース目については，以下のようなグリッドを作れば良いです．

11
00

Score : $700$ points

Problem Statement

We have a grid with $N$ rows and $M$ columns. You want to write an integer between $0$ and $2^K-1$ in each square in the grid to satisfy the following condition.

Consider a path that starts at the top-left square, repeatedly moves right or down to an adjacent square, and ends at the bottom-right square. Such a path is said to be good if and only if the total $\mathrm{XOR}$ of the integers written on the squares visited (including the starting and ending points) is $0$ .
There is exactly one good path, which is the path represented by a string $S$ . The path represented by the string $S$ is a path that, for each $i$ ( $1 \leq i \leq N+M-2$ ), the $i$ -th move is right if the $i$ -th character of $S$ is R and down if that character is D.

Determine whether there is a way to write integers that satisfies the condition.

For each input file, solve $T$ test cases.

What is bitwise $\mathrm{XOR}$ ?

The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$ , $A \oplus B$ , is defined as follows.

When $A \oplus B$ is written in binary, the $k$ -th lowest bit ( $k \geq 0$ ) is $1$ if exactly one of the $k$ -th lowest bits of $A$ and $B$ is $1$ , and $0$ otherwise.

For instance, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$ ).
Generally, the bitwise $\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$ , which can be proved to be independent of the order of $p_1, p_2, p_3, \dots, p_k$ .

Constraints

$1 \leq T \leq 100$
$2 \leq N,M \leq 30$
$1 \leq K \leq 30$
$S$ is a string containing exactly $N-1$ Ds and $M-1$ Rs.
All numbers in the input are integers.

Input

The 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$   $M$   $K$ 
 $S$

Output

For each case, print Yes if there is a way to write integers that satisfies the condition, and No otherwise. Each character in the output may be either uppercase or lowercase.

Sample Input 1Copy

Copy

4
2 2 1
RD
4 3 1
RDDDR
15 20 18
DDRRRRRRRDDDDRRDDRDRRRRDDRDRDDRRR
20 15 7
DRRDDDDDRDDDRRDDRRRDRRRDDDDDRRRDD

Sample Output 1Copy

Copy

Yes
No
Yes
No

As an example, for the first case, you can make the grid as follows.

11
00