/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は気象データの分析をしています。
一列に並んだ N 地点の観測所があり、各観測所 i（1 \leq i \leq N）ではその日の気温 F_i が記録されています。高橋君は、気温の最大値が目立たないようにデータを平滑化したいと考えています。
平滑化処理では、連続する K 地点がすべて観測所の範囲内に収まるように整数 l（1 \leq l \leq N - K + 1）を選び、観測所 l, l+1, \ldots, l+K-1 をグループとします。そのグループ内の全地点の気温を、グループ内の算術平均値 \displaystyle\frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K} に一斉に置き換えます。グループに含まれない地点の気温は変化しません。この操作をちょうど 1 回行います（操作を行わないという選択はできません）。
操作後の各地点の気温を F'_1, F'_2, \ldots, F'_N とします。すなわち、グループに含まれる地点 i（l \leq i \leq l+K-1）については \displaystyle F'_i = \frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K} となり、それ以外の地点 i については F'_i = F_i となります。ここで、平均値は実数として正確に計算し、切り捨てや四捨五入は行いません。
高橋君は、l を最適に選ぶことで、操作後の気温の最大値 \displaystyle\max_{1 \leq i \leq N} F'_i をできるだけ小さくしたいです。
この最大値として考えられる最小の値を求めてください。
制約
- 1 \leq K \leq N \leq 10^6
- -10^9 \leq F_i \leq 10^9
- N, K は整数
- F_i は整数
入力
N K F_1 F_2 \ldots F_N
- 1 行目には、観測所の数を表す整数 N と、平滑化処理で選ぶ連続する地点数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各観測所の気温を表す整数 F_1, F_2, \ldots, F_N が、スペース区切りで与えられる。
出力
平滑化処理後の気温の最大値として考えられる最小の値を 1 行で出力せよ。なお、操作における平均値の計算は正確な実数値として行うが、出力については真の値との絶対誤差または相対誤差が 10^{-6} 以下であれば正解とする。
入力例 1
5 2 3 10 4 2 8
出力例 1
8.0000000000
入力例 2
6 3 -5 0 -2 7 1 -3
出力例 2
1.6666666667
入力例 3
12 4 15 -3 22 8 7 30 -10 5 18 12 -4 25
出力例 3
25.0000000000
入力例 4
30 7 100 -50 23 75 -10 200 0 45 90 -80 60 110 -30 15 5 130 -100 70 85 -20 40 95 -60 150 10 -5 55 120 -90 35
出力例 4
150.0000000000
入力例 5
1 1 -1000000000
出力例 5
-1000000000.0000000000
Score : 366 pts
Problem Statement
Takahashi is analyzing meteorological data.
There are N observation stations arranged in a line, and each observation station i (1 \leq i \leq N) has recorded the temperature F_i for the day. Takahashi wants to smooth the data so that the maximum temperature value is less prominent.
In the smoothing process, he selects an integer l (1 \leq l \leq N - K + 1) such that K consecutive stations all fall within the range of observation stations, and groups stations l, l+1, \ldots, l+K-1 together. The temperatures of all stations in the group are simultaneously replaced with the arithmetic mean of the group \displaystyle\frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K}. The temperatures of stations not included in the group remain unchanged. This operation is performed exactly once (choosing not to perform the operation is not allowed).
Let F'_1, F'_2, \ldots, F'_N be the temperatures at each station after the operation. That is, for stations i included in the group (l \leq i \leq l+K-1), \displaystyle F'_i = \frac{F_l + F_{l+1} + \cdots + F_{l+K-1}}{K}, and for all other stations i, F'_i = F_i. Here, the mean is computed exactly as a real number, without truncation or rounding.
Takahashi wants to choose l optimally to minimize the maximum temperature after the operation, \displaystyle\max_{1 \leq i \leq N} F'_i.
Find the minimum possible value of this maximum.
Constraints
- 1 \leq K \leq N \leq 10^6
- -10^9 \leq F_i \leq 10^9
- N, K are integers
- F_i are integers
Input
N K F_1 F_2 \ldots F_N
- The first line contains the integer N representing the number of observation stations and the integer K representing the number of consecutive stations chosen in the smoothing process, separated by a space.
- The second line contains the integers F_1, F_2, \ldots, F_N representing the temperatures at each observation station, separated by spaces.
Output
Output in one line the minimum possible value of the maximum temperature after the smoothing process. Note that while the mean in the operation is computed as an exact real number, the output will be considered correct if the absolute error or relative error from the true value is at most 10^{-6}.
Sample Input 1
5 2 3 10 4 2 8
Sample Output 1
8.0000000000
Sample Input 2
6 3 -5 0 -2 7 1 -3
Sample Output 2
1.6666666667
Sample Input 3
12 4 15 -3 22 8 7 30 -10 5 18 12 -4 25
Sample Output 3
25.0000000000
Sample Input 4
30 7 100 -50 23 75 -10 200 0 45 90 -80 60 110 -30 15 5 130 -100 70 85 -20 40 95 -60 150 10 -5 55 120 -90 35
Sample Output 4
150.0000000000
Sample Input 5
1 1 -1000000000
Sample Output 5
-1000000000.0000000000