ABC 404 F — Lost and Pound

考察

各ターンでボタンは無作為に並べ直され、Takahashi は区別できないため、戦略に影響するのは M 回の押下を各位置へ何回ずつ割り振るかという多重集合だけである。ターン終了時までの当たり押下回数 k が分かるので、残り勝率は (ターン数 t, k) だけの後ろ向き DP で表せ、k≥K は同一の勝利状態へ丸められる。配分 c_1+…+c_N=M を固定すると当たりボタンは各位置に確率 1/N なので、期待勝率は (1/N)Σ_i DP[t+1][min(K,k+c_i)] である。非零のボタン数 n は高々 min(M,N)。正の組成だけの補助 DP''[n][s] と、未使用ボタン (N-n) 個の共通項を組み合わせれば N 次元を消せる。

採用する候補: DP[t][k] を以後の最大勝率とし、各ターンの押下回数配分を正の部分数 n と合計 s の補助 DP で最適化する

正の c_i だけを先頭へ寄せ、未使用 N-n 個の寄与を DP[t+1][k] と分離すれば、N が大きくても n≤M の O(TKM^3) で計算できる。

棄却する候補: N 個の区別されたボタンへの M 回の押し方をすべて列挙する

N^M 通りを生み、ランダム並べ替えにより同値な配分の順序まで重複して調べることになる。

非零のボタン数 n は高々 min(M,N)。

最終ターン後を k≥K なら 1、それ以外 0 で初期化する。各 t,k について h[n][s]=max_{c_1+…+c_n=s,c_i>0}ΣDP[t+1][min(K,k+c_i)] を正の c で更新し、max_n(h[n][M]+(N-n)DP[t+1][k])/N を DP[t][k] とする。

典型の発動条件

有限期間ゲーム DP

発動条件: 各ラウンド後に十分統計量が観測され、その後の最適戦略を状態から選べるとき。

ターンと累積当たり回数を状態にして、将来勝率を後ろから最大化する。

対称性による次元削減

発動条件: 対象を区別できず、ランダムな特別対象が一様に選ばれるとき。

ボタン番号の順序を捨て、押下回数の正の部分と未使用数だけを数える。

整数組成 DP

発動条件: 固定和を正の整数へ分けたときの寄与和を最適化したいとき。

使用ボタン数 n と割当済み押下数 s を状態にして次の正の c を列挙する。

問題固有の要素

巨大な N は遷移の選択肢数ではなく、押さないボタンの同一寄与 (N-n) 倍としてだけ残る。

別の問題へ持ち帰る視点: 対称な多数対象への資源配分では、資源量 M が小さければ非零対象数を M 以下へ圧縮し、零対象を一括計上する。

正当性

並べ替え後の当たり位置は N 箇所で一様で、押下中に新情報は得られない。同じ位置を c 回押せば当たりなら回数が c 増え、外れなら不変。従って各位置の押下数だけが一ターンの遷移分布を決める。n個の正押下数を合計Mで割り当てた期待値は、各位置の次ターン勝率の和をNで割ったもの。h[n][s]の加算 knapsack は全正分割を網羅し、未押下N−n箇所の寄与を足す。有限ターンの後退帰納法で最適戦略となる。

実装上の注意

  • k+c は K で clamp し、確率は double など十分な精度で保持する。n≤min(M,N)、s≥n の範囲と、T ターン終了直後の基底条件を揃える。

復習の核

  • N=1、M≥K、T=1、K>TM の勝率 0、全ボタンを一度ずつ押せる場合を手計算し、補助 DP の n と未使用項を確認する。

計算量と制約

時間

T ターン、必要当たり K、一ターン M 押下、B=min(N,M)。各(t,k)で正分割 knapsack O(BM²)、全体 O(TKBM²)。

空間

次ターン勝率 O(K)、一状態の割当 knapsack O(BM)、rolling で O(K+BM)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \le N \le 2\times 10^5; 1 \le T \le 30; 1 \le M \le 30; 1 \le K \le 30; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Lost and Pound の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

    主タグ: 確率・期待値DP

    補助タグ: 状態・配置の正規化

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題