Problem240 上位のサイコロ

問題

6面のサイコロ(各面は 1 から 6)を 5 個振って,
上位 3 個の合計が 15 となる場合は 1111 通りある.
いくつか例を挙げる:

D1,D2,D3,D4,D5 = 4,3,6,3,5
D1,D2,D3,D4,D5 = 4,3,3,5,6
D1,D2,D3,D4,D5 = 3,3,3,6,6
D1,D2,D3,D4,D5 = 6,6,3,3,3

12面のサイコロ(各面は 1 から 12)を 20 個振って,
上位 10 個の合計が 70 となる場合は何通りあるか.

ソース

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

class Program
{
    static void Main()
    {
        Solve(6, 5, 3, 15);
        Solve(12, 20, 10, 70);
    }

    static void Solve(int pMenCnt, int pShikouCnt, int pTopN, int pNeedSum)
    {
        //深さ優先探索で上位N件の組み合わせを求める
        List<int[]> TopNPatternArrList = DeriveTopNPatternArrList(pMenCnt, pTopN, pNeedSum);

        long Answer = 0;
        foreach (int[] EachTopNPatternArr in TopNPatternArrList) {
            int TopNPatternMin = EachTopNPatternArr.Min();
            int TopNPatternMinCnt = EachTopNPatternArr.Count(X => X == TopNPatternMin);

            int TopNPatternNonMinCnt = EachTopNPatternArr.Length - TopNPatternMinCnt;

            //TopNの最小値の個数で場合分け
            for (int I = TopNPatternMinCnt; I <= pShikouCnt - TopNPatternNonMinCnt; I++) {
                //残りのマス数
                int RestMasuCnt = pShikouCnt;

                //現在の場合の数
                long CurrPatternCnt = 1;

                var Query = EachTopNPatternArr.GroupBy(X => X);
                foreach (var EachItem in Query) {
                    if (EachItem.Key == TopNPatternMin) {
                        CurrPatternCnt *= DeriveCombi(RestMasuCnt, I);
                        RestMasuCnt -= I;
                    }
                    else {
                        CurrPatternCnt *= DeriveCombi(RestMasuCnt, EachItem.Count());
                        RestMasuCnt -= EachItem.Count();
                    }
                }
                //残りのマスがある場合
                if (RestMasuCnt > 0) {
                    //埋める数字がない場合
                    if (TopNPatternMin == 1) continue;

                    //TopNの最小値未満での重複順列
                    for (int J = 1; J <= RestMasuCnt; J++) {
                        CurrPatternCnt *= (TopNPatternMin - 1);
                    }
                }

                //var sb = new System.Text.StringBuilder();
                //sb.AppendFormat("Top{0}が", pTopN);
                //Array.ForEach(EachTopNPatternArr, X => sb.AppendFormat("{0},", X));
                //sb.AppendFormat("TopNの最小値である{0}の使用回数が{1}だと、", TopNPatternMin, I);
                //sb.AppendFormat("{0}通り", CurrPatternCnt);
                //Console.WriteLine(sb.ToString());

                Answer += CurrPatternCnt;
            }
        }
        Console.WriteLine("面数{0}、試行回数{1}、上位{2}件、合計{3}での解は{4}",
            pMenCnt, pShikouCnt, pTopN, pNeedSum, Answer);
    }

    struct JyoutaiDef
    {
        internal int CurrNum;
        internal int SumVal;
        internal List<int> NumList;
    }

    //深さ優先探索で上位N件の組み合わせを求める
    static List<int[]> DeriveTopNPatternArrList(int pMenCnt, int pTopN, int pNeedSum)
    {
        var WillReturn = new List<int[]>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrNum = 1;
        WillPush.SumVal = 0;
        WillPush.NumList = new List<int>();
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //クリア判定
            if (Popped.NumList.Count == pTopN) {
                if (Popped.SumVal == pNeedSum) {
                    WillReturn.Add(Popped.NumList.ToArray());
                }
                continue;
            }

            for (int I = Popped.CurrNum; I <= pMenCnt; I++) {
                WillPush.CurrNum = I;
                WillPush.SumVal = Popped.SumVal + I;

                //枝切り
                if (WillPush.SumVal > pNeedSum) break;

                WillPush.NumList = new List<int>(Popped.NumList);
                WillPush.NumList.Add(I);
                Stk.Push(WillPush);
            }
        }
        return WillReturn;
    }

    //nCrを求める
    static long DeriveCombi(int pN, int pR)
    {
        long WillReturn = 1;
        pR = Math.Min(pR, pN - pR);

        for (int I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;
        }
        for (int I = 2; I <= pR; I++) {
            WillReturn /= I;
        }
        return WillReturn;
    }
}

実行結果

面数6、試行回数5、上位3件、合計15での解は1111
面数12、試行回数20、上位10件、合計70での解は7448717393364181966

解説

深さ優先探索で上位N件の組み合わせ候補を求めてから、
組み合わせの最小値の個数で場合分けしてます。