yukicoder No.75 回数の期待値の問題
解説ACしてから理解しようとしたら辛かった
https://yukicoder.me/problems/no/75
https://yukicoder.me/submissions/285676
問題概要
- さいころを振って，でた目を累積する．これを1手とする．
- 累積値がKになったら終了．超えたら0にリセットする．
手数の期待値を求めたい．
キーワード
巡回するDP
おすすめ解説サイト
yukicoder No.75 - 回数の期待値の問題 - ゲームにっき（仮）別館（仮）
典型力高すぎてちょっと分からない
因幡めぐる@競技プログラミング(@meguru_comp)/「【yukicoder No.75】」の検索結果 - Twilog
重要な気づき
0
俺たちは雰囲気で確率DPをやっていた…
1
DP[i] を累積値をiにするために必要な手数の期待値とする．
DP[i] = (DP[i-1]+1)/6 + (DP[i-2]+1)/6 + (DP[i-3]+1)/6 + (DP[i-4]+1)/6 + (DP[i-5]+1)/6 + (DP[i-6]+1)/6 が成立する．
雑な説明：1の目が出て累積値がiになったとする．このときの手数は，累積値がi-1の時の手数+1．この事象は1/6で起きる．
2
「超えたら0にリセット」を表現したい．
DP[i<0] = DP[K] と置いて計算できるらしいが，初見で理解できず．
2.1
DP[0]，つまり累積値を0にするために必要な手数は，既にゴールに立っているので 0．
サイコロを振っていくと，iは減っていく．DP[K]がスタート地点で，DP[0]がゴール．
ここから，DP[i<0] は，ゴールを超えてしまった時の手数について記述すれば良さそう．
ゴールを超えてしまった時の手数は，累積値をリセットしてもう一度Kまで稼ぐ必要があるので，DP[K]の手数が必要．
よって，DP[i<0] = DP[K]．
3
変なところにも DP[K] があるので，単純な方法で DP[K] を求めることは難しい．
DP[K] を決め打ちして，二分法で解くのが楽．
3
また雰囲気でDPを理解してしまった…
