ABC 323 E — Playlist

考察

曲の切替時刻は全て整数なので、X+0.5時点で曲1が流れているなら、その開始時刻tはmax(0,X-T_1+1)≤t≤Xのいずれかである。p[t]を時刻tに新しい曲が始まる確率とすると、その時刻に曲1が選ばれる確率はp[t]/Nで、開始時刻別のeventは排反である。時刻tに切り替わる直前の曲kはt-T_kに始まったので、p[t]=(1/N)Σ_k p[t-T_k]というrenewal DPになる。p[0]=1は時刻0に必ず最初の曲を選ぶeventを表し、負時刻のpを0とすれば同じ漸化式で境界を扱える。X+0.5を使うことで整数時刻ちょうどの曲終了境界を避け、開始tの曲1が有効な条件をt+T_1≥X+1と整数式にできる。

採用する候補: 切替確率p[0..X]をDPし、曲1がX+0.5を覆う開始時刻の確率を合計する。

ランダムな無限playlistを有限な時刻Xまでのrenewal過程として正確に集約できる。

棄却する候補: 曲選択列を深さXまで全列挙し、該当列の確率を足す。

各切替でN分岐し、曲長によって深さも変わるため指数的になる。

棄却する候補: 時刻Xで最後に選ばれた曲だけを状態にするMarkov chain。

次の切替までの残り再生時間が必要で、曲番号だけでは状態が足りない。

invN=N^{-1} mod 998244353を一度求め、p[0]=1とする。t=1..Xでsum=Σ_{k:T_k≤t}p[t-T_k]を計算しp[t]=sum·invNとする。l=max(0,X-T_1+1)からXまでのp[t]を足し、さらにinvNを掛けて曲1が選ばれる確率として出力する。

典型の発動条件

renewal時刻DP

発動条件: 独立に選ぶdurationのtaskを切れ目なく繰り返し、特定時刻の状態を問うとき。

各整数時刻に新しいtaskが始まる確率をduration別に遡って足す。

排反な開始時刻分解

発動条件: 観測時点を覆うinterval eventを数えるとき。

対象taskの開始可能時刻ごとの確率を合計する。

問題固有の要素

再生中の曲を直接時刻DPする代わりに、全曲共通の「切替が起きる確率」を先に求めると、曲1固有の条件は最後の窓和だけになる。

別の問題へ持ち帰る視点: semi-Markovな過程では、状態の残り時間を持つ代わりにrenewal eventの時刻分布をDPすると簡潔になる。

正当性

曲終了時刻tの確率は各曲が開始したt−T_i確率の1/N倍の和。曲1が時刻Xに演奏中なのは開始tがX−T1<t≤Xという互いに排他的な事象だから、その開始確率和へ選曲1/Nを掛ける。境界の終了時刻は演奏中でない。

実装上の注意

  • invNを内側loopで毎回pow計算せず一度だけ求め、各p[t]の和へ掛ける。
  • T_1>X+1ならlower boundは0で、負indexのpを参照しない。

復習の核

  • X=0とT_1=1の境界で開始時刻0だけが寄与すること、長い曲では窓が0までclipされることをtimelineで確認する。

計算量と制約

時間

曲N、時刻上限X。開始確率DP O(NX)。

空間

曲長O(N)、時刻確率O(X)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N\leq 10^3; 0 \leq X\leq 10^4; 1 \leq T_i\leq 10^4; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Playlist の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 確率過程・期待値DP

主題
  • 確率過程・期待値DP: 互いに排反な状態に確率を配り、遷移確率・吸収条件・総確率を保って分布や到達確率を計算できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 確率・期待値DP

    補助タグ: 法上の四則演算・高速累乗・逆元

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 確率過程・期待値DP

    • 互いに排反な状態に確率を配り、遷移確率・吸収条件・総確率を保って分布や到達確率を計算できる。

    先に読む単元:

    この解説で扱わないこと:

    • 二人零和ゲームの勝敗・Grundy数。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題