ABC 382 E — Expansion Packs
分類・前提・執筆情報
掲載状態: 収録済み
Expansion Packs の公式問題ページ(外部リンク)
最終確認:
学習上の位置付け
主題の単元: 確率過程・期待値DP
- 主題
- 確率過程・期待値DP: 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。
- 追加で学ぶ技能
- 既習技能
- 資源・容量DP: 資源軸の上限と更新順を選び、選択の重複を避けられる。
主タグ: 確率・期待値DP
補助タグ: 資源軸knapsack DP
執筆: abc-explanation-author1.1.1 / revision 2
学習の位置
体系上の位置: 確率過程・期待値DP
- 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。
先に読む単元:
- 最小十分状態からDPを設計する — 初歩的な一次元DPを土台に、未来を決める情報だけを残す最小十分状態の設計原則を学ぶ。
- 資源・容量DP — 最小十分状態を設計できるようになった後、選択数・容量・費用などの資源軸で遷移を表し、0/1選択と無制限選択の更新方向を区別する。
この解説で扱わないこと:
- 二人零和ゲームの勝敗・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
- ABC314-E — Roulettes
- ABC333-F — Bomb Game 2
- ABC412-F — Socks 4
- ABC421-E — Yacht
- ABC342-F — Black Jack
- ABC404-F — Lost and Pound
- 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