結果

問題 No.576 E869120 and Rings
コンテスト
ユーザー aketijyuuzou
提出日時 2024-10-13 12:39:32
言語 C#(csc)
(csc 3.9.0)
結果
MLE  
実行時間 -
コード長 4,542 bytes
コンパイル時間 1,125 ms
コンパイル使用メモリ 113,820 KB
実行使用メモリ 140,632 KB
最終ジャッジ日時 2024-10-13 12:40:13
合計ジャッジ時間 36,967 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 19 MLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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

        // 答えで二分探索
        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<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;

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