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 if (InputPattern == "Input4") { return System.IO.File.ReadAllLines(@"D:\CSharp\TestConsole\test_in\in01.txt").ToList(); } 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); 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; double[] RunSumArr = new double[UB + 1]; // 累積和を設定する for (int I = 0; I <= UB; I++) { RunSumArr[I] = CompareList[I]; if (0 < I) { RunSumArr[I] += RunSumArr[I - 1]; } } var InsDeque = new Deque(); // 終端を全探索 bool FirstFlag = true; int PrevRangeEnd = -1; 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); // 始点候補のEnd int RangeEnd = I - mK + 1; if (FirstFlag) { FirstFlag = false; } else { RangeSta = Math.Max(RangeSta, PrevRangeEnd + 1); } // 引退処理 while (InsDeque.Count > 0) { int FrontInd = InsDeque[0]; if (RangeSta <= FrontInd && FrontInd <= RangeEnd == false) { InsDeque.PopFront(); continue; } break; } for (int J = RangeSta; J <= RangeEnd; J++) { // 押し出し処理 while (InsDeque.Count > 0) { int LastInd = InsDeque[InsDeque.Count - 1]; if (RunSumArr[LastInd] - CompareList[LastInd] > RunSumArr[J] - CompareList[J]) { InsDeque.PopBack(); continue; } break; } // 追加処理 InsDeque.PushBack(J); } PrevRangeEnd = RangeEnd; // 最小値 double MinVal = RunSumArr[InsDeque[0]] - CompareList[InsDeque[0]]; if (RunSumArr[I] - MinVal >= 0) return true; } return false; } } #region Deque internal class Deque { T[] buf; int offset, count, capacity; internal int Count { get { return count; } } internal Deque(int cap) { buf = new T[capacity = cap]; } internal Deque() { buf = new T[capacity = 16]; } internal T this[int index] { get { return buf[GetIndex(index)]; } set { buf[GetIndex(index)] = value; } } private int GetIndex(int index) { if (index >= capacity) throw new IndexOutOfRangeException("out of range"); int ret = index + offset; if (ret >= capacity) ret -= capacity; return ret; } internal void PushFront(T item) { if (count == capacity) Extend(); if (--offset < 0) offset += buf.Length; buf[offset] = item; count++; } internal T PopFront() { if (count == 0) throw new InvalidOperationException("collection is empty"); count--; T ret = buf[offset++]; if (offset >= capacity) offset -= capacity; return ret; } internal void PushBack(T item) { if (count == capacity) Extend(); int id = count + offset; count++; if (id >= capacity) id -= capacity; buf[id] = item; } internal T PopBack() { if (count == 0) throw new InvalidOperationException("collection is empty"); return buf[GetIndex(--count)]; } internal void Insert(int index, T item) { if (index > count) throw new IndexOutOfRangeException(); this.PushFront(item); for (int i = 0; i < index; i++) this[i] = this[i + 1]; this[index] = item; } internal T RemoveAt(int index) { if (index < 0 || index >= count) throw new IndexOutOfRangeException(); T ret = this[index]; for (int i = index; i > 0; i--) this[i] = this[i - 1]; this.PopFront(); return ret; } private void Extend() { T[] newBuffer = new T[capacity << 1]; if (offset > capacity - count) { int len = buf.Length - offset; Array.Copy(buf, offset, newBuffer, 0, len); Array.Copy(buf, 0, newBuffer, len, count - len); } else Array.Copy(buf, offset, newBuffer, 0, count); buf = newBuffer; offset = 0; capacity <<= 1; } internal T[] Items//デバッグ時に中身を調べるためのプロパティ { get { T[] a = new T[count]; for (int i = 0; i < count; i++) a[i] = this[i]; return a; } } } #endregion