A - Moving Slimes 解説 /

実行時間制限: 2 sec / メモリ制限: 2048 MB

配点 : 700 点

問題文

数直線上に N 匹のスライムがおり，i 番目のスライムは座標 A_i にいます． これらの座標はすべて異なります． 各スライムの重さは 1 です． また整数 K が与えられます．

あなたはまず K 匹のスライムを選び，選ばなかったスライムを数直線上から取り除きます． その後，選ばれたスライムは時刻 0 から以下のように移動を行います．

  • 各スライムの移動: 自分より大きい座標にいるスライムの重さの総和を R，自分より小さい座標にいるスライムの重さの総和を L とする． そして，速度 R-L で移動する．ここで，速度が符号付きであることに注意せよ．つまり，R-L<0 のときスライムは数直線上を負の方向へ動くものとする．

2 匹以上のスライムが同時に同じ座標に到達したとき，それらのスライムは合体します． 合体後のスライムの重さは合体前のスライムの重さの総和です． また合体後のスライムは上と同じ規則にしたがって移動します．

K 匹のスライムは合体を繰り返し，いずれ 1 匹のスライムになります． このスライムが誕生する瞬間を時刻 t とします． あなたの目標は，K 匹のスライムを上手に選び，この t を最大化することです． t の最大値を求めてください．

制約

  • 2 \leq K \leq N \leq 250000
  • 0 = A_1 < A_2 < \cdots < A_N \leq 10^9
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

N K
A_1 A_2 \cdots A_N

出力

答えを実数として出力せよ． 絶対誤差または相対誤差が 10^{-9} 以下ならば，正解と判定される．

入力例 1

3 2
0 1 2

出力例 1

1.00000000000000000000
  • 1 番目と 2 番目のスライムを選ぶと t=0.5 になります．
  • 1 番目と 3 番目のスライムを選ぶと t=1 になります．
  • 2 番目と 3 番目のスライムを選ぶと t=0.5 になります．

よって答えは 1 です．

入力例 2

4 3
0 1 4 9

出力例 2

2.83333333333333333333

1,2,4 番目のスライムを選んだ場合，スライムの移動の様子は以下のとおりです．

  • 1,2,4 番目のスライムを便宜的に X,Y,Z と呼ぶことにする．
  • 時刻 0 : X,Y,Z はそれぞれ速度 +2,0,-2 で移動を開始する．
  • 時刻 1/2 : X と Y が座標 1 で合体する．合体後のスライムを XY と呼ぶことにする．XY は速度 1 で移動を開始する．Z はこのとき座標 8 におり，速度は -2 のままである．
  • 時刻 17/6 : XY と Z が座標 10/3 で合体する．よって t=17/6 となる．

t を 17/6 より大きくすることはできないので，これが答えになります．

入力例 3

4 4
0 1 2 3

出力例 3

0.50000000000000000000

入力例 4

20 6
0 3441380 120768398 229897071 231209282 232046760 254924545 325399248 385631087 400098966 480503302 501372095 502644652 524585010 541761042 691400171 725009462 767549897 837806226 927396743

出力例 4

135453315.33333333333333333333

Score : 700 points

Problem Statement

There are N slimes on a number line, and the i-th slime is at coordinate A_i. All these coordinates are distinct. Each slime has a weight of 1. Also, you are given an integer K.

First, you will choose K slimes and remove the others from the number line. Then, from time 0, the chosen slimes will move as follows:

  • Movement of each slime: Let R be the total weight of slimes at coordinates greater than its own, and L be the total weight of slimes at coordinates less than its own. Then, it moves with a velocity of R-L. Note that the velocity can be negative. That is, it moves in the negative direction if R-L<0.

When two or more slimes reach the same coordinate at the same time, they merge. The weight of the merged slime is the sum of the weights of the slimes before merging. The merged slime will move according to the same rules as above.

The K slimes will continue to merge until there is only one slime left. Let t be the moment when this single slime is born. Your goal is to choose the K slimes so that t is maximized. Find the maximum value of t.

Constraints

  • 2 \leq K \leq N \leq 250000
  • 0 = A_1 < A_2 < \cdots < A_N \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_N

Output

Print the answer as a real number. It will be considered correct if the absolute or relative error is at most 10^{-9}.

Sample Input 1

3 2
0 1 2

Sample Output 1

1.00000000000000000000
  • Choosing the 1st and 2nd slimes results in t=0.5.
  • Choosing the 1st and 3rd slimes results in t=1.
  • Choosing the 2nd and 3rd slimes results in t=0.5.

Thus, the answer is 1.

Sample Input 2

4 3
0 1 4 9

Sample Output 2

2.83333333333333333333

If you choose the 1st, 2nd, and 4th slimes, the slimes move as follows:

  • For convenience, call the 1st, 2nd, and 4th slimes X, Y, and Z, respectively.
  • At time 0: X, Y, and Z start moving with velocity +2, 0, and -2, respectively.
  • At time 1/2: X and Y merge at coordinate 1. The merged slime, called XY, starts moving with velocity 1. On the other hand, Z is at coordinate 8 and continues moving with velocity -2.
  • At time 17/6: XY and Z merge at coordinate 10/3. Thus, t=17/6.

It is impossible to make t larger than 17/6, so this is the answer.

Sample Input 3

4 4
0 1 2 3

Sample Output 3

0.50000000000000000000

Sample Input 4

20 6
0 3441380 120768398 229897071 231209282 232046760 254924545 325399248 385631087 400098966 480503302 501372095 502644652 524585010 541761042 691400171 725009462 767549897 837806226 927396743

Sample Output 4

135453315.33333333333333333333