yukicoder 0576 E869120 and Rings

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        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") {
            WillReturn.Add("3 3");
            WillReturn.Add("110");
            //0.666666666667
        }
        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<string> 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;
        }

        // 答えで二分探索
        if (CanAchieve(1)) {
            Console.WriteLine(1);
            return;
        }

        double L = 0D;
        double R = 1D;

        while (L + 0.00000001D < R) {
            double Mid = (L + R) / 2D;

            bool Result = CanAchieve(Mid);
            if (Result) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        Console.WriteLine(L);
    }

    // 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<int>();

        // 終端を全探索
        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;

            // 引退処理
            while (InsLinkedList.Count > 0) {
                int FrontInd = InsLinkedList.First.Value;
                if (RangeSta <= FrontInd && FrontInd <= RangeEnd) {
                    break;
                }
                InsLinkedList.RemoveFirst();
                continue;
            }

            if (FirstFlag) {
                FirstFlag = false;
            }
            else {
                RangeSta = Math.Max(RangeSta, PrevRangeEnd + 1);
            }

            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;
    }
}

解説

まず青の割合をA以上にする条件の不等式を同値変形し、
見通しを良くします。

青の個数 / 全体個数 >= A
⇔
青の個数 >= A * 全体個数
⇔
青の個数 - A * 全体個数 >= 0

この不等式を良く見ると
青なら1-A , 赤なら -A
とした時のSumが0以上なら良いと分かります。

解には単調性があるので、答えを二分探索します。
区間の終端を全探索し、区間の始点を増やしつつ、
スライド最小値のアルゴリズムを使えば、O(Nlog(N))で解けます。

スライド最小値では、
LinkedList内で
FirstからLastに向けて、
狭義単調増加なデータ構造にしてます。
こうすることで必ずFirstが最小値となります。