HHKB プログラミングコンテスト 2020 F - Random Max

↓これ

区間を座圧して得られた $O(N)$ 個の区間それぞれに対し, 「その区間に属する変数が $x$ 個で, それ以外の変数がその区間より小さい区間に属する確率」を求めまふ. これは, 変数ごとにその区間に属する確率・それより小さい区間に属する確率を求めたうえでDPしてやれば $x=1,2,...,N$ すべてに対して $O(N^2)$ で求められまふ.

区間 $[ L,R ]$ に $x$ 個の変数があるとき, そのうち最大の値の期待値を求めたいれふ. 1番大きい値, 2番目に大きい値, ...の期待値は, $[ L,R ]$ 内に等間隔で存在しないと偏ってる気がするので, 求める期待値は $L + \frac{(R-L)x}{x+1}$ になる気がしまふ(サンプル1・2を見ると, これで良さそうなのが確認できまふ).

以上の解法で $O(N^3)$ になりまふ. $N \le 1000$ なので不安になるかもしれないれふが, 最大値になりえない区間を除外したり, 現在見ている区間に所属することが無い変数をDPに使わなかったりすることで, 余裕をもってAC出来まふ.

ちゃんと解析すると, 最悪ケースは $(L,R) = (10,20), (10,30), (10,40), ...$ のようなケースになりまふ( $L$ が10未満になるケースがあると区間の個数自体は増えるのれふが, こうして生じた区間は最大値になりえないため影響がないれふ). これらを座圧して得られる区間のうち, $[ 10,20 ]$ は $N$ 個の変数が属する可能性がありまふが, $[ 20,30 ]$ は $N-1$ 個, $[ 30,40 ]$ は $N-2$ 個, ...と減っていきまふ. そのため, 上述の定数倍高速化をしていれば, 合計で $1^2 + 2^2 + ... + N^2 \fallingdotseq \frac{N^3}{3}$ となりまふ.