ABC 226 H — Random Kth Max

考察

K番目に大きい値Yの期待値は、非負変数なので∫P(Y≥x)dxで求められる。各X_iの端点が0から100の整数であるため、単位区間[a,a+1]内ではP(X_i≥x)が定数または一次式になる。

採用する候補: 各単位区間で、x以上となる変数の個数分布を係数がxの多項式であるDPとして作り、少なくともK個となる確率多項式を区間積分する。

順位統計量を直接追わずtail確率へ変えると独立変数の個数DPになり、整数端点により有限個の区間で厳密な多項式積分ができる。

棄却する候補: 乱数サンプリングでK番目の値を多数回生成し、平均を法998244353へ変換する。

要求値は厳密な有理数の剰余であり、近似誤差を持つMonte Carloや数値積分から復元できない。

Y≥x はN個のうち少なくともK個がx以上であることと同値で、独立性から各変数の成功確率p_i(x)を掛けるPoisson-binomial型DPで求められる。

[a,a+1]内でp_i(x)は0、1、(R_i-x)/(R_i-L_i)のいずれかなので、DP値も次数N以下の多項式となり、係数ごとに割って厳密に積分できる。

a=0,…,99ごとに各p_i(x)の一次多項式を作り、成功個数DPを多項式として更新する。j≥Kの多項式を合計して[a,a+1]で積分し、全区間の値を法998244353で加える。

典型の発動条件

tail確率による期待値積分

発動条件: 非負の連続確率変数の期待値を求め、値以上となる事象の方が組合せ的に数えやすいとき。

順位値Yそのものの密度を作らず、E[Y]=∫P(Y≥x)dxを用いて個数条件へ変換する。

区分多項式の確率DP

発動条件: 独立事象の成功確率が区間ごとに低次数多項式となり、成功個数の閾値確率が必要なとき。

成功個数を状態にして一次多項式p_iと1-p_iを掛け、得たtail多項式を係数積分する。

問題固有の要素

全分布の端点が小さい整数なので、連続変数の問題でも積分区間を100個の単位区間へ固定し、各区間を有限多項式計算として扱える。

別の問題へ持ち帰る視点: 連続分布の式が区分的に変わる問題では、全breakpointを列挙し、その間で密度・CDFが何次式になるかを確認する。

正当性

YをK番目に大きい値とするとY≥xは少なくともK個のX_i≥xと同値。独立性により成功数の生成多項式は∏((1−p_i(x))+p_i(x)z)。各単位区間ではp_i(x)が一次以下なので係数DPで正確に構成できる。非負変数の尾積分E[Y]=∫P(Y≥x)dxを各区間へ分割し、次数ごとの積分と総和を取れば期待値を求められる。法では全ての分母が可逆な範囲である。

実装上の注意

  • K番目に大きい値には『x以上が少なくともK個』を使う。区間端点は確率0なので開閉を過剰に分岐せず、積分時の1/(d+1)と各(R_i-L_i)の逆元を前計算する。

復習の核

  • K番目の密度を直接微分する前に、『少なくともK個が閾値以上』というtail事象と、端点間での多項式性を使う。

計算量と制約

時間

値域上限R=100としてO(RN³)。成功数O(N)×多項式次数O(N)×変数N。

空間

O(N²)。区間ごとに多項式DPを作り直す。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 50; 1 \leq K \leq N; 0 \leq L_i \lt R_i \leq 100; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Random Kth Max の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

    主タグ: 確率・期待値DP

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

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題