No.463

魔法を使えない状態でマス $i$ にいるとき, ゴールまでに失うお金の期待値を $E(i)$ とすると,

$$E(i) = \sum_{j=1}^m \frac{ E(i+j) + c_{i+j} }{m}$$

となる. ただし, $E(n) = 0$, $E(n+k) = E(n-k)$ である.

これを $i = 1, 2, \dots, n-1$ について考えると, $n-1$ 本の連立方程式ができるので, これをガウスの消去法などで解く.

次に魔法を1回使える状態でマス $i$ にいるとき, ゴールまでに失うお金の期待値を $F(i)$ とすると,

$$F(i) = \min\left( \min_{j=1,2,\dots,m} (E(i+j) + c_{i+j}), \sum_{j=1}^m \frac{ F(i+j) + c_{i+j} }{m} \right)$$

となる. $i + m \geq n$ のときは明らかに $F(i) = 0$ となるので, あとは $i$ を後ろから計算していけばいい.