コンテスト中AC: A〜E

E - Sugoroku 3

期待値DPが使えます。
サイコロを振ることを操作と呼ぶことにします。

マス $i$ からマス $N$ までにかかる操作回数の期待値を $E_i$ とします。

マス $i$ からは、マス $i,\ i+1,\ \cdots ,\ i+A_i$ に行くことができます。
$m = A_i+1$ とおけば、それぞれのマスには $\frac{1}{m}$ の確率で移動します。

また、マス $j$ に辿りつくと、マス $j$ からは(平均して) $E_j$ 回の操作でマス $N$ に行けます。 $i$ から $j$ に行くのに操作を1回行うので、マス $i$ からマス $j$ を経由してマス $N$ に辿りつくには $E_j + 1$ 回の操作が必要になります。

以上から、以下の式が成り立ちます。

$E_i = \frac{1}{m}(E_i + 1) + \frac{1}{m}(E_{i+1} + 1) \cdots + \frac{1}{m}(E_{i+A_i} + 1)$

さて、この式には右辺・左辺の両方に $E_i$ があるので、左辺に移行します。

$\frac{m-1}{m}E_i = \frac{1}{m} + \frac{1}{m}(E_{i+1} + 1) \cdots + \frac{1}{m}(E_{i+A_i} + 1)$

$E_i = \frac{m}{m-1}\{\frac{1}{m} + \frac{1}{m}(E_{i+1} + 1)+ \cdots + \frac{1}{m}(E_{i+A_i} + 1)\}$

この式より、 $E_{i+1}, \cdots ,\ E_{i+A_i}$ が求まっていると $E_i$ が求められます。
同じマスに戻るような場合、一見無限回の試行が必要なように思えますが、このように式変形すると問題なく求められる場合があります。

次に、期待値を求めていきますが、マスの移動先が少なければメモ化再帰等で愚直に求めていくことができます。しかし、今回は移動先が多いため $O(N^2)$ となってしまうので、もう少し工夫する必要があります。

前述の式を更に整理します。

$E_i$
$= \frac{m}{m-1}\{\frac{1}{m} + \frac{1}{m}(E_{i+1} + 1)+ \cdots + \frac{1}{m}(E_{i+A_i} + 1)\}$

$= \frac{1}{m-1}\{1 + (E_{i+1} + 1)+ \cdots + (E_{i+A_i} + 1)\}$

$= \frac{1 + E_{i+1} + 1+ \cdots + E_{i+A_i} + 1}{m-1}$

$= \frac{E_{i+1} + \cdots + E_{i+A_i} + m}{m-1}$

したがって、

$E_i = \frac{E_{i+1} + \cdots + E_{i+A_i} + m}{m-1}$

となります。 $E_{i+1} + \cdots + E_{i+A_i}$ の部分を高速に求められればよく、連続した区間の和なのでFenwick Treeにより $O(logN)$ で求められます。

以上より、 $E_N = 0$ を初期値として、 $i=N-1,\ \cdots ,\ 2,\ 1$ の順に $E_i$ を求めていくことで、
$O(NlogN)$ でこの問題を解くことができます。

(累積和を用いれば計算量が落ちるかもしれません)

geam1113’s diary