#1196653 (C#) No.576 E869120 and Rings

• 問題: No.576 E869120 and Rings
• ユーザー: aketijyuuzou
• 提出日時: 2026-11-03 11:03:28
• 言語: C# (.NET 10.0.403 + ACL)
• 結果: AC
• 実行時間: 791 ms / 1,500 ms
• コード長: 3,739 bytes
• コンパイル時間: 8,322 ms
• コンパイル使用メモリ: 172,072 KB
• 実行使用メモリ: 81,528 KB
• 最終ジャッジ日時: 2026-11-03 11:03:53
• 合計ジャッジ時間: 22,655 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 28

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (201 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

// gemini作成
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");
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8 4");
            WillReturn.Add("11011001");
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 4");
            WillReturn.Add("1001001001");
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("3 3");
            WillReturn.Add("110");
        }
        else {
            string wkStr;
            while ((wkStr = Console.In.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static int mK;
    static double[] mAArr;

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

        // 全て1の場合
        if (HasZero == false) {
            Console.WriteLine(1);
            return;
        }

        // 答えで二分探索
        double L = 0D;
        double R = 1D;

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

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

    // NeedAVGを達成できるかを判定
    static bool CanAchieve(double pNeedAVG)
    {
        GC.Collect();

        // --- 【変更点1】毎回新しく配列を生成してグローバル変数の破壊を防ぐ ---
        double[] compareArr = new double[mN * 2];

        // --- 【変更点2】2周分のデータを正しく埋める ---
        for (int I = 0; I < mN * 2; I++) {
            compareArr[I] = mAArr[I % mN] - pNeedAVG;
        }

        // --- 【変更点3】安全な累積和配列 (pref) の作成 ---
        double[] pref = new double[mN * 2 + 1];
        for (int I = 0; I < mN * 2; I++) {
            pref[I + 1] = pref[I] + compareArr[I];
        }

        // 長さ L (mK <= L <= mN) の区間 [j, i] で pref[i] - pref[j] >= 0 となるものがあるか
        // 条件: i - mN <= j <= i - mK
        var q = new LinkedList<int>();

        for (int i = 0; i <= mN * 2; i++) {
            // ウィンドウの範囲外（古くなった左端）を削除
            while (q.Count > 0 && q.First.Value < i - mN) {
                q.RemoveFirst();
            }

            // 新しく左端候補になり得るインデックスをキューに追加（単調性を保つ）
            int addIdx = i - mK;
            if (addIdx >= 0) {
                while (q.Count > 0 && pref[q.Last.Value] >= pref[addIdx]) {
                    q.RemoveLast();
                }
                q.AddLast(addIdx);
            }

            // 判定
            if (q.Count > 0) {
                int bestJ = q.First.Value;
                if (bestJ >= i - mN && pref[i] - pref[bestJ] >= 0D) {
                    return true;
                }
            }
        }

        return false;
    }
}