No.75

それまでに出た目の合計が $x$ のとき, そこからちょうど $K$ に達するためにふるサイコロの回数の期待値を $E(x)$ とする. このとき,

$$E(x) = \sum_{d=1}^6 1/6 \cdot E(x+d) + 1$$

s.t.

$$E(K) = 0, \ \forall a \gt K, E(a) = E(0)$$

となる.

$\forall a > K, E(a) = m$ と置いて $E(K-1)$ から $E(K-2), E(K-3), \dots$ を順に計算していき, この結果得られた $E(0)$ と $m$ の差が誤差範囲に収まるよう, 二分探索で $m$ を探索する.