HHKB プログラミングコンテスト 2020 F - Random Max の類題です。 Random Max の解説 と同様に区間\([P, Q)\)に分割するアプローチで解いてみます。

多項式関数の動的計画法

\(i\) 番目の確率変数までで確率変数の値が \(x\) 以下となるものが \(k\) 個以上となる確率の密度関数を \(f_{i,k}(x)\) とします。

あきらかに\(f_{i,0}(x) = 1\) が成り立ちます。

確率密度関数 \(f\) は以下のような動的計画法で求められます。

\(Q \le L_i\) の場合

\(X_i\) が \([0, Q)\) の値になることはないので、

\[f_{i,k}(x)=f_{i-1,k}(x)\]

\(R_i \le P\) の場合

\(X_i\) は常に \([0, P]\) の値になるので

\[f_{i,k}(x)=f_{i-1,k-1}(x)\]

その他の場合

条件を満たすのは

• \(X_{i-1}\) までで \(x\) 以下が \(k\) 個以上ある場合
• \(X_i\) が \(x\) 以下であり、\(X_{i-1}\) までで \(x\) 以下がちょうど \(k-1\) 個ある場合

のいずれかです。

\[ \{X_{i-1} までで x 以下がちょうど k-1 個ある確率の密度関数\} = f_{i-1,k-1}(x)-f_{i-1,k}(x) \]

であるため、

\[f_{i,k}(x)=f_{i-1,k}(x)+\frac{x-L_i}{R_i-L_i}\Big(f_{i-1,k-1}(x)-f_{i-1,k}(x)\Big)\]

解法

あとは Random Max の解説 と同様に

\[\sum \int_P^Q xf_{N, N-K+1}'(x) dx \]

です。

\(x\) 以下になる確率と定義したので小さい方から \(N-K+1\) 番目となることに注意してください。

区間が\(O(N)\) 、動的計画法が \(O(N^3)\) なので \(O(N^4)\) で解けました。

提出例(C#): https://atcoder.jp/contests/abc226/submissions/31473003