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.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static int mN; static int mK; static List mAList = new List(); static void Main() { List InputList = GetInputList(); int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray(); mN = wkArr[0]; mK = wkArr[1]; string AStr = InputList[1]; foreach (char EachA in AStr) { if (EachA == '0') mAList.Add(0); if (EachA == '1') mAList.Add(1); } // 全て1の場合 if (mAList.TrueForAll(pX => pX == 1D)) { Console.WriteLine(1); return; } // 答えで二分探索 double L = 0; double R = 1; while (L + 0.0000000001 < R) { double Mid = (L + R) / 2; bool Result = CanAchieve(Mid); //Console.WriteLine("L={0},Mid={1},R={2},Result={3}", L, Mid, R, Result); if (Result) { L = Mid; } else { R = Mid; } } Console.WriteLine(R); } // NeedAVGを達成できるかを判定 static bool CanAchieve(double pNeedAVG) { // 取得区間はK以上N以下なので、2倍の長さにしておく var CompareList = new List(); for (int I = 1; I <= 2; I++) { foreach (double EachA in mAList) { CompareList.Add(EachA - pNeedAVG); } } int UB = CompareList.Count - 1; // 累積和を設定する for (int I = 1; I <= UB; I++) { CompareList[I] += CompareList[I - 1]; } var InsSparseTable = new SparseTable(CompareList, true); // 終端を全探索 for (int I = 0; I <= UB; I++) { // 長さKの区間を取れなければcontinue if (I - mK + 1 < 0) continue; // 始点候補のSta int RangeSta = I - mN + 1; RangeSta = Math.Max(0, RangeSta); RangeSta--; RangeSta = Math.Max(0, RangeSta); // 始点候補のEnd int RangeEnd = I - mK + 1; RangeEnd--; RangeEnd = Math.Max(0, RangeEnd); double RangeMin = InsSparseTable.Query(RangeSta, RangeEnd); if (CompareList[I] - RangeMin >= 0) return true; } return false; } } #region SparseTable // スパーステーブル internal class SparseTable { private Type[] mInitArr; private int UB_0; private int UB_1; // 最小値か最大値[開始Ind,2の指数]なArr private Type[,] mMinOrMaxArr; // Log2の値[2べきな値] なDict static Dictionary mLogDict = new Dictionary(); // 最小値を取得するか? private bool mIsMin = false; // コンストラクタ internal SparseTable(IEnumerable pInitEnum, bool pIsMin) { mIsMin = pIsMin; mInitArr = pInitEnum.ToArray(); UB_0 = mInitArr.GetUpperBound(0); int Sisuu = 0; int Beki2 = 1; while (true) { mLogDict[Beki2] = Sisuu; if (Beki2 > mInitArr.Length) { break; } Beki2 *= 2; Sisuu++; } UB_1 = Sisuu; mMinOrMaxArr = new Type[UB_0 + 1, UB_1 + 1]; // 長さ1の分を初期化 for (int I = 0; I <= UB_0; I++) { mMinOrMaxArr[I, 0] = mInitArr[I]; } for (int LoopLength = 2; LoopLength < int.MaxValue; LoopLength *= 2) { bool WillBreak = true; int HalfRange = LoopLength / 2; for (int I = 0; I <= UB_0; I++) { int StaInd1 = I; int EndInd1 = I + HalfRange - 1; int StaInd2 = EndInd1 + 1; int EndInd2 = StaInd2 + HalfRange - 1; if (EndInd2 > UB_0) break; var KouhoList = new List(); KouhoList.Add(mMinOrMaxArr[I, mLogDict[HalfRange]]); KouhoList.Add(mMinOrMaxArr[StaInd2, mLogDict[HalfRange]]); if (mIsMin) { mMinOrMaxArr[I, mLogDict[LoopLength]] = KouhoList.Min(); } else { mMinOrMaxArr[I, mLogDict[LoopLength]] = KouhoList.Max(); } WillBreak = false; } if (WillBreak) break; } } // 閉区間 [L,R]の最小値または最大値を求める internal Type Query(int pL, int pR) { // 区間を内包する2べきを返す int Beki2 = 1; int Sisuu = 0; while (true) { int LeftRangeMax = pL + Beki2 - 1; int RightRangeMin = pR - Beki2 + 1; if (LeftRangeMax + 1 >= RightRangeMin) { break; } Beki2 *= 2; Sisuu++; } var KouhoList = new List(); KouhoList.Add(mMinOrMaxArr[pL, Sisuu]); KouhoList.Add(mMinOrMaxArr[pR - Beki2 + 1, Sisuu]); if (mIsMin) { return KouhoList.Min(); } return KouhoList.Max(); } } #endregion