#1196425 (C#) No.252 "良問"(良問とは言っていない (2)

• 問題: No.252 "良問"(良問とは言っていない (2)
• ユーザー: aketijyuuzou
• 提出日時: 2026-11-01 16:41:16
• 言語: C# (.NET 10.0.403 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 9,784 bytes
• コンパイル時間: 5,319 ms
• コンパイル使用メモリ: 171,844 KB
• 実行使用メモリ: 49,648 KB
• 最終ジャッジ日時: 2026-11-01 16:41:29
• 合計ジャッジ時間: 12,295 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

ファイルパターン	結果
other	AC * 3 TLE * 1 -- * 10

コンパイルメッセージ

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

ソースコード

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

// https://yukicoder.me/problems/no/252
class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("veryverygoodproblem");
            WillReturn.Add("goodexcellentproblems");
            WillReturn.Add("problemgood");
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("goodproblem");
            WillReturn.Add("agdddekproblemsdl");
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9");
            WillReturn.Add("geodaaaproblem");
            WillReturn.Add("goodproblen");
            WillReturn.Add("badendlessprobrem");
            WillReturn.Add("podpdpprrobleem");
            WillReturn.Add("problemgoodprobremgood");
            WillReturn.Add("smallproblem");
            WillReturn.Add("proproprefurohobbyhobby");
            WillReturn.Add("gooeproblemd");
            WillReturn.Add("itisproblemcoolgoodproblem");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static string mS;
    static char[] mCharArr;
    static long UB_S;

    static void Main()
    {
        List<string> InputList = GetInputList();
        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(1)) {
            mS = EachStr;
            mCharArr = EachStr.ToCharArray();
            UB_S = mCharArr.GetUpperBound(0);
            long Answer = Solve();
            sb.Append(Answer);
            sb.AppendLine();
            GC.Collect();
        }
        Console.Write(sb.ToString());
    }

    static int Solve()
    {
        Dictionary<int, int> CostDictGood = DeriveCost("good");
        Dictionary<int, int> CostDictProb = DeriveCost("problem");

        // スパーステーブル作成
        int[] ValuesArr = CostDictProb.Values.ToArray();
        var InsSparseTable = new SparseTable<int>(ValuesArr, true);

        HashSet<int> PosSet = GetPosSet();
        int Answer = int.MaxValue;

        int BaseCnt = 0;
        // goodにする位置を全探索
        for (int I = 0; I <= UB_S; I++) {
            int Cost = BaseCnt;
            int RangeSta = I + 4;
            int RangeEnd = ValuesArr.GetUpperBound(0);
            if (RangeSta <= RangeEnd) {
                Cost += CostDictGood[I] + InsSparseTable.Query(RangeSta, RangeEnd);
                Answer = Math.Min(Answer, Cost);
            }
            if (PosSet.Contains(I)) {
                BaseCnt++;
            }
        }
        return Answer;
    }

    // 文字列を引数とし、コスト[開始Ind]なDictを返す
    static Dictionary<int, int> DeriveCost(string pTarget)
    {
        var CostDict = new Dictionary<int, int>();
        for (int I = 0; I <= UB_S; I++) {
            if (I + pTarget.Length - 1 > UB_S) break;

            int Cost = 0;
            for (int J = 0; J <= pTarget.Length - 1; J++) {
                if (mCharArr[I + J] != pTarget[J]) {
                    Cost++;
                }
            }
            CostDict[I] = Cost;
        }
        return CostDict;
    }

    // problemのmの位置のSetを返す
    static HashSet<int> GetPosSet()
    {
        var PosList = new HashSet<int>();
        for (int I = 0; I <= UB_S; I++) {
            if (I + "problem".Length - 1 > UB_S) break;
            string SubStr = mS.Substring(I, "problem".Length);
            if (SubStr == "problem") {
                PosList.Add(I + "problem".Length - 1);
            }
        }
        return PosList;
    }
}

#region SparseTable
internal class SparseTable<Type> where Type : IComparable<Type>
{
    // 最小値か最大値[2の指数][開始Ind]なArr
    private Type[][] mMinOrMaxJagArr;

    // Log2の値[2べき値] なDict
    private Dictionary<long, long> mLogDict = new Dictionary<long, long>();

    // 対応する2べき値[クエリの区間長]
    private long[] mBeki2Arr;

    // 最小値を取得するか？
    private bool mIsMin = false;

    // コンストラクタ1(配列が引数)
    internal SparseTable(Type[] pInitArr, bool pIsMin)
    {
        mIsMin = pIsMin;

        long Sisuu = 0;
        long Beki2 = 1;
        while (true) {
            mLogDict[Beki2] = Sisuu;
            Beki2 *= 2;

            if (Beki2 > pInitArr.Length) {
                break;
            }
            Sisuu++;
        }

        mMinOrMaxJagArr = new Type[Sisuu + 1][];
        foreach (var EachPair in mLogDict) {
            long CurrBeki2 = EachPair.Key;
            long CurrSisuu = EachPair.Value;
            long CurrUB = pInitArr.GetUpperBound(0) - CurrBeki2 + 1;
            mMinOrMaxJagArr[CurrSisuu] = new Type[CurrUB + 1];
        }

        // 長さ1の分を初期化
        for (long I = 0; I <= pInitArr.GetUpperBound(0); I++) {
            mMinOrMaxJagArr[0][I] = pInitArr[I];
        }

        // コンストラクタのヘルパメソッド
        ConstructorHelper();

        // 対応する2べき値[クエリの区間長]を設定
        SetBeki2Arr(pInitArr.Length);
    }

    // コンストラクタ2(Listが引数)
    internal SparseTable(List<Type> pInitList, bool pIsMin)
    {
        mIsMin = pIsMin;

        long Sisuu = 0;
        long Beki2 = 1;
        while (true) {
            mLogDict[Beki2] = Sisuu;
            Beki2 *= 2;

            if (Beki2 > pInitList.Count) {
                break;
            }
            Sisuu++;
        }

        mMinOrMaxJagArr = new Type[Sisuu + 1][];
        foreach (var EachPair in mLogDict) {
            long CurrBeki2 = EachPair.Key;
            long CurrSisuu = EachPair.Value;
            long CurrUB = pInitList.Count - 1 - CurrBeki2 + 1;
            mMinOrMaxJagArr[CurrSisuu] = new Type[CurrUB + 1];
        }

        // 長さ1の分を初期化
        for (int I = 0; I <= pInitList.Count - 1; I++) {
            mMinOrMaxJagArr[0][I] = pInitList[I];
        }

        // コンストラクタのヘルパメソッド
        ConstructorHelper();

        // 対応する2べき値[クエリの区間長]を設定
        SetBeki2Arr(pInitList.Count);
    }

    // コンストラクタ3(列挙が引数)
    internal SparseTable(IEnumerable<Type> pInitEnum, bool pIsMin)
    {
        mIsMin = pIsMin;

        Type[] InitArr = pInitEnum.ToArray();

        long Sisuu = 0;
        long Beki2 = 1;
        while (true) {
            mLogDict[Beki2] = Sisuu;
            Beki2 *= 2;

            if (Beki2 > InitArr.Length) {
                break;
            }
            Sisuu++;
        }

        mMinOrMaxJagArr = new Type[Sisuu + 1][];
        foreach (var EachPair in mLogDict) {
            long CurrBeki2 = EachPair.Key;
            long CurrSisuu = EachPair.Value;
            long CurrUB = InitArr.GetUpperBound(0) - CurrBeki2 + 1;
            mMinOrMaxJagArr[CurrSisuu] = new Type[CurrUB + 1];
        }

        // 長さ1の分を初期化
        for (int I = 0; I <= InitArr.GetUpperBound(0); I++) {
            mMinOrMaxJagArr[0][I] = InitArr[I];
        }

        // コンストラクタのヘルパメソッド
        ConstructorHelper();

        // 対応する2べき値[クエリの区間長]を設定
        SetBeki2Arr(InitArr.Length);
    }

    // 対応する2べき値[クエリの区間長]を設定
    private void SetBeki2Arr(long pDataLen)
    {
        long[] Beki2Arr = mLogDict.Keys.ToArray();

        mBeki2Arr = new long[pDataLen + 1];
        long CurrBeki2 = 1;
        for (long I = 0; I <= pDataLen; I++) {
            mBeki2Arr[I] = CurrBeki2;
            if (mLogDict.ContainsKey(I)) {
                CurrBeki2 = I;
            }
        }
    }

    // コンストラクタのヘルパメソッド
    private void ConstructorHelper()
    {
        for (long LoopLength = 2; LoopLength < long.MaxValue; LoopLength *= 2) {
            if (mLogDict.ContainsKey(LoopLength) == false) break;

            long HalfRange = LoopLength / 2;
            Type[] CurrArr = mMinOrMaxJagArr[mLogDict[HalfRange]];
            Type[] SendArr = mMinOrMaxJagArr[mLogDict[LoopLength]];
            for (long I = 0; I <= SendArr.GetUpperBound(0); I++) {
                long StaInd1 = I;
                long EndInd1 = I + HalfRange - 1;
                long StaInd2 = EndInd1 + 1;
                long EndInd2 = StaInd2 + HalfRange - 1;

                Type Val1 = CurrArr[I];
                Type Val2 = CurrArr[StaInd2];
                int CompResult = Val1.CompareTo(Val2);
                if (mIsMin) {
                    SendArr[I] = (CompResult >= 1 ? Val2 : Val1);
                }
                else {
                    SendArr[I] = (CompResult >= 1 ? Val1 : Val2);
                }
            }
        }
    }

    // 閉区間 [L,R]の最小値または最大値を求める
    internal Type Query(long pL, long pR)
    {
        // 区間を内包する2べき値を使用
        long RangeLen = pR - pL + 1;
        long Beki2 = mBeki2Arr[RangeLen];
        long Sisuu = mLogDict[Beki2];

        Type Val1 = mMinOrMaxJagArr[Sisuu][pL];
        Type Val2 = mMinOrMaxJagArr[Sisuu][pR - Beki2 + 1];
        int CompResult = Val1.CompareTo(Val2);

        if (mIsMin) {
            return (CompResult >= 1 ? Val2 : Val1);
        }
        return (CompResult >= 1 ? Val1 : Val2);
    }
}
#endregion