問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

整数列 $A=(A_1, \dots, A_N)$ がある. $K=1,2, \dots, N$ それぞれに対して以下の問に答えよ.

確率変数 $X,Y$ をそれぞれ $A_1, \dots, A_K$ から一様ランダムに決定する (重複がある場合はその分だけ 2倍, 3倍になる). このとき, $\max (X,Y)$ の期待値を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 2 \times 10^5$

解法1

まず, $K$ を固定して考える. $A_1, \dots, A_K$ を昇順に並び替えた列を $B_1, \dots, B_K$ とする. まず, これらが全て相異る場合, 期待値 $E_K:=E[\max(X,Y) ]$ は,

$\begin{align*} E_K &=E[\max(X,Y) ] \\ &=\sum_{i=1}^K B_i \operatorname{Prob}(\max(X,Y)=B_i) \\ &=\sum_{i=1}^K B_i \operatorname{Prob}(\max(X,Y) \leq B_i \land \lnot \max(X,Y) \lt B_i) \\ &=\sum_{i=1}^K B_i \operatorname{Prob}(X \leq B_i \land Y \leq B_i \land \lnot (X \lt B_i \land Y \lt B_i)) \\ &=\sum_{i=1}^K B_i (\operatorname{Prob}(X \leq B_i \land Y \leq B_i)-\operatorname{Prob}(X \lt B_i \land Y \lt B_i)) \\ &=\sum_{i=1}^K B_i (\operatorname{Prob}(X \leq B_i)\operatorname{Prob}(Y \leq B_i)-\operatorname{Prob}(X \lt B_i )\operatorname{Prob}(Y \lt B_i)) \\ &=\sum_{i=1}^K B_i \left(\dfrac{i}{K} \times \dfrac{i}{K}-\dfrac{i-1}{K} \times \dfrac{i-1}{K} \right) \\ &=\dfrac{1}{K^2} \sum_{i=1}^K B_i \left(i^2-(i-1)^2 \right)\\ &=\dfrac{1}{K^2} \sum_{i=1}^K B_i (2i-1)\\ \end{align*}$

である. ここで, $\displaystyle S_K:=\sum_{i=1}^N B_i (2i-1)$ とし, $S_1, \dots, S_N$ を高速に求める方法を考えることにする.

解放2

$S_0=0$ である. $A_1, \dots, A_K$ を昇順に並び替えた列を $B_1, \dots, B_K$ とし, この中に $A_{K+1}$ 未満の整数が $t$ 個あるとする *1.

このとき,

$\begin{align*} S_{K+1} &=\sum_{i=1}^t B_i (2i-1)+A_{K+1} (2(t+1)-1)+\sum_{i=t+1}^K B_i (2(i+1)-1) \\ &=\sum_{i=1}^t B_i (2i-1)+A_{K+1} (2(t+1)-1)+\sum_{i=t+1}^K B_i (2i-1)+2\sum_{i=t+1}^K B_i \\ &=\sum_{i=1}^K B_i (2i-1)+A_{K+1} (2(t+1)-1)+2\sum_{i=t+1}^K B_i \\ &=S_{K-1}+2 \left((t+1)A_{K+1}+\sum_{i=t+1}^K B_i \right)-A_{K+1} \\ \end{align*}$