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

• 問題: No.252 "良問"(良問とは言っていない (2)
• ユーザー: aketijyuuzou
• 提出日時: 2026-11-01 16:31:05
• 言語: C# (.NET 10.0.403 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 12,624 bytes
• コンパイル時間: 5,451 ms
• コンパイル使用メモリ: 168,732 KB
• 実行使用メモリ: 51,880 KB
• 最終ジャッジ日時: 2026-11-01 16:31:17
• 合計ジャッジ時間: 11,843 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge7_0

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

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (170 ミリ秒)。
  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();
        foreach (string EachStr in InputList.Skip(1)) {
            mS = EachStr;
            mCharArr = EachStr.ToCharArray();
            UB_S = mCharArr.GetUpperBound(0);
            long Answer = Solve();
            GC.Collect();
            Console.WriteLine(Answer);
        }
    }

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

        // フェニック木作成
        var InsFenwick_Tree = new Fenwick_Tree(UB_S);
        List<int> PosList = GetPosList();
        foreach (int EachPos in PosList) {
            InsFenwick_Tree[EachPos]++;
        }

        var AnswerList = new List<int>();

        // goodにする位置を全探索
        for (int I = 0; I <= UB_S; I++) {
            int Cost = 0;
            if (I > 0) {
                // goodの前にあるproblemを破壊するコスト
                Cost = (int)InsFenwick_Tree.GetSum(0, I - 1);
            }

            int RangeSta = I + 4;
            int RangeEnd = ValuesArr.GetUpperBound(0);
            if (RangeSta <= RangeEnd) {
                Cost += CostDictGood[I] + InsSparseTable.Query(RangeSta, RangeEnd);
                AnswerList.Add(Cost);
            }
        }
        return AnswerList.Min();
    }

    // 文字列を引数とし、コスト[開始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の位置のListを返す
    static List<int> GetPosList()
    {
        var PosList = new List<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

// フェニック木
#region Fenwick_Tree
internal class Fenwick_Tree
{
    private long[] mBitArr;
    private long mExternalArrUB;

    // ノードのIndexの列挙を返す
    internal IEnumerable<long> GetNodeIndEnum()
    {
        for (long I = 0; I <= mExternalArrUB; I++) {
            yield return I;
        }
    }

    // 木のノードのUBを返す
    internal long GetUB()
    {
        return mExternalArrUB;
    }

    // コンストラクタ(外部配列のUBのみ指定)
    internal Fenwick_Tree(long pExternalArrUB)
    {
        mExternalArrUB = pExternalArrUB;

        // フェニック木の外部配列は0オリジンで、
        // フェニック木の内部配列は1オリジンなため、2を足す
        mBitArr = new long[pExternalArrUB + 2];
    }

    // コンストラクタ(初期化用の配列指定)
    internal Fenwick_Tree(long[] pArr)
        : this(pArr.GetUpperBound(0))
    {
        for (long I = 0; I <= pArr.GetUpperBound(0); I++) {
            this.Add(I, pArr[I]);
        }
    }

    // コンストラクタ(初期化用のList指定)
    internal Fenwick_Tree(List<long> pList)
        : this(pList.Count - 1)
    {
        for (int I = 0; I <= pList.Count - 1; I++) {
            this.Add(I, pList[I]);
        }
    }

    // Indのチェック
    private void IndCheck(long pInd)
    {
        if (pInd < 0) throw new Exception("pInd < 0");
        if (mExternalArrUB < pInd) throw new Exception("UB < pInd");
    }

    // Indの大小チェック
    private void IndRangeCheck(long pSta, long pEnd)
    {
        IndCheck(pSta);
        IndCheck(pEnd);
        if (pSta > pEnd) throw new Exception("pSta > pEnd");
    }

    // インデクサ
    internal long this[long pInd]
    {
        get { return GetSum(pInd, pInd); }
        set { Add(pInd, value - GetSum(pInd, pInd)); }
    }

    // [pSta,pEnd] のSumを返す
    internal long GetSum(long pSta, long pEnd)
    {
        IndRangeCheck(pSta, pEnd);

        long Result = GetSum(pEnd);
        if (pSta > 0) {
            Result -= GetSum(pSta - 1);
        }
        return Result;
    }

    // [0,pEnd] のSumを返す
    internal long GetSum(long pEnd)
    {
        IndCheck(pEnd);

        pEnd++; // 1オリジンに変更

        long Sum = 0;
        while (pEnd >= 1) {
            Sum += mBitArr[pEnd];
            pEnd -= pEnd & -pEnd;
        }
        return Sum;
    }

    // [I] に Xを加算
    internal void Add(long pI, long pX)
    {
        IndCheck(pI);

        pI++; // 1オリジンに変更

        while (pI <= mBitArr.GetUpperBound(0)) {
            mBitArr[pI] += pX;
            pI += pI & -pI;
        }
    }
}
#endregion