Problem115 ブロックの組み合わせ方の数え上げ その2

問題

注意: これは Problem114をより難しくした問題である.

長さnユニットからなる 1 列上に, 最低mユニットの長さを持つ赤ブロックが置かれている.
ただしどの赤ブロック同士も, 少なくとも1ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい).

敷き詰め計数関数 F(m, n) は 1列に敷き詰める方法が何通りかを表すとする.
例えば, F(3, 29) = 673135 であり, F(3, 30) = 1089155 である.

m=3 の時, n=30 がこの敷き詰め計数関数が初めて100万を超える最小の値であることが分かる.

同様に, m=10 では F(10, 56) = 880711, F(10, 57) = 1148904 であることがわかり,
つまり n=57 がこの敷き詰め計数関数が初めて100万を超える最小の値であることが分かる.

m=50 のとき, この敷き詰め計数関数が初めて100万を超える最小のnの値を求めよ.

ソース

using System;

class Program
{
    static void Main()
    {
        Console.WriteLine("F({0},{1})={2}", 3, 29, ExecDP(3, 29));
        Console.WriteLine("F({0},{1})={2}", 3, 30, ExecDP(3, 30));
        Console.WriteLine("F({0},{1})={2}", 10, 56, ExecDP(10, 56));
        Console.WriteLine("F({0},{1})={2}", 10, 57, ExecDP(10, 57));

        for (int I = 1; I < int.MaxValue; I++) {
            long wkCnt = ExecDP(50, I);
            Console.WriteLine("F({0},{1})={2}", 50, I, wkCnt);
            if (wkCnt > 1000000) break;
        }
    }

    static long ExecDP(int pM, int pN)
    {
        //場合の数[残りのマス]なDP表
        long[] DPArr = new long[pN + 1];
        DPArr[pN] = 1;

        for (int I = pN; 1 <= I; I--) {
            if (DPArr[I] == 0) continue;

            //赤を敷き詰める場合
            for (int J = pM; J <= pN; J++) {
                int NewI = I - J;

                //マス目が不足する場合
                if (NewI < 0) break;

                //次の黒を敷き詰め
                if (NewI > 0) NewI--;

                DPArr[NewI] += DPArr[I];
            }
            //黒を敷き詰める場合
            DPArr[I - 1] += DPArr[I];
        }
        return DPArr[0];
    }
}

実行結果

省略
F(50,165)=848304
F(50,166)=910165
F(50,167)=978181
F(50,168)=1053389

解説

動的計画法を使ってます。