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 double[] mAArr; static double[] mCompareArr; static double[] mRunSumArr; 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]; mAArr = new double[mN]; bool HasZero = false; for (int I = 0; I <= AStr.Length - 1; I++) { if (AStr[I] == '0') { mAArr[I] = 0D; HasZero = true; } if (AStr[I] == '1') mAArr[I] = 1D; } mCompareArr = new double[mN * 2]; mRunSumArr = new double[mN * 2]; // 全て1の場合 if (HasZero == false) { Console.WriteLine(1); return; } // 答えで二分探索 double L = 0D; double R = 1D; //while (L + 0.0000001 < 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] = mAArr[I] - pNeedAVG; mCompareArr[I] = mAArr[I] - pNeedAVG; } int UB = mCompareArr.GetUpperBound(0); // 累積和を設定する for (int I = 0; I <= UB; I++) { mRunSumArr[I] = mCompareArr[I]; if (0 < I) { mRunSumArr[I] += mRunSumArr[I - 1]; } } var InsDeque = new Deque(); // 終端を全探索 bool FirstFlag = true; int PrevRangeEnd = -1; for (int I = mN - 1; I <= UB; 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 (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 (mRunSumArr[LastInd] - mCompareArr[LastInd] > mRunSumArr[J] - mCompareArr[J]) { InsDeque.PopBack(); continue; } break; } // 追加処理 InsDeque.PushBack(J); } PrevRangeEnd = RangeEnd; // 最小値 double MinVal = mRunSumArr[InsDeque[0]] - mCompareArr[InsDeque[0]]; if (mRunSumArr[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