atcoder#AGC060B. [AGC060B] Unique XOR Path
[AGC060B] Unique XOR Path
配点 : 点
問題文
行 列のグリッドがあります． あなたはグリッドの各マスに 以上 以下の整数を書き込み，以下の条件を満たしたいです．
- 左上のマスを出発し，右または下に隣接するマスへの移動を繰り返して，右下のマスへと至るパスを考える． ここで，通ったマス (始点終点を含む) に書かれた整数の総 が になるパスを，よいパスと呼ぶことにする．
- よいパスはちょうど つだけ存在し，それは文字列 が表すパスである．
文字列 が表すパスとは，各 () について， 回目の移動の際， の 文字目が
Rなら右，Dなら下に進むようなパスである．
条件を満たす整数の書き込み方が存在するかどうか判定してください．
つの入力ファイルにつき， 個のテストケースを解いてください．
ビット単位 $\mathrm{XOR}$ 演算とは
非負整数 $A, B$ のビット単位 $\mathrm{XOR}$ 、$A \oplus B$ は、以下のように定義されます。
- $A \oplus B$ を二進表記した際の $2^k$ ($k \geq 0$) の位の数は、$A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。
一般に 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 の順番によらないことが証明できます。
制約
- はちょうど 個の
Dと 個のRからなる文字列 - 入力される数はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
各ケースは以下の形式で与えられる．
出力
各ケースに対し，条件を満たす整数の書き込み方が存在する場合は Yes を，存在しないならば No を出力せよ．
出力中の各文字は英大文字・小文字のいずれでもよい．
4
2 2 1
RD
4 3 1
RDDDR
15 20 18
DDRRRRRRRDDDDRRDDRDRRRRDDRDRDDRRR
20 15 7
DRRDDDDDRDDDRRDDRRRDRRRDDDDDRRRDD
Yes
No
Yes
No
例えば ケース目については，以下のようなグリッドを作れば良いです．
11
00