キーエンス プログラミング コンテスト 2021 C - Robot on Grid

問題概要

グリッド上のKマスに'D', 'R', 'X'が書かれていて、

• 'D'ならば下
• 'R'なら右
• 'X'なら右、下両方

にすすめる

あいた$HW-K$のマスに自由に'D', 'R', 'X'を入れる方法($3^{HW-K}$)に対し
$(0, 0)$から$(H-1, W-1)$まで行く行き方をを求めたものの総和を求めたい

$$\sum_{空いたマスの割り当て方} \sum ((0, 0)から(H-1, W-1)に行く行き方)$$

解法

こういう和の和をとるみたいな問題では和のとり方をひっくり返すことで考えやすくなることがある
つまり

$$\sum_{(0, 0)から(H-1, W-1)に行く行き方} \sum (その行き方が可能である空いたマスの割り当て方)$$

と考えても結果は同じになる

これは経路上にあるマスは決まっていて、経路上に存在しないマスは任意に決められるという風に考えられる
各経路に対して、経路上に存在しなかった空白マスの個数をxとすると、
$3^x$個分だけその経路が可能となるマスの割り当て方が出てくる
経路上に存在した空白マスの個数をdpテーブルに持ってdpをすればこれを解くことができる

• $dp[i][j][k]$: 空白マスをk個通ってマス(i, j)に行く行き方
• grid[h][w] == 'D' || grid[h][w] == 'X'のとき
  $dp[h+1][w][k] \mathrel{{+}{=}} dp[h][w][k]$
• grid[h][w] == 'R' || grid[h][w] == 'X'のとき
  $dp[h+1][w][k] \mathrel{{+}{=}} dp[h][w][k]$
• grid[h][w] == ' '(空白)のとき
  $dp[h+1][w][k] \mathrel{{+}{=}} 2*dp[h][w]$('D'として割り当てた場合, 'X'として割り当てた場合)
  $dp[h][w+1][k] \mathrel{{+}{=}} 2*dp[h][w]$

答え: $\sum_{k} dp[H-1][W-1][k] * 3^{HW-K-k}$

しかし、これでは状態数がHWKとなってしまい、
$5000*5000*10000$で間に合わない
上の式を整理する

$3^{HW-K} * \sum_{k} dp[H-1][W-1][k] / 3^k$

つまり空白のマスを通った数だけ3で割っている
これは最後に3で割っているが、空白のマスを使って遷移するたびに3で割っても結局は同じことだとわかる

提出コード

https://atcoder.jp/contests/keyence2021/submissions/19485247