確率・期待値DP
確率遷移に対する期待値・分布・到達確率の再帰式を解く。
この典型を扱う単元: 確率過程・期待値DP
検索別名: Markov DP、stochastic dynamic programming、期待値DP、確率DP
未知問からこの典型を見つける手掛かり
- 扱う対象
- ランダム
- 分布
- 期待値
- 確率
- 使う手掛かり
- 期待値の線形性
- 等確率
- 遷移確率
- 保つ不変量
- 吸収
- 期待回数
- 確率分布
- 求めるもの
- 分布
- 期待値
- 確率
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
学習成果と学習単位
意思決定時点で観測済みの情報を状態にし、行動の最適化と確率平均を正しい順序で組み合わせたBellman式を解ける。
確率過程・期待値DPで学ぶ互いに排反な状態に確率を配り、遷移確率・吸収条件・総確率を保って分布や到達確率を計算できる。
確率過程・期待値DPで学ぶ状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。
確率過程・期待値DPで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC266 E「Throwing the Die」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC298 E「Unfair Sugoroku」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC226 H「Random Kth Max」 公式問題主題: 確率過程・期待値DP / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC226 H「Random Kth Max」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC239 Ex「Dice Product 2」 公式問題主題: 整数境界と同値区間を正確に分ける / 補助タグ
- ABC242 Ex「Random Painting」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC249 Ex「Dye Color」 公式問題主題: 期待値の頻度圧縮と加法的ポテンシャル / 補助タグ
- ABC263 E「Sugoroku 3」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC266 E「Throwing the Die」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC270 Ex「add 1」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC271 G「Access Counter」 公式問題主題: 固定線形遷移を巨大回数進める / 補助タグ
- ABC275 E「Sugoroku 4」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC277 G「Random Walk to Millionaire」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC280 E「Critical Hit」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC298 E「Unfair Sugoroku」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC299 Ex「Dice Sum Infinity」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC300 E「Dice Product 3」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC310 F「Make 10 Again」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC314 E「Roulettes」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC323 E「Playlist」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC326 E「Revenge of "The Salary of AtCoder Inc."」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC333 F「Bomb Game 2」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC342 F「Black Jack」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC350 E「Toward 0」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC360 E「Random Swaps of Balls」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC382 E「Expansion Packs」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC402 E「Payment Required」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC404 F「Lost and Pound」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC409 G「Accumulation of Wealth」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 補助タグ
技能・出典
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、確率・期待値DP
- ABC412 F「Socks 4」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC421 E「Yacht」 公式問題主題: 確率過程・期待値DP / 主タグ
- ABC450 G「Random Subtraction」 公式問題主題: 確率過程・期待値DP / 主タグ