ABC266 E - Throwing the Die (500)
後ろから考える
最後の1回の期待値は1から6の平均なので3.5
それ以前では以下を順に考える
そのタイミングでゲームを終了することを選択するというのは今の出目が次の期待値以上ということ
$ i
回目の期待値を
$ E(i)
とすると
$ E(i) = \frac{6 - 期待値以上の出目の個数}{6} E(i+1) + \frac{期待値以上の出目の和}{6}
順々に一つ前の結果を用いて計算できるので
$ \mathcal{O}(N)
問題:
https://atcoder.jp/contests/abc266/tasks/abc266_e
提出:
https://atcoder.jp/contests/abc266/submissions/34385808
#ABC266
#500pt
#E
#ABC
#AtCoder
#期待値DP