Problem178 ステップ数

問題

45656を考えよう. 連続する2桁の数は全て差の絶対値が1である.

連続する2桁の数の差の絶対値が全て1である数をステップ数と呼ぶ.
パンデジタル数では0から9の各数が少なくとも1回出現する.

10の40乗未満の数でパンデジタル数かつステップ数であるものの数を答えよ.

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal bool IsAppearedNonZero; //0以外の登場有無
        internal int LastNum; //最後の数字
        internal bool[] IsAppearedArr; //0から9の登場有無
    }

    static string GetHash(JyoutaiDef pJyoutai)
    {
        var sb = new System.Text.StringBuilder();
        sb.Append(pJyoutai.IsAppearedNonZero ? '1' : '0');
        sb.Append(pJyoutai.LastNum);
        foreach (bool EachBool in pJyoutai.IsAppearedArr) {
            sb.Append(EachBool ? '1' : '0');
        }
        return sb.ToString();
    }

    static JyoutaiDef GetJyoutai(string pHash)
    {
        JyoutaiDef WillReturn;
        WillReturn.IsAppearedNonZero = pHash[0] == '1';
        WillReturn.LastNum = pHash[1] - '0';
        WillReturn.IsAppearedArr = new bool[10];
        for (int I = 0; I <= WillReturn.IsAppearedArr.GetUpperBound(0); I++) {
            WillReturn.IsAppearedArr[I] = pHash[I + 2] == '1';
        }
        return WillReturn;
    }

    static void Main()
    {
        //場合の数[状態のハッシュ値]なDP表
        var PrevDP = new Dictionary<string, long>();
        PrevDP.Add(new string('0', 1 + 1 + 10), 1);

        for (int I = 1; I <= 40; I++) {
            var CurrDP = new Dictionary<string, long>();
            foreach (var EachPair in PrevDP) {
                for (int J = 0; J <= 9; J++) {
                    JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);

                    if (CurrJyoutai.IsAppearedNonZero) {
                        if (Math.Abs(CurrJyoutai.LastNum - J) != 1) continue;

                        CurrJyoutai.IsAppearedArr[J] = true;
                        CurrJyoutai.LastNum = J;
                    }
                    else if (J != 0) {
                        CurrJyoutai.IsAppearedNonZero = true;
                        CurrJyoutai.IsAppearedArr[J] = true;
                        CurrJyoutai.LastNum = J;
                    }

                    string wkKey = GetHash(CurrJyoutai);
                    if (CurrDP.ContainsKey(wkKey)) {
                        CurrDP[wkKey] += EachPair.Value;
                    }
                    else CurrDP[wkKey] = EachPair.Value;
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = 0;
        foreach (var EachPair in PrevDP) {
            JyoutaiDef wkJyoutai = GetJyoutai(EachPair.Key);
            if (Array.TrueForAll(wkJyoutai.IsAppearedArr, X => X))
                Answer += EachPair.Value;
        }
        Console.WriteLine("解は{0}通り", Answer);
    }
}

実行結果

解は126461847755通り

解説

桁DPで解いてます。