ARC120 B Uniformly Distributed
実験をし, 手元でエスパーをすると, 対角線ごとに, すなわち$ (i, j)について$ i + jの値ごとに独立に考えてよいことがわかる. ここで, 塗られたものの数が一定となる条件は, どちらか一方しか登場しないことである. よって, ある$ i + jの値について, 次のような場合分けをした解くことができる.
RとBが両方登場する場合 → その時点で答えが0と決まる.
そうでない場合
すべて.の場合 → .はRにもBにもなれるので答えに2を掛ける
RとBの少なくとも一方が存在する場合 → 残った.は必ず存在する方に合わせなければならないので答えに変動はない
このようにして, この問題を$ O(HW)で解くことができた.