ABC 326 E — Revenge of "The Salary of AtCoder Inc."

考察

salary総額は各A_iの支払indicatorの和なので、期待値の線形性によりΣA_i·Pr(A_iが支払われる)で求められる。A_iが支払われる直前のxは0..i-1のいずれかで、各状態jへ到達した後に出目iを1/Nで出すeventは互いに排反である。p_jをstate x=jへ到達してA_jを受け取る確率、p_0=1とするとp_i=(1/N)Σ_{j<i}p_jになる。stateは出目が現在値より大きいときだけ増え、一度訪れたiを再訪しないため、A_iの支払確率とstate iへの到達確率が同じである。Σ_{j<i}p_jをprefとして持てばp_i=pref/N、続いてpref+=p_iと更新するだけでよい。

採用する候補: 各indexへ到達する確率p_iをprefix sumで更新し、A_i p_iを加える。

strictly increasingなstate遷移を1次元確率DPにし、全過去和を累積値1つで線形計算できる。

棄却する候補: die roll列をterminationまで全列挙してsalaryを平均する。

長さは有限でもroll列の分岐数が指数的である。

棄却する候補: 各stepの期待paymentが一定としてexpected step数を掛ける。

現在xにより支払対象となる出目とpayment A_yが変わり、stepごとの分布は同じでない。

mod 998244353でinvN=N^{-1}を求め、pref=p_0=1、answer=0とする。i=1..Nでp_i=pref·invN、answer+=A_i·p_i、pref+=p_iと更新する。最後にanswerを正規化して出力する。

典型の発動条件

indicator期待値

発動条件: random過程中に各rewardが高々一度発生し総額がその和になるとき。

各rewardの発生確率を独立に求めて重み付き加算する。

単調stateの到達確率DP

発動条件: state indexが遷移ごとにstrictly増加し、前状態から同確率で飛ぶとき。

過去到達確率のprefix sumで次stateを計算する。

問題固有の要素

processの終了時刻分布を求めず、各salary項目が一度支払われる確率だけを見ると、停止rollはDP遷移に明示せず自然に確率massから抜ける。

別の問題へ持ち帰る視点: 期待総報酬では過程全体を追うより、各一回限りeventの到達確率へ分解できないか考える。

正当性

次のdiceが現在indexより大きい場合だけ継続するため各indexiへ届く確率は過去全到達確率和/N。訪問indexは厳密増加で各報酬一回なので期待報酬はΣA_i p_i。prefix維持がこの和を厳密に共有する。

実装上の注意

  • p_0=1は実在するpaymentではなく初期state用なのでanswerへA_0を加えない。
  • invNはmodがprimeかつN<modなので存在し、一度だけ計算する。

復習の核

  • N=2で全roll列を短く展開し、p_1=1/2、p_2=(p_0+p_1)/2と停止eventを含む確率が一致するか確認する。

計算量と制約

時間

報酬列長N。累積確率一値で O(N)。

空間

prefix、answerだけ O(1)、入力O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All inputs are integers.; 1 \le N \le 3 \times 10^5; 0 \le A_i < 998244353

出典

分類・前提・執筆情報

掲載状態: 収録済み

Revenge of "The Salary of AtCoder Inc." の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

    主タグ: 確率・期待値DP

    補助タグ: 寄与の数え上げと順序交換 法上の四則演算・高速累乗・逆元

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題