Q15 階段で立ち話

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        //const int UB = 4;
        const int UB = 10;

        //場合の数[Aの位置,Bの位置]なDP表
        int[,] PrevDP = new int[UB + 1, UB + 1];
        PrevDP[0, UB] = 1;

        int AnswerCnt = 0;
        while (true) {
            bool WillBreak = true;
            int[,] CurrDP = new int[UB + 1, UB + 1];

            Action<int, int> DeriveNextPattern = (pI, pJ) =>
            {
                for (int NewI = pI + 1; NewI <= pI + 4; NewI++) {
                    if (UB < NewI) break;
                    for (int NewJ = pJ - 1; pJ - 4 <= NewJ; NewJ--) {
                        if (NewJ < 0) break;
                        CurrDP[NewI, NewJ] += PrevDP[pI, pJ];
                    }
                }
            };

            for (int I = 0; I <= UB; I++) {
                for (int J = I + 1; J <= UB; J++) {
                    if (PrevDP[I, J] == 0) continue;
                    DeriveNextPattern(I, J);
                    WillBreak = false;
                }
            }
            if (WillBreak) break;
            //PrintDP(CurrDP);

            //解を計上する
            for (int I = 0; I <= UB; I++) {
                AnswerCnt += CurrDP[I, I];
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(AnswerCnt);
    }

    static void PrintDP(int[,] pCurrDP)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= pCurrDP.GetUpperBound(0); I++) {
            for (int J = 0; J <= pCurrDP.GetUpperBound(1); J++) {
                if (pCurrDP[I, J] > 0) {
                    sb.AppendFormat("Aが{0},Bが{1}が{2}通り", I, J, pCurrDP[I, J]);
                    sb.AppendLine();
                }
            }
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

201

解説

場合の数を更新する動的計画法で解いてます。