ABC387-C Snake Numbers

問題へのリンク

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("97 210");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1000 9999");
            //2025
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("252509054433933519 760713016476190692");
            //221852052834757
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        long L = wkArr[0];
        long R = wkArr[1];

        long CntL = ExecDP(L - 1);
        long CntR = ExecDP(R);

        Console.WriteLine(CntR - CntL);
    }

    // 桁DPで引数以下のヘビ数の個数を返す
    static long ExecDP(long pLimit)
    {
        string StrN = pLimit.ToString();

        // 場合の数[使える数の最大値,数字自由フラグ]なDP表
        long[,] PrevDP = new long[10, 2];
        PrevDP[9, 0] = 1;

        for (int I = 0; I <= StrN.Length - 1; I++) {
            long[,] CurrDP = new long[10, 2];

            for (int J = 0; J <= PrevDP.GetUpperBound(0); J++) {
                for (int K = 0; K <= 1; K++) {
                    if (PrevDP[J, K] == 0) continue;

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

                        int NewK = K;
                        if (StrN[I] > NewChar) NewK = 1;

                        int NewJ = NewChar - '0';
                        if (J == 9) {
                            if (NewJ > 0) {
                                NewJ--;
                            }
                            else {
                                NewJ = 9;
                            }
                        }
                        else {
                            if (J < NewJ) continue;
                            NewJ = J;
                        }

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

        long Answer = 0;
        for (int J = 0; J <= PrevDP.GetUpperBound(0); J++) {
            for (int K = 0; K <= 1; K++) {
                if (J < 9) {
                    Answer += PrevDP[J, K];
                }
            }
        }

        return Answer;
    }
}

解説

引数以下のヘビ数を
場合の数[使える数の最大値,数字自由フラグ]な桁DPで求めるメソッドを作ってます。
「使える数の最大値」の初期値を9とし、前ゼロに対応してます。