問題

体力が $H$ のモンスターがいる.

このモンスターに1回攻撃すると, $P$ % の確率で体力が $2$ 減り, $(100-P)$ % の確率で体力が $1$ 減ることのどちらか一方のみが起こる.

モンスターの体力が $0$ 以下になるまでに行う攻撃回数の期待値を求めよ.

動的計画法で解くことにする. $H=-1,0,1,2, \dots, N$ に対して, ${\rm DP}[H]$ を以下で定義する.

ベースケースとして, ${\rm DP}[-1]={\rm DP}[0]=0$ である.

更新式について, $H \geq 1$ とする. このとき, 1回攻撃を行うと, 次のようになる.

このことから,

${\rm DP}[H]=\dfrac{P}{100} {\rm DP}[H-2]+ \left(1- \dfrac{P}{100} \right) {\rm DP}[H-1]+1$

となることがわかった.

この更新式によって, 最終的な解答は ${\rm DP}[N]$ であり, 上の更新式を用いることによって, $O(N)$ 時間で求めることができた.

Kazun の競プロ記録