結果

問題 No.576 E869120 and Rings
ユーザー 明智重蔵明智重蔵
提出日時 2023-01-07 13:59:14
言語 C#
(.NET 8.0.203)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,542 bytes
コンパイル時間 18,209 ms
コンパイル使用メモリ 170,396 KB
実行使用メモリ 194,952 KB
最終ジャッジ日時 2024-05-08 10:27:51
合計ジャッジ時間 44,646 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,277 ms
69,764 KB
testcase_01 AC 1,213 ms
69,920 KB
testcase_02 AC 1,170 ms
69,800 KB
testcase_03 AC 1,262 ms
69,760 KB
testcase_04 AC 1,239 ms
69,632 KB
testcase_05 AC 1,259 ms
69,664 KB
testcase_06 AC 1,284 ms
69,796 KB
testcase_07 AC 1,182 ms
69,920 KB
testcase_08 AC 1,049 ms
74,020 KB
testcase_09 AC 1,151 ms
71,052 KB
testcase_10 AC 1,243 ms
71,848 KB
testcase_11 AC 1,120 ms
74,012 KB
testcase_12 AC 1,103 ms
73,896 KB
testcase_13 AC 871 ms
80,036 KB
testcase_14 AC 1,046 ms
69,668 KB
testcase_15 AC 66 ms
38,320 KB
testcase_16 AC 968 ms
81,772 KB
testcase_17 AC 856 ms
73,760 KB
testcase_18 AC 961 ms
71,276 KB
testcase_19 AC 942 ms
70,688 KB
testcase_20 AC 937 ms
71,076 KB
testcase_21 AC 955 ms
70,820 KB
testcase_22 AC 57 ms
30,204 KB
testcase_23 AC 58 ms
30,336 KB
testcase_24 AC 60 ms
30,464 KB
testcase_25 AC 54 ms
29,952 KB
testcase_26 AC 58 ms
30,208 KB
testcase_27 AC 60 ms
30,336 KB
testcase_28 AC 59 ms
30,336 KB
testcase_29 MLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (105 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

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