ABC 295 E — Kth Number

考察

K番目の値Xの期待値はΣ_(x=1)^M Pr[X≥x]であり、閾値ごとなら0の置換成功数だけを数えればよい。

採用する候補: 閾値ごとの二項分布計数

棄却する候補: 全M^zero通りの置換を列挙

0が最大2000個あり指数的。

x=1..Mを走査し、既知の≥x個数を更新しながら、0の成功数が不足分以上となる確率を二項係数と冪で合計して期待値へ加える。

計算するtailを明示する。0の個数をz、既知値でx以上の個数をC_x、r_x=N+1−K−C_xとする。p=(M−x+1)/M、q=(x−1)/Mなら

Pr[X≥x] = Σ_{t=max(0,r_x)}^z C(z,t) p^t q^(z−t)

で、r_x>zなら0、r_x≤0なら1。法998244353でMの逆元を一度計算し、factorial・inverse factorialからC(z,t)を定数時間で求める。各xでpowerP[0]=powerQ[0]=1からz回掛けて全冪を作り、上式を走査する。p=1,q=0でも0^0は空積1として正しく評価できる。各項で高速累乗をやり直すとO(MN log N)になるので、O(MN)の本文ではこの冪表を使う。

既知値の頻度prefixからC_xを求めれば各閾値の不足数も定数時間で更新できる。z=0なら分布はt=0だけで、元列のK番目へ期待値が戻る。閾値ごとO(z+1)、全体O(N+M(z+1))⊆O(MN)。

典型の発動条件

tail-sum formula

発動条件: 有限非負整数値確率変数の期待値を求める。

E[X]=ΣPr[X≥x]へ変換する。

二項分布

発動条件: 同一確率の独立な0置換の成功数を数える。

閾値以上へ置換される個数のtailを計算する。

問題固有の要素

順序統計量そのものの分布より、各閾値を越えるために必要な成功個数の方が単純になる。

別の問題へ持ち帰る視点: 期待順位値は閾値確率へ分解する。

正当性

0一個がx以上になる確率は(M-x+1)/Mで独立なので、必要成功数以上のbinomial tailになる。 固定x以上の既知要素数と0個数から、少なくともN+1-K個がx以上となる確率を二項係数和で求められる。

実装上の注意

  • K番目が昇順であるため必要な≥x個数はN+1-K。確率の分母M^zeroを法逆元で扱う。

復習の核

  • 小N,Mの全置換と比較し、0なし、全0、K=1,N、閾値不足が0以下の例を確認する。

計算量と制約

時間

O(MN)、各thresholdで零位置成功数のbinomial tail、階乗前計算O(N)。

空間

O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1\leq K \leq N \leq 2000; 1\leq M \leq 2000; 0\leq A_i \leq M; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 寄与の数え上げと順序交換

    補助タグ: 組合せ係数・数え上げ 法上の四則演算・高速累乗・逆元

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

    学習の位置

    体系上の位置: 局所寄与へ分解して集計順を交換する

    • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

    先に読む単元:

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

    • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題