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"); //0.857142857142857 } else if (InputPattern == "Input2") { WillReturn.Add("8 4"); WillReturn.Add("11011001"); //0.833333333333333 } else if (InputPattern == "Input3") { WillReturn.Add("10 4"); WillReturn.Add("1001001001"); //0.6 } else { string wkStr; while ((wkStr = Console.In.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static int mN; static int mK; static double[] mAArr; static double[] mCompareArr; static int UB2; 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; } mCompareArr = new double[mN * 2]; UB2 = mCompareArr.GetUpperBound(0); // 全て1の場合 if (HasZero == false) { Console.WriteLine(1); return; } // 答えで二分探索 double L = 0D; double R = 1D; while (L + 0.000001D < R) { double Mid = (L + R) / 2; bool Result = CanAchieve(Mid); if (Result) { L = Mid; } else { R = Mid; } } Console.WriteLine(R); } // NeedAVGを達成できるかを判定 static bool CanAchieve(double pNeedAVG) { // 取得区間はK以上N以下なので、2倍の長さにしておく for (int I = 0; I <= mAArr.GetUpperBound(0); I++) { mCompareArr[I + mN] = mCompareArr[I] = mAArr[I] - pNeedAVG; } // 累積和を設定する for (int I = 1; I <= UB2; I++) { mCompareArr[I] += mCompareArr[I - 1]; } var InsLinkedList = new LinkedList(); // 終端を全探索 bool FirstFlag = true; int PrevRangeEnd = -1; for (int I = mN - 1; I <= UB2; I++) { // 始点候補のSta int RangeSta = I - mN + 1; // 始点候補のEnd int RangeEnd = I - mK + 1; if (FirstFlag) { FirstFlag = false; } else { RangeSta = Math.Max(RangeSta, PrevRangeEnd + 1); } // 引退処理 while (InsLinkedList.Count > 0) { int FrontInd = InsLinkedList.First.Value; if (RangeSta <= FrontInd && FrontInd <= RangeEnd == false) { InsLinkedList.RemoveFirst(); continue; } break; } for (int J = RangeSta; J <= RangeEnd; J++) { // 押し出し処理 while (InsLinkedList.Count > 0) { int LastInd = InsLinkedList.Last.Value; double RunSum1 = 0D; if (LastInd >= 1) { RunSum1 = mCompareArr[LastInd - 1]; } double RunSum2 = 0D; if (J >= 1) { RunSum2 = mCompareArr[J - 1]; } if (RunSum1 >= RunSum2) { InsLinkedList.RemoveLast(); continue; } break; } // 追加処理 InsLinkedList.AddLast(J); } PrevRangeEnd = RangeEnd; // 最小値 int MinInd = InsLinkedList.First.Value; double MinVal = 0D; if (MinInd >= 1) { MinVal = mCompareArr[MinInd - 1]; } if (mCompareArr[I] - MinVal >= 0) return true; } return false; } }