問題一覧 > 通常問題

No.576 E869120 and Rings

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 128 MB / 小数誤差許容問題　絶対誤差または相対誤差が $10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : （AC するまで非表示） / 解いたユーザー数 24
作問者 : e869120 / テスター : square1001
お気に入りにしたユーザー ProblemId : 1923 / 自分の提出
問題文最終更新日: 2026-06-26 12:17:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 難問コンテスト (順位表) の他の問題:

Problem Statement

E869120 received a ring. This ring consists of $N$ gems arranged in a circle.
Each gem is either blue or red.
E869120 has decided to take out a contiguous part of the ring. This part must consist of at least $K$ gems.
Find the maximum possible proportion of "blue gems" within the "part of the ring" taken out.

Input

$N$ $K$
$a_1$$a_2$...$a_N$

  • $1≦K≦N≦500000$
  • $0≦a_i≦1$
  • $a_i=0$ means red, and $a_i=1$ means blue

Output

Output the maximum proportion of blue as a decimal. An error of up to $10^{-6}$ is allowed. Print a newline at the end.

Sample

Sample 1
Input
8 4
11101110
Output
0.857142857142857

The gems are arranged as follows.
yukicoder_1923_1
In this case, taking gems 1, 2, 3, 4, 5, 6, 7 gives $6$ blue gems and $1$ red gem.
The proportion is then $6 / 7$ ≒ $0.857142857...$.

Note that, for example, taking gems 5, 6, 7 would make the proportion of blue $100$%, but since $K=4$, you must take at least $4$ gems.

Sample 2
Input
8 4
11011001
Output
0.833333333333333

Take out the interval [8, 5] (that is, gems {8, 1, 2, 3, 4, 5}).
Then the proportion of blue is $5 / 6$ ≒ $0.833333333...$.

Sample 3
Input
10 4
1001001001
Output
0.6

Take out the interval [10, 4] (that is, gems {10, 1, 2, 3, 4}).
The interval [7, 1] also achieves the same proportion.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。