AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Regular Contest 120 B – Uniformly Distributed
問題文を読んだ直後はひどく難しそうに感じる問題だが、実際に解くとそうでもない。小さな具体例をいくつか上げていけば、法則には気づけると思う。
# AtCoder Regular Contest 120 B - Uniformly Distributed
# https://atcoder.jp/contests/arc120/tasks/arc120_b
# tag: グリッド 色塗り 特殊構造 順列・組み合わせ 数え上げ
# 次の 3 x 3 の経路を考えてみる。
# 1 2 3
# 4 5 6
# 7 8 9
# 1 4 7 8 9
# 1 4 5 8 9
# という、一個違いの経路について考慮してみると、
# 5 と 7 は同じ色で無ければならない。
# 同様に、1 4 5 6 9 と 1 2 5 6 9 から
# 2 と 4 も同じ色。
# つまり、右上→左下の方向の斜めに隣り合ったマスは、
# すべて同じ色でなければならない。
# ところで、スタートからの距離をプロットすると
# 斜めの模様になることを考慮すると、上記の場合、
# スタートから同じ距離のマスは全て同じ色になる。
# よって、あらゆる経路は全く同じ色のパターンとなり、
# 条件を満たすことになる。
def main():
H, W = map(int, input().split())
field = [input() for _ in range(H)]
MOD = 998244353
# スタートからの距離別に管理する
# 0: どちらでもいい
# 1: 赤
# 2: 青
# 3: 矛盾
# という感じでビットで色を管理
color_by_dist = [0] * (H+W-1)
for h in range(H):
for w in range(W):
dist = h + w
if field[h][w] == 'R':
color = 1
elif field[h][w] == 'B':
color = 2
else:
color = 0
# 色はビット演算のORを利用して更新する
color_by_dist[dist] |= color
result = 1
# 距離別に見ていく
for d in range(H+W-1):
# 赤と青の両方の色があれば、矛盾なので 0 を
# 返して終了する
if color_by_dist[d] == 3:
print(0)
return
# 色が決定していない時のみ、赤 or 青にできるので、
# 2 を掛ける
elif color_by_dist[d] == 0:
result = (result * 2) % MOD
print(result)
main()
関連
