// gemini作成 using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("8 4"); WillReturn.Add("11101110"); } else if (InputPattern == "Input2") { WillReturn.Add("8 4"); WillReturn.Add("11011001"); } else if (InputPattern == "Input3") { WillReturn.Add("10 4"); WillReturn.Add("1001001001"); } else if (InputPattern == "Input4") { WillReturn.Add("3 3"); WillReturn.Add("110"); } else { string wkStr; while ((wkStr = Console.In.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static int mN; static int mK; static double[] mAArr; static void Main() { List InputList = GetInputList(); int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray(); mN = wkArr[0]; mK = wkArr[1]; mAArr = new double[mN]; bool HasZero = false; for (int I = 0; I <= InputList[1].Length - 1; I++) { if (InputList[1][I] == '0') { mAArr[I] = 0D; HasZero = true; } if (InputList[1][I] == '1') mAArr[I] = 1D; } // 全て1の場合 if (HasZero == false) { Console.WriteLine(1); return; } // 答えで二分探索 double L = 0D; double R = 1D; while (L + 0.000001D < R) { double Mid = (L + R) / 2D; bool Result = CanAchieve(Mid); if (Result) { L = Mid; } else { R = Mid; } } Console.WriteLine(R); } // NeedAVGを達成できるかを判定 static bool CanAchieve(double pNeedAVG) { // --- 【変更点1】毎回新しく配列を生成してグローバル変数の破壊を防ぐ --- double[] compareArr = new double[mN * 2]; // --- 【変更点2】2周分のデータを正しく埋める --- for (int I = 0; I < mN * 2; I++) { compareArr[I] = mAArr[I % mN] - pNeedAVG; } // --- 【変更点3】安全な累積和配列 (pref) の作成 --- double[] pref = new double[mN * 2 + 1]; for (int I = 0; I < mN * 2; I++) { pref[I + 1] = pref[I] + compareArr[I]; } // 長さ L (mK <= L <= mN) の区間 [j, i] で pref[i] - pref[j] >= 0 となるものがあるか // 条件: i - mN <= j <= i - mK var q = new LinkedList(); for (int i = 0; i <= mN * 2; i++) { // ウィンドウの範囲外(古くなった左端)を削除 while (q.Count > 0 && q.First.Value < i - mN) { q.RemoveFirst(); } // 新しく左端候補になり得るインデックスをキューに追加(単調性を保つ) int addIdx = i - mK; if (addIdx >= 0) { while (q.Count > 0 && pref[q.Last.Value] >= pref[addIdx]) { q.RemoveLast(); } q.AddLast(addIdx); } // 判定 if (q.Count > 0) { int bestJ = q.First.Value; if (bestJ >= i - mN && pref[i] - pref[bestJ] >= 0D) { return true; } } } return false; } }