ふか杯 5th contest E - すごろく

• 問題
• AC

$f(i) :=$ マス$i$からゴールするまでにサイコロを振る回数の期待値、として降順にDPしたいが、振り出しに戻る場合の扱いを考えなくてはならない。

通常、ループを含む確率DPは左辺と右辺の両方に$f(i)$が登場する式が立式できて、$f(i) = ...$となるように整理すると遷移がわかるはずだが、この場合は紙の上で式変形するのは難しそうに見える。そこで、$f(1)$の係数も別にDPで求めることにする。つまり、$f(i) = a(i) + b(i)f(1)$と表して、$a, b$を降順で求める。

$x_i>0$なら

$$a(i) = a(i + x_i)$$ $$b(i) = b(i + x_i)$$

$x_i = 0$なら

$$a(i) = \frac{1}{6}(a(i+1) + ... + a(i+6)) + 1$$ $$b(i) = \frac{1}{6}(b(i+1) + ... + b(i+6))$$

$x_i = -1$なら

$$a(i) = 0$$ $$b(i) = 1$$

これで$a(1), b(1)$が得られるので、答えは$f(1) = a(1)/(1-b(1))$と求まる。