SRM381 Div2 500

とぷこだ 過去問

問題

サイコロを振って、出た目の個数だけキャンディをもらえる。
少なくともキャンディをcandies個だけもらいたい場合、何回サイコロを振る必要があるか。その期待値を返す。

考え方

確率DP。
たとえば、少なくともn個のキャンディを得るための期待値をE[n]とすると、
E[n-1]回から1回振ることで少なくともn個のキャンディを得る場合
E[n-2]回から1回振ることで少なくともn個のキャンディを得る場合
E[n-3]回から1回振ることで少なくともn個のキャンディを得る場合
E[n-4]回から1回振ることで少なくともn個のキャンディを得る場合
E[n-5]回から1回振ることで少なくともn個のキャンディを得る場合
E[n-6]回から1回振ることで少なくともn個のキャンディを得る場合
が等確率でありえるので、
E[n] =
(E[n-1] + 1.0)*(1/6)+
(E[n-2] + 1.0)*(1/6)+
(E[n-3] + 1.0)*(1/6)+
(E[n-4] + 1.0)*(1/6)+
(E[n-5] + 1.0)*(1/6)+
(E[n-6] + 1.0)*(1/6)
で得られる。0個以下を得る期待値は0。