Official

H - Random Kth Max Editorial by Nyaan

この問題は連続確率変数の扱い方を問うている問題です。本題に入る前に、この問題を解くのに必要な知識を簡単にまとめておきます。

確率密度関数と累積分布関数

以下では \(P(\mathrm{cond})\) を「 \(\mathrm{cond}\) である確率」という意味で使います。

確率変数 \(X \)の確率密度関数 \(f(x)\) とは、確率変数がある値をとるという事象の確率密度を表す関数です。これは言い換えると、確率変数がある範囲の値を取る確率を \(f(x)\) の定積分により得られるように定義された関数であり、確率との間には次のような関係式が成り立ちます。

\[P(a\leq X \leq b) = \int_a^b f(x) dx\]

\[\int_{-\infty}^\infty f(x)dx = 1\]

次に、確率変数 \(X\) の累積分布関数 \(F(x)\) は「\(X \leq x\) である確率」の関数であり、次のような式で表せます。

\[\mathrm{P}(X \leq x) = F(x)\]

\[\mathrm{P}(a \lt X \leq b) = F(b) - F(a)\]

今までの定義から、確率密度関数と累積分布関数の間には次の関係式、すなわち「確率密度関数を積分すると累積分布関数になる」という関係が成り立ちます。

\[F(x) = \int_{-\infty}^x f(t)dt\]

また、確率変数 \(X\) が \(a \leq x \leq b\) の範囲の値を取る時、\(f(x),F(x)\) と \(X\) の期待値 \(E[X]\) の関係式は次の式で与えられます。式を観察すると、どちらも変数が離散的な場合の期待値の式と同じ構造をしていることがわかると思います。

\[E[X] = \int_{a}^b xf(x)dx\]

\[E \lbrack X \rbrack = a + \int_{a}^{b} (1 - F(x)) dx \]

(例題) \(m\)番目に大きい数

\([0,1]\) 上の連続一様分布に従う \(n\) 個の確率変数 \(X_1,\ldots,X_n\) のうち \(m\) 番目に大きい数の期待値は？

確率変数 \(X\) が \(x\) 以上である確率は \(1 - x\), 以下である確率は \(x\) であることを利用すると、答えが \(x\) 以上である確率を表す関数 \(\overline{F}(x) := 1 - F(x)\) は

\[\overline{F}(x) = \sum_{i=m}^n \binom{n}{i} (1-x)^i x^{n-i}\]

になります。よって期待値 \(E\) は \(\overline{F}(x)\) を積分して

\[ \begin{aligned} E &= \int_{0}^{1} \left\lbrace \sum_{i=m}^n \binom{n}{i} (1-x)^i x^{n-i} \right\rbrace dx \\ &= \sum_{i=m}^n \binom{n}{i} \int_{0}^{1} (1-x)^i x^{n-i} dx \end{aligned} \]

となります。ベータ関数の積分公式

\[\int_{0}^{1} x^m (1-x)^n dx = \frac{m!n!}{(m+n+1)!}\]

を利用して式変形すると、

\[ \begin{aligned} E &= \sum_{i=m}^n \binom{n}{i} \frac{i!(n-i)!}{(n+1)!} \\ &= \sum_{i=m}^n \frac{1}{n+1} \\ &= 1 - \frac{m}{n+1} \end{aligned} \]

を得ることができました。

本題

以下では簡単のため \(N = \max(R)\) として計算量を表記します。

区間を固定して DP ： \(\mathrm{O}(N^4)\)

必要な区間を \(\lbrack A, A + 1\rbrack\) で固定して考えると、

  • \(dp_{i,j,k}\) : \(i\) 個目まで見て \(A+1\) より大きいものが \(j\) 個、 \(A\) 以上 \(A+1\) 以下のものが \(k\) 個ある確率

という DP で \(\mathrm{O}(N^3)\) で DP を計算することができます。 さらに、DP によって得られた結果は「区間に \(k\) 個あるときの大きい方から \(K - j\) 番目の値の期待値は？」という問題を解くことで求める答えに帰着できて、これは上の例題の答えから \(\mathrm{O}(1)\) で変換できます。
よって全体で \(\mathrm{O}(N^4)\) でこの問題を解くことができました。

累積分布関数を計算・差分更新 : \(\mathrm{O}(N^3)\)

\(X := \mathrm{kthmax}(\lbrace X_1, X_2, \dots,X_N \rbrace)\) とします。\(X\) が \(x\) 以上である確率の累積分布関数 \(F(x)\) を計算していくことを考えましょう。もしこれを計算できれば、 \(F(x)\) を積分すればこの問題を解けるとわかります。

\(F(x)\) は関数 \(F_i(x) :=\) \(X_i\) が \(x\) 以上である確率を使って次のように表せます。

\[F(x) = \sum_{S \subseteq X\lbrace 1,2,\dots,N\rbrace, |S| = K} \prod_{i \in S} F_i(x)\]

また、 \(F(x)\) は \(X_1,\dots,X_N\) の区間の内外に依存するため、区間を \(\lbrack a, a + 1\rbrack\) \((0 \leq a \lt \max(A))\) に分割すると、それぞれの区間内において単純な式で表せます。

よって、すべての区間に対して \(F(x)\) を計算することでこの問題を \(\mathrm{O}(N^4)\) で解くことができます。さらに、\(F(x)\) を適切に差分更新していくことで計算量を \(\mathrm{O}(N^3)\) に改善できます。

分割統治を利用した高速化 : \(\mathrm{O}(N^2 \log ^2 N)\)

上の DP を Taylor Shift などを組み合わせた分割統治を行えば 定数倍の重い \(\mathrm{O}(N^2 \log ^2 N)\) になると思います。

類題

posted:
last update: