Q53 いたずらされたお菓子

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        //場合の数[御菓子の状態]なDP表
        var PrevDP = new Dictionary<string, long>();
        PrevDP["AAAAAABBBBBBCCCCCCDDDDDDEEEEEE"] = 1;

        for (int I = 1; I <= 5 * 6; I++) {
            string TutumiGami = "";
            if (I <= 6) TutumiGami = "A";
            else if (I <= 12) TutumiGami = "B";
            else if (I <= 18) TutumiGami = "C";
            else if (I <= 24) TutumiGami = "D";
            else TutumiGami = "E";

            var CurrDP = new Dictionary<string, long>();
            foreach (var EachPair in PrevDP) {
                Action<string> UpdateAct = pTarget =>
                {
                    if (pTarget == TutumiGami) return;
                    int wkInd = EachPair.Key.IndexOf(pTarget);
                    if (wkInd == -1) return;

                    string NewKey = EachPair.Key.Remove(wkInd, 1);

                    if (CurrDP.ContainsKey(NewKey)) {
                        CurrDP[NewKey] += EachPair.Value;
                    }
                    else CurrDP[NewKey] = EachPair.Value;
                };
                UpdateAct("A"); UpdateAct("B"); UpdateAct("C");
                UpdateAct("D"); UpdateAct("E");
            }
            PrintDP(CurrDP);
            PrevDP = CurrDP;
        }
        Console.WriteLine("答えは{0}通り", PrevDP[""]);
    }

    static void PrintDP(Dictionary<string, long> pDP)
    {
        foreach (var EachPair in pDP.OrderBy(X => X.Key)) {
            Console.WriteLine("{0}の場合の数={1}", EachPair.Key, EachPair.Value);
        }
    }
}

実行結果

省略
DDの場合の数=103727050595452
DEの場合の数=115332374088864
EEの場合の数=87527929503456
Aの場合の数=481543029347284
Bの場合の数=481543029347284
Cの場合の数=481543029347284
Dの場合の数=481543029347284
Eの場合の数=461329496355456
の場合の数=1926172117389136
答えは1926172117389136通り

解説

String型で状態を管理する動的計画法で解いてます。