ABC-007-D 禁止された数字

■■■問題■■■

たかはし王国の国王であるたかはし君主は数字の4と9が大嫌いです。
それらの数字を国内で目にするだけで気分が悪いので、それらを使ってはいけないという法律を定めました。
この法律を破ってしまうと罰せられます。

数字が禁止されているので、ある数の10進表現を考えたとき、
いずれかの桁に禁止された数字が1つでも含まれている場合、その数を使うことはできません。

今まで使っていた数字を使えなくなったあなたは、うっかり使ってしまって罰せられては困るので、
使う可能性がある数の区間 [A,B]={A,A+1,A+2, ・・・ ,B} に、
いくつ禁止された数が含まれているかを確かめることにしました。
そのためのプログラムを作ってください。

■■■入力■■■

A B

1行目には、整数 A,B (1 <= A <= B <= 10の18乗) が空白区切りで与えられる。

■■■出力■■■

区間 [A,B] に含まれる禁止された数がいくつ含まれているかを1行に出力せよ。
出力の末尾に改行をいれること。

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("1 9");
            //2
            //4と9が禁止されています。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("40 49");
            //10
            //40から49は全て禁止された数です。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 1000");
            //488
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("1 1000000000000000000");
            //981985601490518016
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string[] wkArr = InputList[0].Split(' ');
        string A = wkArr[0];
        string B = wkArr[1];

        long CntA = ExecDP(A);
        long CntB = ExecDP(B);

        long CntCommon = 0;
        if (A.Contains('4') || A.Contains('9'))
            CntCommon = 1;

        Console.WriteLine(CntB - CntA + CntCommon);
    }

    //0から引数までの4または9を含んだ数の個数を返す
    static long ExecDP(string pStr)
    {
        //場合の数[4または9の存在フラグ,数字自由フラグ]なDP表
        long[,] PrevDP = new long[2, 2];
        PrevDP[0, 0] = 1;

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

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

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

                        int NewJ = J;
                        if (NewChar == '4') NewJ = 1;
                        if (NewChar == '9') NewJ = 1;

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

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

        long Answer = 0;
        Answer += PrevDP[1, 0];
        Answer += PrevDP[1, 1];
        return Answer;
    }
}

解説

桁DPで解いてます。