問題一覧 > 通常問題

No.576 E869120 and Rings

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 128 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 33
作問者 : e869120e869120 / テスター : square1001square1001
5 ProblemId : 1923 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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

宝石の並びとしては、以下のようになります。
yukicoder_1923_1
その場合、宝石 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もしくは右上の雲マークをクリックしてアカウントを作成してください。