ABC 404 F — Lost and Pound
分類・前提・執筆情報
掲載状態: 収録済み
Lost and Pound の公式問題ページ(外部リンク)
最終確認:
学習上の位置付け
主題の単元: 確率過程・期待値DP
- 主題
- 確率過程・期待値DP: 意思決定時点で観測済みの情報を状態にし、行動の最適化と確率平均を正しい順序で組み合わせたBellman式を解ける。
- 追加で学ぶ技能
- 既習技能
- 同値な状態を正規化する: 対称操作で同値な状態の標準形と不変量を選べる。
主タグ: 確率・期待値DP
補助タグ: 状態・配置の正規化
執筆: abc-explanation-author1.1.1 / revision 2
学習の位置
体系上の位置: 確率過程・期待値DP
- 意思決定時点で観測済みの情報を状態にし、行動の最適化と確率平均を正しい順序で組み合わせたBellman式を解ける。
先に読む単元:
- 最小十分状態からDPを設計する — 初歩的な一次元DPを土台に、未来を決める情報だけを残す最小十分状態の設計原則を学ぶ。
- 同値な状態を正規化する — 対称な状態を同一視できると探索やDPの状態数を減らせるため、同値類の標準形と不変量を先に定める。
この解説で扱わないこと:
- 二人零和ゲームの勝敗・Grundy数。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る
同じ単元の問題
- ABC266-E — Throwing the Die
- ABC360-E — Random Swaps of Balls
- ABC275-E — Sugoroku 4
- ABC323-E — Playlist
- ABC298-E — Unfair Sugoroku
- ABC326-E — Revenge of "The Salary of AtCoder Inc."
- ABC300-E — Dice Product 3
- ABC350-E — Toward 0
- ABC402-E — Payment Required
- ABC263-E — Sugoroku 3
- ABC382-E — Expansion Packs
- ABC314-E — Roulettes
- ABC333-F — Bomb Game 2
- ABC412-F — Socks 4
- ABC421-E — Yacht
- ABC342-F — Black Jack
- ABC450-G — Random Subtraction
- ABC277-G — Random Walk to Millionaire
- ABC226-H — Random Kth Max
- ABC242-EX — Random Painting
- ABC299-EX — Dice Sum Infinity
- ABC270-EX — add 1