No.016 D

※ コードは WA が取れていない

ある海域 $k$ に体力 $h$ でいるときに, ゴールまでたどり着くまでの時間の期待値を $E(k, h)$ とする. また, 海域 $k$ から行くことができる海域の集合を $K$ とする.

まずは海域 $k$ に体力 $h$ でいるときに撤退しなければならないかどうかを $T(k, h)$ として, 以下の方法で調べる.

• $k = N$ ならば撤退しない.
• $K$ の要素について $h$ 以上の $D_i$ となる $i$ が存在するならば撤退しなければならない.
• $K$ の要素すべてについて $T(i, h-D_i)$ が true ならば撤退しなければならない.

$T(1, H)$ が true であるならば, ゴールにはたどり着けない.

さて, $E(k, h)$ であるが, 海域 $k$ に体力 $h$ でいるときに撤退しなければならない場合は,

$$E(k, h) = H-h + E(1, H) + 1$$

となる. そうでないときは,

$$E(k, h) = \min\left( \frac{1}{\vert K \vert} \sum_{i \in K} E(i, h-D_i), H-h+E(1, H) \right) + 1$$

となる. これを再帰的に計算して $E(1, H)$ を求めればいいのだが, このままでは無限ループしてしまう.

そこで, 右辺の $E(1, H)$ を $x$ とおいて, 左辺の $E(1, H)$ を計算してみる. $x$ が真の値より大きければ, 計算した $E(1, H)$ は $x$ より小さくなるので, この情報をもとに二分探索で $x$ を決定する.