ABC 266 E — Throwing the Die

考察

続行を選ぶと過去の出目は最終scoreに残らないため、将来の最適期待値は残りturn数だけで決まる。現在の出目xを見た後は、今終了してxを得るか、残りturnの最適期待値を得るかの大きい方を選べる。最適方策は出目xが継続価値f(n−1)以上なら終了し、未満なら続行するthreshold ruleになる。

棄却する候補: 全ての出目履歴と各時点の終了・続行判断を決定木として列挙する。

履歴数が6^Nに増える一方、過去履歴は続行後の価値へ影響しない。

採用する候補: f(n)を残りn回での最適期待値とし、f(n)=Σ_{x=1}^6 max(x,f(n−1))/6 を小さいnから計算する。

出目を観測した後の最適行動を各xで独立に選び、その条件付き価値を平均すればよい。

有限期限optimal stoppingをBellman value iterationにし、観測後のstop payoffとcontinuation valueの最大を取る。

典型の発動条件

有限期限の最適停止DP

発動条件: 各stepで確率結果を観測してから終了か続行を選び、期限が固定されているとき。

残りstep数の価値を状態にし、各観測結果で即時報酬と継続価値の最大を平均する。

問題固有の要素

N=1では強制終了なのでf(1)=3.5となり、同じ漸化式をf(0)=0から始めてもこの基底を自然に得られる。

別の問題へ持ち帰る視点: 期限付き停止問題は残り0stepの継続価値を定義すると基底と遷移を統一できる。

正当性

出目xを見た後、停止価値xと残り試行の最適期待値fの最大を選べる。各出目の条件付き最適を平均すれば一回追加した最適期待値。最終一回の平均3.5から試行数の帰納法で正しい。

実装上の注意

  • doubleでN回更新し、各回で1から6までのmaxを加えて6で割る。
  • 十分な小数桁を出力して絶対・相対誤差10^{-6}を満たす。

復習の核

  • 最適停止では、続行後に過去情報が残るかを確認し、残らないなら残り期限だけへ状態を圧縮する。
  • 判断が確率結果の観測後なら、期待値を取る前に各結果でmaxを取る順序を守る。

計算量と制約

時間

再抽選上限N、dice6面。Bellman更新 O(6N)=O(N)。

空間

直前期待値 O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 100

出典

分類・前提・執筆情報

掲載状態: 収録済み

Throwing the Die の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 確率過程・期待値DP

主題
  • 確率過程・期待値DP: 意思決定時点で観測済みの情報を状態にし、行動の最適化と確率平均を正しい順序で組み合わせたBellman式を解ける。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 確率・期待値DP

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 確率過程・期待値DP

      • 意思決定時点で観測済みの情報を状態にし、行動の最適化と確率平均を正しい順序で組み合わせたBellman式を解ける。

      先に読む単元:

      この解説で扱わないこと:

      • 二人零和ゲームの勝敗・Grundy数。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題