ABC 333 F — Bomb Game 2
分類・前提・執筆情報
掲載状態: 収録済み
最終確認:
学習上の位置付け
主題の単元: 確率過程・期待値DP
- 主題
- 確率過程・期待値DP: 互いに排反な状態に確率を配り、遷移確率・吸収条件・総確率を保って分布や到達確率を計算できる。
- 追加で学ぶ技能
- 既習技能
- 法上の四則演算・高速累乗・逆元: 剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。
- DP遷移を因数分解・集約して加速する: 隣接する出力の遷移式を比較し、共通項の消去と出入りする項から定数時間更新を導ける。
主タグ: 確率・期待値DP
補助タグ: DP遷移の集約・高速化 法上の四則演算・高速累乗・逆元
執筆: abc-explanation-author1.1.1 / revision 2
学習の位置
体系上の位置: 確率過程・期待値DP
- 互いに排反な状態に確率を配り、遷移確率・吸収条件・総確率を保って分布や到達確率を計算できる。
先に読む単元:
- 最小十分状態からDPを設計する — 初歩的な一次元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
- 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