No.576 E869120 and Rings

問題提出提出一覧質問統計解説

問題一覧 > 通常問題

No.576 E869120 and Rings

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 128 MB / 小数誤差許容問題　絶対誤差または相対誤差が

10^{- 6}

以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 33
作問者 :

e869120 / テスター :

square1001

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

宝石の並びとしては、以下のようになります。

その場合、宝石 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もしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder