ABC 242 Ex — Random Painting
分類・前提・執筆情報
掲載状態: 収録済み
Random Painting の公式問題ページ(外部リンク)
最終確認:
学習上の位置付け
主題の単元: 確率過程・期待値DP
- 主題
- 確率過程・期待値DP: 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。
- 追加で学ぶ技能
- 既習技能
- 法上の四則演算・高速累乗・逆元: 剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。
- 列・subsequence DP: 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。
- 組合せ係数と対称性で数える: 選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。
主タグ: 確率・期待値DP
執筆: abc-explanation-author1.1.1 / revision 2
学習の位置
体系上の位置: 確率過程・期待値DP
- 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。
先に読む単元:
- 組合せ係数と対称性で数える — 選び方を通常・Gaussian二項係数で整理し、必要ならStirling変換でrank別計数を基底変換する。
- 列・subsequence DP — DPの最小十分状態で得た考え方と実装を再利用し、列・subsequence 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
- ABC404-F — Lost and Pound
- ABC450-G — Random Subtraction
- ABC277-G — Random Walk to Millionaire
- ABC226-H — Random Kth Max
- ABC299-EX — Dice Sum Infinity
- ABC270-EX — add 1