ARC173-A Neq Number

問題へのリンク

C#のソース

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("3");
            WillReturn.Add("25");
            WillReturn.Add("148");
            WillReturn.Add("998244353");
            //27
            //173
            //2506230721
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        foreach (string EachStr in InputList.Skip(1)) {
            long N = long.Parse(EachStr);

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

            while (L + 1 < R) {
                long Mid = R / 2;
                if (R < long.MaxValue) {
                    Mid = (L + R) / 2;
                }

                long Cnt = DeriveCnt(Mid);

                if (Cnt < N) {
                    L = Mid;
                }
                else {
                    R = Mid;
                }
            }
            Console.WriteLine(R);
        }
    }

    // N以下のNeqNumberの個数を返す
    static long DeriveCnt(long pN)
    {
        string StrN = pN.ToString();

        // 場合の数[0以外登場有無,最後の数字,数字自由フラグ]なDP表
        long[, ,] PrevDP = new long[2, 10, 2];
        PrevDP[0, 0, 0] = 1;

        for (int I = 0; I <= StrN.Length - 1; I++) {
            long[, ,] CurrDP = new long[2, 10, 2];
            for (long J = 0; J <= PrevDP.GetUpperBound(0); J++) {
                for (long K = 0; K <= PrevDP.GetUpperBound(1); K++) {
                    for (long L = 0; L <= 1; L++) {
                        if (PrevDP[J, K, L] == 0) continue;

                        for (char NewChar = '0'; NewChar <= '9'; NewChar++) {
                            if (L == 0 && StrN[I] < NewChar) break;

                            long NewJ = J;
                            if (NewChar != '0' && J == 0) {
                                NewJ = 1;
                            }

                            long NewK = NewChar - '0';
                            if (J == 1 && K == NewChar - '0') {
                                continue;
                            }

                            long NewL = L;
                            if (StrN[I] > NewChar) NewL = 1;

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

        long Answer = PrevDP.Cast<long>().Sum();
        return Answer - 1; // 0の分を引く
    }
}

解説

N以下のNeqNumberの個数を桁DPで調べるメソッドを用意してから、
答えを二分探索してます。