Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 275 E問題 Sugoroku 4

AtCoder ABC275 ABC E問題 500 pts

問題

提出解答

問題の概要

$(N+1)$ 個のマスがあり, 各マスにはマス $0$ , マス $1, \dots$ , マス $N$ と名付けられている.

最初, コマはマス $0$ にある. ルーレットで $1,2, \dots, M$ から等確率で1つの整数を決定し, その数だけコマを進める. ただし, マス $N$ をオーバーした場合はそのオーバーした分だけマスを戻らなくてはならない.

コマがマス $N$ に到達した場合, ゴールとなりゲームを終了する.

$K$ 回以内のコマの移動でゴールできる確率を求めよ.

制約

$M \leq N \leq 1000$
$1 \leq M \leq 10$
$1 \leq K \leq 1000$

解法

次のルールを追加する.

ゴールした後も $K$ 回目になるまでルーレットを回す. ただし, 移動はしない.

これにより, $K$ 回目の移動終了後にマス $N$ にいる確率を求めることに帰着される.

動的計画法で考える. ${\rm DP}[i,x]$ を次のように定める.

$i$ 回目の移動終了後にマス $x$ にいる確率.

ベースケースは $i=0$ の場合で,

${\rm DP}[0,x]=\begin{cases} 1 & (x=0) \\ 0 & (x \neq 0) \end{cases}$

である.

ここで, $\operatorname{visit}(x,a)$ で, 現在 $x$ にいるときにルーレットで $a$ が出た場合の移動先のマスとする. これは上記の追加ルールも考慮することによって, 次のようになる.

$\operatorname{visit}(x,a)=\begin{cases} N & (x=N) \\ N-(x+a-N) & (x \neq N, x+a \gt N) \\ x+a & ({\rm otherwise}) \end{cases}$

更新式も次のようにして配るDPの要領で更新すればよい.

${\rm DP}[i, \operatorname{visit}(x,a) ] \xleftarrow{{\rm add}} {\rm DP}[i-1, x] \quad (0 \leq x \leq N, 1 \leq a \leq M)$

これにより, ${\rm DP}[K,N]$ が求めるべき解答になる. 計算量は $O(NMK)$ 時間である.