結果

問題 No.576 E869120 and Rings
ユーザー 明智重蔵明智重蔵
提出日時 2023-01-07 13:59:14
言語 C#
(.NET 8.0.203)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,542 bytes
コンパイル時間 13,363 ms
コンパイル使用メモリ 149,284 KB
実行使用メモリ 170,168 KB
最終ジャッジ日時 2023-08-21 04:55:06
合計ジャッジ時間 36,689 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,119 ms
67,064 KB
testcase_01 AC 1,046 ms
67,056 KB
testcase_02 AC 1,015 ms
66,932 KB
testcase_03 AC 1,119 ms
66,992 KB
testcase_04 AC 1,091 ms
65,196 KB
testcase_05 AC 1,116 ms
69,280 KB
testcase_06 AC 1,115 ms
67,156 KB
testcase_07 AC 1,018 ms
67,284 KB
testcase_08 AC 894 ms
65,924 KB
testcase_09 AC 988 ms
68,172 KB
testcase_10 AC 1,057 ms
69,704 KB
testcase_11 AC 958 ms
67,428 KB
testcase_12 AC 954 ms
67,800 KB
testcase_13 AC 756 ms
77,368 KB
testcase_14 AC 819 ms
67,084 KB
testcase_15 AC 60 ms
37,228 KB
testcase_16 AC 865 ms
85,916 KB
testcase_17 AC 697 ms
67,432 KB
testcase_18 AC 839 ms
68,916 KB
testcase_19 AC 820 ms
67,680 KB
testcase_20 AC 797 ms
67,376 KB
testcase_21 AC 822 ms
65,332 KB
testcase_22 AC 54 ms
30,652 KB
testcase_23 AC 56 ms
28,876 KB
testcase_24 AC 54 ms
28,832 KB
testcase_25 AC 51 ms
28,504 KB
testcase_26 AC 56 ms
28,784 KB
testcase_27 AC 55 ms
28,768 KB
testcase_28 AC 56 ms
28,924 KB
testcase_29 MLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
  Determining projects to restore...
  Restored /home/judge/data/code/main.csproj (in 131 ms).
.NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f
Copyright (C) Microsoft Corporation.All rights reserved.

  プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください
  main -> /home/judge/data/code/bin/Release/net6.0/main.dll
  main -> /home/judge/data/code/bin/Release/net6.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