No.576 E869120 and Rings
レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限
: 128 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 33
作問者 :
e869120
/ テスター :
square1001
タグ : / 解いたユーザー数 33
作問者 :
e869120
/ テスター :
square1001
問題文最終更新日: 2018-02-23 23:44:42
問題文
E869120 は、指輪をもらいました。この指輪は $N$ 個の宝石から成り、円環上になっています。
また、それぞれの宝石は青色か赤色のどちらかです。
さて、E869120 は指輪の 連続した一部分を取り出すことにしました。また、その一部分は $K$ 個以上の宝石から成り立たなければなりません。
その時、取り出した「指輪の一部分」の中の「青色の宝石」の割合の最大値を求めなさい。
入力
$N$ $K$ $a_1$$a_2$...$a_N$
- $1≦K≦N≦500000$
- $0≦a_i≦1$
- $a_i=0$ の時赤色、$a_i=1$ の時青色
出力
青色の割合の最大値を小数で出力してください。許容誤差は $10^{-6}$ 以下です。 最後に改行してください。
サンプル
サンプル1
入力
8 4 11101110
出力
0.857142857142857
宝石の並びとしては、以下のようになります。
その場合、宝石 1, 2, 3, 4, 5, 6, 7 を取ったら、青い宝石 $6$ 個、赤い宝石 $1$ 個が達成できます。
そのとき、割合は $6 / 7$ ≒ $0.857142857...$ となります。
なお、例えば 宝石 5, 6, 7 を取れば青の割合は $100$% となりますが、 $K=4$ のため、必ず $4$ つ以上宝石を取らなければなりません。
サンプル2
入力
8 4 11011001
出力
0.833333333333333
区間 [8, 5] （つまり、宝石 {8, 1, 2, 3, 4, 5} ということ） を取り出しましょう。
そうすると、青の割合は $5 / 6$ ≒ $0.833333333...$ となります。
サンプル3
入力
10 4 1001001001
出力
0.6
区間 [10, 4] （つまり、宝石 {10, 1, 2, 3, 4} ということ）を取り出しましょう。
区間 [7, 1] でも同じ割合が達成できます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。