ABC_350_E "Toward 0"をrubyで解く
入水と緑落ちの反復横跳びがウザすぎる。
今回の問題はこちら。
考察
1が出たら状況が変わらず振り直しのサイコロ
に関する問題が、ABCでは年に一回くらい出ます。例えばこれ。
こういう問題が出た時に「運悪く1が無限に連続した時はどうするのか？」と考えるとドツボです。次の言葉を思い出してください。
1以外が出るまで振り直しのサイコロは、1.2回振れば2から6が確定で出る5面ダイスと(分散を無視し、期待値だけを考えるなら)同値です。
感覚的に納得できない人は、例えば「2の目が出るのに何回振るかの期待値」について考えてみてください。
- 一回振って2の目が出る確率は1/6
- 2回振って1→2と出る確率は(1/6)^2
- 3回振って1→1→2と出る確率は(1/6)^3
- 4回振って1→1→1→2と出る確率は(1/6)^4
- 以下無限に続く
あとは高校数学の授業を思い出して無限級数の和を算出するか、もしくはWolframに問題文を投げれば答えが出ます。
正直これが1番メモしたかったからここ以外はおまけ。(本音)
DP
緑レート以下でDPが得意という人は多分いないと思います(3回目)。ギリギリ水コーダーの私も、今でもコツがあるならこっちが聞きてーよと言いたいです。
しかしほぼ決まっていることがあります。確定済みの状態から未確定の方向に一歩ずつ進めるのであり、前から後ろに一歩ずつ進めるとは限らないという事です。
一般的な配るDPは「開始状態→今の状態が確定済み。今の状態→未来の状態への影響を計算。他の状態からも未来の状態に影響を与えるのでまだ未来の状態は未確定」というアルゴリズムです。
これに対し貰うDPは「開始状態→一段階前の状態が確定済み。今の状態が未確定なので、一段階前の状態→今の状態を計算して確定させる」というアルゴリズムです。
今回は貰うDPの変形です。「現在より一段階先→N=0までの期待値は確定済み。現在→一段階先に必要な期待値を計算して、それに一段階先→N=0の期待値を足して現在→N=0の期待値を確定」という形です。終了状態での期待値(厳密には終了状態から終了状態に遷移するコスト期待値)が確定済み開始状態から終了状態に進むのとは逆に終了時点から戻って開始時点の期待値を計算するわけです。言ってみれば逆貰うDPでしょうか。類題はこちら。
計算すべきNの抽出
Nが20万くらいであれば、全てのNについて計算する事も可能です。
しかし今回のNは1e18とかあります。間違いなくtleしますし、そもそもrubyの配列に収まりません。
そこで計算不要なNがないかを考えます。例えばN=100を計算する場合、直接に必要なNは50,33,25,20,16の5つです。間接的な物を含めても50,33,25,20,16,12,10,8,11,6,5,4,3,2,1,0の16個。残り84個は計算不要なのです。
その必要なNを調べる方法ですが、DFSでリストアップしても構いません。私も本番中はNを/2から/6まで繰り返してstackに入れ、stackからpopした値を/2から/6まで繰り返してstackに入れました。
が、わざわざ必要な値をstackDFSしてからソートしてDPするくらいなら、最初から再帰関数でDPしながらDFSする方が単純です。
つまり今回の問題は、「期待値dp配列をキャッシュとして使う、メモ化再帰関数による再帰DFS問題」です。
疑似コード
- キャッシュ連想配列を用意。N=0の時は支払い期待値0。
- 現在のNを受け取る
- キャッシュが残っている場合は早期リターン
- 「NからN/Aに遷移するのにX円支払い」+「N/Aから0に遷移するのにかかるコスト(未計算なら2にN/Aを渡して再帰)」
- 「1.2*Y円支払って2から6までの5面ダイスを振る」+「N/2から0に遷移するコスト~N/6から0に遷移するコスト(未計算なら再帰を進めて計算)の平均」
- 4と5を比較して安い方が答え。キャッシュして値を返す。
- 2に初期Nを与える
ACコード
wolframの使い方が未だによくわかりません。
Discussion