Q09 つりあわない男女

C#のソース

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        const int MenCnt = 20;
        const int WomenCnt = 10;

        //場合の数[男の数][女の数]なDP表
        var PrevDP = new Nullable<int>[MenCnt + 1, WomenCnt + 1];
        PrevDP[0, 0] = 1;

        for (int I = 1; I <= MenCnt + WomenCnt - 1; I++) {
            var CurrDP = new Nullable<int>[MenCnt + 1, WomenCnt + 1];

            for (int X = 0; X <= MenCnt; X++) {
                for (int Y = 0; Y <= WomenCnt; Y++) {
                    if (PrevDP[X, Y] == null) continue;

                    Action<int, int> UpdateAct = (pNewIndX, pNewIndY) =>
                    {
                        //上限超えはNG
                        if (MenCnt < pNewIndX) return;
                        if (WomenCnt < pNewIndY) return;

                        //左が男女同数ならNG
                        if (pNewIndX == pNewIndY) return;
                        //右が男女同数ならNG
                        if (MenCnt - pNewIndX == WomenCnt - pNewIndY) return;

                        //和の法則でDP表を更新
                        CurrDP[pNewIndX, pNewIndY] =
                            (CurrDP[pNewIndX, pNewIndY] ?? 0) + PrevDP[X, Y].Value;
                    };

                    //男を追加する場合
                    UpdateAct(X + 1, Y);

                    //女を追加する場合
                    UpdateAct(X, Y + 1);
                }
            }
            PrevDP = CurrDP;
            Console.WriteLine("{0}回目のDPの結果", I);
            PrintDP(PrevDP);
        }
        Console.WriteLine("解は{0}通り", PrevDP.Cast<int?>().Sum(X => X ?? 0));
    }

    static void PrintDP(Nullable<int>[,] pDP)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= pDP.GetUpperBound(0); I++) {
            for (int J = 0; J <= pDP.GetUpperBound(1); J++) {
                if ((pDP[I, J] ?? 0) > 0) {
                    sb.AppendFormat("男{0}人、女{1}人での並びが{2}通り",
                        I, J, pDP[I, J].Value);
                    sb.AppendLine();
                }
            }
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

省略
25回目のDPの結果
男15人、女10人での並びが621875通り
男16人、女9人での並びが479941通り
男17人、女8人での並びが177859通り

26回目のDPの結果
男16人、女10人での並びが1101816通り
男17人、女9人での並びが657800通り

27回目のDPの結果
男17人、女10人での並びが1759616通り
男18人、女9人での並びが657800通り

28回目のDPの結果
男18人、女10人での並びが2417416通り

29回目のDPの結果
男19人、女10人での並びが2417416通り

解は2417416通り

解説

場合の数を順次求めていく、動的計画法を使ってます。