Official
B - Uniformly Distributed Editorial by QCFium
問題文のマス目に含まれる任意の \(2 \times 2\) のマス目を考えます。
これをマス \((i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1)\) とすると、以下の \(2\) 通りの移動の仕方を考えます。
- \((i, j) \rightarrow (i, j + 1) \rightarrow(i + 1, j + 1)\)
- \((i, j) \rightarrow (i + 1, j) \rightarrow(i + 1, j + 1)\)
\((1, 1)\) から \((i, j)\) までや \((i + 1, j + 1)\) から \((H, W)\) までの移動の仕方は適当に両者同じものを選ぶものとすると、マス \((i, j + 1)\) と \((i + 1, j)\) の色は同じである必要があることが分かります。
これを全ての \(2 \times 2\) のマス目で行うと、以下の事実が得られます :
- \(i + j\) が同じようなマス \((i, j)\) は全て同じ色である必要がある
移動を \(1\) 回すると \(i + j\) が \(1\) だけ増えますから、どう移動しても \(i + j\) が同じマスはちょうど \(1\) つだけ通ります。よって、逆に上の条件が満たされていれば問題文の条件も満たされます。
あとは、答えを \(1\) とした状態から、\(i + j\) が同じマスごとに以下の通り計算すればよいです。
- 全て
.
ならば答えに \(2\) を掛ける R
とB
が両方あれば、答えに \(0\) を掛ける (既に矛盾)- そうでなければ答えを変えない
posted:
last update: