Problem116 赤タイル, 緑タイル, あるいは青タイル

問題

5個の黒い正方形のタイルの列を, 赤(長さ2), 緑(長さ3), 青(長さ4)から選んで,
この色のついた長方形のタイルでいくつか置き換える.

赤のタイルを選んだ場合は, ちょうど 7通りの方法がある.


緑のタイルを選んだ場合は, 3通りである.


青のタイルを選んだ場合は, 2通りである.


複数の色を混ぜられない場合は,
5ユニットの長さの1列に並んだ黒いタイルを置き換える方法は 7+3+2 = 12 通りある.

50ユニットの長さの1列に並んだ黒いタイルを置き換える方法は何通りあるか.
ただし複数の色を混ぜることはできず, 少なくとも1個は色のついたタイルを使うこと.

ソース

using System;

class Program
{
    //const int Unit = 5;
    const int Unit = 50;

    static void Main()
    {
        long CntRed = ExecDP(2);
        Console.WriteLine("赤タイルを使うと{0}通り", CntRed);

        long CntGreen = ExecDP(3);
        Console.WriteLine("緑タイルを使うと{0}通り", CntGreen);

        long CntBlue = ExecDP(4);
        Console.WriteLine("青タイルを使うと{0}通り", CntBlue);

        Console.WriteLine("合計で{0}通り", CntRed + CntGreen + CntBlue);
    }

    static long ExecDP(int pM)
    {
        //場合の数[残りのマス,色タイルの使用有無]なDP表
        long[,] DPArr = new long[Unit + 1, 1 + 1];
        DPArr[Unit, 0] = 1;

        for (int I = Unit; 1 <= I; I--) {
            for (int J = 0; J <= 1; J++) {
                if (DPArr[I, J] == 0) continue;

                //色タイルを使う場合
                int NewI = I - pM;
                if (NewI >= 0) {
                    DPArr[NewI, 1] += DPArr[I, J];
                }

                //黒タイルを使う場合
                DPArr[I - 1, J] += DPArr[I, J];
            }
        }
        return DPArr[0, 1];
    }
}

実行結果

赤タイルを使うと20365011073通り
緑タイルを使うと122106096通り
青タイルを使うと5453760通り
合計で20492570929通り

解説

動的計画法で解いてます。