/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 525 点
問題文
AtCoder 社は、オンラインショップでグッズを販売しています。
今、N 個のグッズが社内に残っています。 ここで、i (1\leq i\leq N) 個目のグッズの重さは W_i です。
高橋君は残ったグッズをまとめて D 袋の福袋として販売する事にしました。
高橋君は各福袋に入ったグッズの重さの合計の分散を最小にしたいと考えています。
ここで、各福袋に入ったグッズの重さの合計がそれぞれ x_1,x_2,\ldots,x_D であるとき、
それらの平均を \bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D) として、
分散は V=\frac{1}{D}\displaystyle\sum_{i=1}^D (x_i-\bar{x})^2 として定義されます。
各福袋に入ったグッズの重さの合計の分散が最小になるようにグッズを分けた時の分散の値を求めてください。
ただし、空の福袋が存在してもかまいません（この時福袋に入ったグッズの重さの合計は 0 として定義されます）が、
どのグッズも D 袋のうちちょうど 1 つの福袋に入っている ようにするものとします。
制約
- 2 \leq D\leq N\leq 15
- 1 \leq W_i\leq 10^8
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D W_1 W_2 \ldots W_N
出力
各福袋に入ったグッズの重さの合計の分散が最小になるようにグッズを分けた時の分散の値を出力せよ。
出力は、真の値との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。
入力例 1
5 3 3 5 3 6 3
出力例 1
0.888888888888889
1 つめの福袋に 1,3 個目のグッズを、
2 つめの福袋に 2,5 個目のグッズを、
3 つめの福袋に 4 個目のグッズを入れると、
それぞれの福袋に入ったグッズの重さの合計は 6,8,6 となります。
このとき、重さの平均は \frac{1}{3}(6+8+6)=\frac{20}{3} であり、
分散は
\frac{1}{3}\left\{\left(6-\frac{20}{3}\right)^2+\left(8-\frac{20}{3}\right)^2+\left(6-\frac{20}{3}\right)^2 \right\}=\frac{8}{9}=0.888888\ldots
となり、このときが最小です。
同じ重さのグッズが複数存在し得ること、 各グッズはいずれかの福袋に入っている必要があることに注意してください。
Score : 525 points
Problem Statement
AtCoder Inc. sells merchandise on its online shop.
There are N items remaining in the company. The weight of the i-th item (1\leq i\leq N) is W_i.
Takahashi will sell these items as D lucky bags.
He wants to minimize the variance of the total weights of the items in the lucky bags.
Here, the variance is defined as V=\frac{1}{D}\displaystyle\sum_{i=1}^D (x_i-\bar{x})^2, where x_1,x_2,\ldots,x_D are the total weights of the items in the lucky bags, and \bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D) is the average of x_1,x_2,\ldots,x_D.
Find the variance of the total weights of the items in the lucky bags when the items are divided to minimize this value.
It is acceptable to have empty lucky bags (in which case the total weight of the items in that bag is defined as 0),
but each item must be in exactly one of the D lucky bags.
Constraints
- 2 \leq D\leq N\leq 15
- 1 \leq W_i\leq 10^8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D W_1 W_2 \ldots W_N
Output
Print the variance of the total weights of the items in the lucky bags when the items are divided to minimize this value.
Your output will be considered correct if the absolute or relative error from the true value is at most 10^{-6}.
Sample Input 1
5 3 3 5 3 6 3
Sample Output 1
0.888888888888889
If you put the first and third items in the first lucky bag, the second and fifth items in the second lucky bag, and the fourth item in the third lucky bag, the total weight of the items in the bags are 6, 8, and 6, respectively.
Then, the average weight is \frac{1}{3}(6+8+6)=\frac{20}{3},
and the variance is
\frac{1}{3}\left\{\left(6-\frac{20}{3}\right)^2+\left(8-\frac{20}{3}\right)^2+\left(6-\frac{20}{3}\right)^2 \right\}=\frac{8}{9}=0.888888\ldots,
which is the minimum.
Note that multiple items may have the same weight, and that each item must be in one of the lucky bags.