Problem113 非はずみ数

問題

ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき,
その数を増加数 (increasing number) と呼ぶ;
例えば134468は増加数である.

同様に, 任意の桁の数が自身の右にある桁の数以上であるとき,
その数を減少数 (decreasing number) と呼ぶ;
例えば66420がそうである.

増加数でも減少数でもない正の整数を "はずみ"数 ("bouncy" number) と呼ぶ;
155349がそうである.

nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる.
例えば, 100万未満では, はずみ数でない数は12951個しかない.
同様に, 100億未満では277032個しかない.

googol数 (10の100乗) 未満ではずみ数でない数の個数を答えよ.

ソース

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        Solve(6);
        Solve(10);
        Solve(100);
    }

    static void Solve(int pKetaSuuJyougen)
    {
        Console.WriteLine("{0}桁未満の数で検証します。", pKetaSuuJyougen);

        long ZoukasuuCnt = DeriveZoukasuuCnt(pKetaSuuJyougen);
        long GensyousuuCnt = DeriveGensyousuuCnt(pKetaSuuJyougen);
        Console.WriteLine("増加数は、{0}個", ZoukasuuCnt);
        Console.WriteLine("減少数は、{0}個", GensyousuuCnt);

        int KyoutuuCnt = 9 * pKetaSuuJyougen;
        Console.WriteLine("増加数かつ減少数は、{0}個", KyoutuuCnt);

        Console.WriteLine("非はずみ数は、{0}個", ZoukasuuCnt + GensyousuuCnt - KyoutuuCnt);
        Console.WriteLine();
    }

    //増加数の個数を求める
    static long DeriveZoukasuuCnt(int pKetaSuuJyougen)
    {
        //場合の数[現在の桁の数字]なDP表
        long[] PrevDP = new long[10];

        for (int I = 1; I <= 9; I++)
            PrevDP[I] = 1;

        long WillReturn = PrevDP.Sum();

        for (int I = 2; I <= pKetaSuuJyougen; I++) {
            long[] CurrDP = new long[10];

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

                for (int K = J; K <= 9; K++)
                    CurrDP[K] += PrevDP[J];
            }
            WillReturn += CurrDP.Sum();
            PrevDP = CurrDP;
        }
        return WillReturn;
    }

    //減少数の個数を求める
    static long DeriveGensyousuuCnt(int pKetaSuuJyougen)
    {
        //場合の数[現在の桁の数字]なDP表
        long[] PrevDP = new long[10];

        long WillReturn = 0;

        for (int I = 1; I <= 9; I++) {
            PrevDP[I] = 1;
            //減少数は、右に0を付加した分も計上する
            int RestKetaSuu = pKetaSuuJyougen - 1;
            WillReturn += 1 + RestKetaSuu;
        }

        for (int I = 2; I <= pKetaSuuJyougen; I++) {
            long[] CurrDP = new long[10];

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

                for (int K = J; 1 <= K; K--)
                    CurrDP[K] += PrevDP[J];
            }

            foreach (long EachLong in CurrDP) {
                //減少数は、右に0を付加した分も計上する
                int RestKetaSuu = pKetaSuuJyougen - I;
                WillReturn += EachLong * (RestKetaSuu + 1);
            }
            PrevDP = CurrDP;
        }
        return WillReturn;
    }
}

実行結果

6桁未満の数で検証します。
増加数は、5004個
減少数は、8001個
増加数かつ減少数は、54個
非はずみ数は、12951個

10桁未満の数で検証します。
増加数は、92377個
減少数は、184745個
増加数かつ減少数は、90個
非はずみ数は、277032個

100桁未満の数で検証します。
増加数は、4263421511270個
減少数は、46897636623880個
増加数かつ減少数は、900個
非はずみ数は、51161058134250個

解説

個数定理
n(A∪B) = n(A) + n(B) - n(A∩B)
をふまえて

桁DPで、増加数と減少数の個数を求めてから、
増加数かつ減少数の個数を引いてます。