ABC 342 F — Black Jack

考察

dealerの最終score分布は戦略と独立なので先に計算できる。playerがscore iで止めた勝率q[i]と、もう一度振る場合の将来最適勝率平均を比較すれば、後ろからoptimal stopping DPになる。

採用する候補: dealer分布をsliding-sum DPで求め、playerを逆順DPする

両者のdice遷移が連続D状態の平均なので、range sumを維持して全体O(N+D)で計算できる。

棄却する候補: playerの全stop/continue戦略をgame treeとして探索する

各scoreで二択、dice分岐D通りが重なり、同じscore状態の再利用をしないと指数的になる。

player score i≤Nで止める勝率はdealer最終yがy<iまたはy>Nとなる確率q[i]である。続行時は一様にi+1,…,i+Dへ移り、N超過stateの勝率0を含むのでr[i]=max(q[i],Σr[i+t]/D)となる。

p[0]=1からdealerがL未満のstateだけを展開し、difference arrayまたはsliding sumで各p[y]を求める。terminal y≥Lのprefix sumから全q[i]を作る。r[j]=0 for j>Nとしてi=N,…,0を走査し、次D個のr平均をwindow sumで得てr[i]を更新し、r[0]を出力する。

典型の発動条件

吸収Markov DP

発動条件: dealerはscoreがL以上になるまで同じdice transitionを繰り返す。

未吸収stateだけから確率を配り、最終score分布をrange-addで集計する。

optimal stopping DP

発動条件: 各stateで即時rewardと一回進めた期待値の大きい方を選べる。

stop勝率qとcontinue平均をmaxし、遷移先scoreが大きい順序で逆算する。

問題固有の要素

dealerのrandomnessを最終分布qへ周辺化してからplayer戦略を解くことで、二者のprocessを一つの巨大状態空間に結合せずに済む。

別の問題へ持ち帰る視点: 相手の固定確率processは先にterminal payoff分布へ畳み込み、意思決定側のBellman方程式へ渡す。

正当性

dealerはscore<Lの状態からだけ続行するので、前向きの確率分布更新で最終score分布を求められる。playerがscore iで止めて勝つのはdealerのscoreがi未満、またはN超過の場合だけである。続行の勝率はi+1..i+Dの最適勝率の平均で、N超過は0とする。scoreが常に増えるためr[i]=max(停止勝率,続行平均)をNから逆順に解く帰納法が成立する。区間和の差分更新と窓平均は同じ確率和を保つので、線形時間の計算も最適停止判断を失わない。

実装上の注意

  • dealerはy≥Lで停止するためpからの遷移を行わない。playerのi>Nは即敗北0で、q[i]を使わない。double誤差を抑えwindow更新の出入りindexを固定する。

復習の核

  • D=1、L=N、playerが即stopする境界、必ずbustするcontinueを、小さい状態の直接連立/再帰計算と比較する。

計算量と制約

時間

O(N+D)、dealer forward差分とplayer backward窓平均。

空間

O(N+D)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All inputs are integers.; 1 \leq L \leq N \leq 2 \times 10^5; 1 \leq D \leq N

出典

分類・前提・執筆情報

掲載状態: 収録済み

Black Jack の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

    主タグ: 確率・期待値DP

    補助タグ: DP遷移の集約・高速化

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題