結果

問題 No.3299 K-th MMA String
コンテスト
ユーザー aketijyuuzou
提出日時 2025-10-17 19:59:00
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 4,010 bytes
コンパイル時間 7,793 ms
コンパイル使用メモリ 169,424 KB
実行使用メモリ 191,728 KB
最終ジャッジ日時 2025-10-17 19:59:11
合計ジャッジ時間 10,635 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (106 ミリ秒)。
  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;

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

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3 1");
            //MMA
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 3");
            //MMAM
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("15 25505");
            //MMAMMAMMAMMAMMA
        }
        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 long mN;
    static long mK;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        mN = wkArr[0];
        mK = wkArr[1];

        long L = 0;
        long R = long.MaxValue;

        while (L + 1 < R) {
            //Console.WriteLine("L={0},R={1}", L, R);
            long Mid = R / 2;
            if (R < long.MaxValue) {
                Mid = (L + R) / 2;
            }

            if (CanAchieve(Mid)) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }

        string Answer = Convert.ToString(R, 2);
        Answer = Answer.Replace('1', 'M');
        Answer = Answer.Replace('0', 'A');
        Answer = Answer.PadLeft((int)mN, 'A');
        Console.WriteLine(Answer);
    }

    // Limitを引数として、Limit以下で110を含む2進数の個数が、K以上かを返す
    static bool CanAchieve(long pLimit)
    {
        string BinStr = Convert.ToString(pLimit, 2);
        char[] BinArr = BinStr.ToCharArray();

        long UB = BinArr.GetUpperBound(0);

        // 場合の数[Limit未満確定フラグ,110の登場有無,1つ上の桁の数,2つ上の桁の数]なDP表
        long[, , ,] PrevDP = new long[2, 2, 2, 2];
        PrevDP[0, 0, 0, 0] = 1;

        for (long I = 0; I <= UB; I++) {
            long[, , ,] CurrDP = new long[2, 2, 2, 2];
            for (long J = 0; J <= 1; J++) {
                for (long K = 0; K <= 1; K++) {
                    for (long L = 0; L <= 1; L++) {
                        for (long M = 0; M <= 1; M++) {
                            if (PrevDP[J, K, L, M] == 0) continue;

                            for (char NewChar = '0'; NewChar <= '1'; NewChar++) {
                                if (J == 0 && BinArr[I] < NewChar) continue;

                                long NewJ = J;
                                if (BinArr[I] > NewChar) NewJ = 1;

                                int CurrNum = NewChar - '0';
                                long NewK = K;
                                if (M == 1 && L == 1 && CurrNum == 0) {
                                    NewK = 1;
                                }

                                long NewL = CurrNum;
                                long NewM = L;

                                CurrDP[NewJ, NewK, NewL, NewM] += PrevDP[J, K, L, M];
                            }
                        }
                    }
                }
            }
            PrevDP = CurrDP;
        }

        long Cnt_110 = 0;
        for (long J = 0; J <= 1; J++) {
            for (long K = 0; K <= 1; K++) {
                for (long L = 0; L <= 1; L++) {
                    for (long M = 0; M <= 1; M++) {
                        if (K == 1) {
                            Cnt_110 += PrevDP[J, K, L, M];
                        }
                    }
                }
            }
        }

        //Console.WriteLine("{0}以下の110を含む数は{1}通り", pLimit, Cnt_110);
        return Cnt_110 >= mK;
    }
}
0