AIで解説 AtCoder攻略　確率・期待値DP

確率・期待値DPページの位置づけ

項目	内容
必修度	標準
学習目安	標準〜発展
前提	DP・浮動小数点
対象問題	30問（推定値あり30問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	2
標準	0〜799	3
標準〜発展	800〜1199	1
発展	1200以上	24
未算出	—	0

確率の状態をDPに保存し、期待値や当選確率を一度ずつ更新します。浮動小数点の誤差、確率の合計、期待値の線形性を使い分けます。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

確率・期待値DPの見分け方

ランダムな操作の結果の確率・平均を求める
同じ状態へ複数の確率が流れ込む
期待値を各選択の寄与へ分解できる

確率・期待値DPの実装前チェック

確率の和が1になるか小さい例で確認する
期待値の単位と初期状態を固定する
誤差許容と法の下の確率を区別する

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC154 D Dice in Line（公式解説）を解きます。サイコロの期待値は(N+1)/2です。長さKの連続区間の期待値を最初に計算し、左右1個ずつ入れ替えるスライドで最大値を探します。

N, K = map(int, input().split())
P = list(map(int, input().split()))
expected = [(value + 1) / 2 for value in P]

window = sum(expected[:K])
answer = window
for right in range(K, N):
    window += expected[right] - expected[right - K]
    answer = max(answer, window)

print(answer)

区間ごとにK個を足し直すとO(NK)ですが、スライド更新ならO(N)時間、O(N)メモリです。

確率・期待値DPの学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC242 A T-shirt	公式解説	得点区間に応じた当選確率を、区間長の比として場合分けして計算する。	-555
ABC407 B P(X or Y)	公式解説	公式Editorialの方針を probability union として整理する。	-397
ABC418 C Flush	公式解説	公式Editorialの方針を flush probability として整理する。	401
ABC154 D Dice in Line	公式解説	各サイコロの期待値(P+1)/2を作り、K個連続区間の和をスライディングウィンドウで最大化する。	485
ABC392 D G. Doubles	公式解説	Count each face on every die and maximize the probability that two chosen dice show the same face.	579

次に解く

問題	公式解説	出題意図	difficulty
ABC194 D Journey	公式解説	Sum N/(N-i) for i=0..N-1, the expected time to discover all people.	1078
ABC266 E H. Throwing the Die	公式解説	サイコロを振る回数ごとの最大値の期待値を漸化式で求める。	1227
ABC417 D G. Takahashi’s Expectation	公式解説	公式Editorialの方針を expectation dp として整理する。	1230
ABC360 E H. Random Swaps of Balls	公式解説	Official editorial intent is classified as random swap probability.	1249
ABC280 E H. Critical Hit	公式解説	DP the probability of reaching N after each critical-hit round, adding 2 or 1 with probabilities and staying at N.	1251

挑戦問題

問題	公式解説	出題意図	difficulty
ABC275 E H. Sugoroku 4	公式解説	Propagate modular probabilities over dice moves, reflecting positions beyond N, and collect the chance of reaching N.	1264
ABC184 D increment of coins	公式解説	Memoize the expected remaining turns for each (a,b,c) coin state and apply the transition probabilities.	1276
ABC323 E H. Playlist	公式解説	Use time DP for the probability that song 1 is playing at X+0.5 seconds.	1279
ABC298 E H. Unfair Sugoroku	公式解説	2人の位置と手番を状態にした確率DPで先にゴールする確率を求める。	1300
ABC326 E H. Revenge of "The Salary of AtCoder Inc."	公式解説	Iterate the salary recurrence and compute the expected final salary.	1363