/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 650 点
問題文
長さ N の数列 P=(P_1,P_2,\dots,P_N) が与えられます。高橋君と青木君が、数列 P を使ってゲームを行います。
まず、高橋君が、 1,2,\dots,N から K 個の相異なる整数 x_1,x_2,\dots,x_K を選びます。
次に、青木君が、 1,2,\dots,N から 1 つの整数 y を P_y に比例する確率で選びます。すなわち、整数 y が選ばれる確率は \dfrac{P_y}{\sum_{y'=1}^N P_{y'}} です。そして、青木君が \displaystyle \min_{i=1,2,\dots,K} |x_i-y| のスコアを得ます。
高橋君は、青木君が得るスコアの期待値を最小化したいです。高橋君が適切に x_1,x_2,\dots,x_K を選んだときに、青木君が得るスコアの期待値の最小値を \sum_{y'=1}^N P_{y'} 倍した値を求めてください。なお、出力すべき値は整数になることが証明できます。
制約
- 1 \leq N \leq 5 \times 10^4
- 1 \leq K \leq N
- 0 \leq P_i \leq 10^5
- 1 \leq \sum_{y'=1}^N P_{y'} \leq 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K P_1 P_2 \dots P_N
出力
答えを出力せよ。
入力例 1
5 2 1 1 1 1 1
出力例 1
3
青木君が 1,2,\dots,N を選ぶ確率はすべて等しく \frac{1}{5} です。
高橋君が x_1=2,x_2=4 と選んだとすると、青木君が得るスコアの期待値は 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} = \frac{3}{5} です。
高橋君が x_1=2,x_2=3 と選んだとすると、青木君が得るスコアの期待値は 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 2 \times \frac{1}{5} = \frac{4}{5} です。
高橋君が他の選び方をしても、青木君が得るスコアの期待値は \frac{3}{5} より小さくなりません。よって最小値は \frac{3}{5} であり、これを 5 倍した 3 を出力します。
入力例 2
5 1 0 0 1 0 0
出力例 2
0
入力例 3
1 1 100
出力例 3
0
入力例 4
20 7 4262 9522 2426 3823 7364 964 2743 2423 1955 5274 3684 847 363 35 278 3220 203 2904 6304 1928
出力例 4
22809
Score : 650 points
Problem Statement
You are given a sequence P=(P_1,P_2,\dots,P_N) of length N. Takahashi and Aoki will play a game using the sequence P.
First, Takahashi will choose K distinct integers x_1,x_2,\dots,x_K from 1,2,\dots,N.
Next, Aoki will choose an integer y from 1,2,\dots,N with a probability proportional to P_y. That is, the probability that integer y is chosen is \dfrac{P_y}{\sum_{y'=1}^N P_{y'}}. Then, Aoki's score will be \displaystyle \min_{i=1,2,\dots,K} |x_i-y|.
Takahashi wants to minimize the expected value of Aoki's score. Find the expected value of Aoki's score when Takahashi chooses x_1,x_2,\dots,x_K so that this value is minimized, multiplied by \sum_{y'=1}^N P_{y'}. It is guaranteed that the value to be printed is an integer.
Constraints
- 1 \leq N \leq 5 \times 10^4
- 1 \leq K \leq N
- 0 \leq P_i \leq 10^5
- 1 \leq \sum_{y'=1}^N P_{y'} \leq 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K P_1 P_2 \dots P_N
Output
Print the answer.
Sample Input 1
5 2 1 1 1 1 1
Sample Output 1
3
The probabilities of Aoki choosing 1,2,\dots,N are all equal: \frac{1}{5}.
If Takahashi chooses x_1=2 and x_2=4, then the expected value of Aoki's score will be 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} = \frac{3}{5}.
If Takahashi chooses x_1=2 and x_2=3, then the expected value of Aoki's score will be 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 2 \times \frac{1}{5} = \frac{4}{5}.
No matter how Takahashi chooses, the expected value of Aoki's score cannot be smaller than \frac{3}{5}. Therefore, the minimum value is \frac{3}{5}, so print this value multiplied by 5, which is 3.
Sample Input 2
5 1 0 0 1 0 0
Sample Output 2
0
Sample Input 3
1 1 100
Sample Output 3
0
Sample Input 4
20 7 4262 9522 2426 3823 7364 964 2743 2423 1955 5274 3684 847 363 35 278 3220 203 2904 6304 1928
Sample Output 4
22809