103556: [Atcoder]ABC355 G - Baseball
Description
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
Output
问题描述
给定一个长度为 $N$ 的序列 $P=(P_1,P_2,\dots,P_N)$。Takahashi 和 Aoki 将使用序列 $P$ 进行游戏。
首先,Takahashi 从 $1,2,\dots,N$ 中选择 $K$ 个不同的整数 $x_1,x_2,\dots,x_K$。
接着,Aoki 将以 $P_y$ 与 $\sum_{y'=1}^N P_{y'}$ 的比例选择一个整数 $y$。即,选择 $y$ 的概率为 $\dfrac{P_y}{\sum_{y'=1}^N P_{y'}}$。然后,Aoki 的分数将是 $\displaystyle \min_{i=1,2,\dots,K} |x_i-y|$。
Takahashi 想要**最小化** Aoki 分数的期望值。找出当 Takahashi 选择 $x_1,x_2,\dots,x_K$ 以使该值最小化时,Aoki 分数的期望值乘以 $\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
Aoki 选择 $1,2,\dots,N$ 的概率都相等:$\frac{1}{5}$。
如果 Takahashi 选择 $x_1=2$ 和 $x_2=4$,那么 Aoki 分数的期望值将是 $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}$。
如果 Takahashi 选择 $x_1=2$ 和 $x_2=3$,那么 Aoki 分数的期望值将是 $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}$。
无论 Takahashi 如何选择,Aoki 分数的期望值都无法小于 $\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