atcoder#AGC060B. [AGC060B] Unique XOR Path
[AGC060B] Unique XOR Path
Score : points
Problem Statement
We have a grid with rows and columns. You want to write an integer between and 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 of the integers written on the squares visited (including the starting and ending points) is .
- There is exactly one good path, which is the path represented by a string .
The path represented by the string is a path that, for each (), the -th move is right if the -th character of is
Rand down if that character isD.
Determine whether there is a way to write integers that satisfies the condition.
For each input file, solve 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.
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
- is a string containing exactly
Ds andRs. - All numbers in the input are integers.
Input
The input is given from Standard Input in the following format:
Each case is in the following format:
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.
4
2 2 1
RD
4 3 1
RDDDR
15 20 18
DDRRRRRRRDDDDRRDDRDRRRRDDRDRDDRRR
20 15 7
DRRDDDDDRDDDRRDDRRRDRRRDDDDDRRRDD
Yes
No
Yes
No
As an example, for the first case, you can make the grid as follows.
11
00