キーエンス プログラミング コンテスト2021 C - Robot on Grid (500)
そのパスを通る方法が何通りあるかを考えたい
スタート地点では$ 3^{HW-K}
他のマスは上の行から順に右方向に以下のように左右それぞれDPする
一つ前のマスが文字が既に決まっていて、このマスに到達可能なら値をそのまま足す
一つ前のマスが文字が既に決まっていて、このマスに到達不可能なら足さない
文字が決まっていない場合、RDXの3種類の内2種類で到達可能なので$ \frac{2}{3} をかけて足す
$ \mod 998244353での$ \frac{2}{3}を計算量削減のために先に求めて置いた
コンテスト中は$ H \times Wのだとメモリ使用量と時間が不安だったので$ 2 \times Wの配列にしたが$ W要素の一次元配列でも求まる
最後のHWマスの値が答え
全てのマスを探索してそれぞれのマスは$ O(1)なので全体では$ O(HW)