Problem205 サイコロゲーム

問題

ピーターは4面のサイコロを9つ持っている. サイコロの各面には1, 2, 3, 4と書いてある.
コリンは6面のサイコロを6つ持っている. サイコロの各面には1, 2, 3, 4, 5, 6と書いてある.

ピーターとコリンはサイコロを投じ, 出た目の合計を比べる.
合計が多い方が勝ちである. もし出た目の合計が等しければ勝負は引き分けになる.

ピーターがコリンに勝つ確率はいくつだろうか?
10進7桁にroundし, 0.abcdefgという形で回答欄に入力せよ.

ソース(4進数と9進数を使う方法)

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

class Program
{
    static void Main()
    {
        Action<Dictionary<int, int>, int> MergeVal = (pDict, pVal) =>
        {
            if (pDict.ContainsKey(pVal)) pDict[pVal]++;
            else pDict[pVal] = 1;
        };

        var PeterCaseCntDict = new Dictionary<int, int>();
        for (int I = 0; I <= (int)Math.Pow(4D, 9D) - 1; I++)
            MergeVal(PeterCaseCntDict, CalcSum(I, 4, 9));

        var ColinCaseCntDict = new Dictionary<int, int>();
        for (int I = 0; I <= (int)Math.Pow(6D, 6D) - 1; I++)
            MergeVal(ColinCaseCntDict, CalcSum(I, 6, 6));

        decimal SumCaseCnt = (decimal)ColinCaseCntDict.Values.Sum() *
                             (decimal)PeterCaseCntDict.Values.Sum();

        decimal WinCaseCnt = 0M;
        foreach (int EachColin in ColinCaseCntDict.Keys) {
            foreach (int EachPeter in PeterCaseCntDict.Keys.Where(X => X > EachColin)) {
                WinCaseCnt += (decimal)ColinCaseCntDict[EachColin] *
                              (decimal)PeterCaseCntDict[EachPeter];
            }
        }
        Console.WriteLine(Math.Round(WinCaseCnt / SumCaseCnt, 7, MidpointRounding.AwayFromZero));
    }

    static int CalcSum(int pTarget, int pShinsuu, int pSaikoroCnt)
    {
        int WillReturn = 0;
        for (int I = 1; I <= pSaikoroCnt; I++) {
            WillReturn += pTarget % pShinsuu + 1;
            pTarget /= pShinsuu;
        }
        return WillReturn;
    }
}

ソース(ListジェネリックのForEachメソッドで組み合わせを求める方法)

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

class Program
{
    static void Main()
    {
        var PeterCaseCntDict = DeriveSumList(4, 9).GroupBy(A => A)
           .ToDictionary(A => A.Key, A => A.Count());
        var ColinCaseCntDict = DeriveSumList(6, 6).GroupBy(A => A)
           .ToDictionary(A => A.Key, A => A.Count());

        decimal SumCaseCnt = (decimal)ColinCaseCntDict.Values.Sum()
                           * (decimal)PeterCaseCntDict.Values.Sum();

        decimal WinCaseCnt = 0M;
        foreach (int EachColin in ColinCaseCntDict.Keys) {
            foreach (int EachPeter in PeterCaseCntDict.Keys.Where(X => X > EachColin)) {
                WinCaseCnt += (decimal)ColinCaseCntDict[EachColin]
                        * (decimal)PeterCaseCntDict[EachPeter];
            }
        }
        Console.WriteLine(Math.Round(WinCaseCnt / SumCaseCnt, 7, MidpointRounding.AwayFromZero));
    }

    static List<int> DeriveSumList(int pDiceMaxVal, int pN)
    {
        var SumList = Enumerable.Range(1, pDiceMaxVal).ToList();
        for (int N = 1; N <= pN - 1; N++) {
            var NewSumList = new List<int>();
            SumList.ForEach(Any =>
            {
                for (int Val = 1; Val <= pDiceMaxVal; Val++)
                    NewSumList.Add(Any + Val);
            });
            SumList = NewSumList;
        }
        return SumList;
    }
}

ソース(Stackジェネリックで組み合わせを求める方法)

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

class Program
{
    static void Main()
    {
        var PeterCaseCntDict = DeriveCaseCntDict(4, 9);
        var ColinCaseCntDict = DeriveCaseCntDict(6, 6);

        decimal SumCaseCnt = (decimal)ColinCaseCntDict.Values.Sum()
                           * (decimal)PeterCaseCntDict.Values.Sum();

        decimal WinCaseCnt = 0M;
        foreach (int EachColin in ColinCaseCntDict.Keys) {
            foreach (int EachPeter in PeterCaseCntDict.Keys.Where(X => X > EachColin)) {
                WinCaseCnt += (decimal)ColinCaseCntDict[EachColin]
                            * (decimal)PeterCaseCntDict[EachPeter];
            }
        }
        Console.WriteLine(Math.Round(WinCaseCnt / SumCaseCnt, 7, MidpointRounding.AwayFromZero));
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal int SumVal;
    };

    static Dictionary<int, int> DeriveCaseCntDict(int pDiceMaxVal, int pN)
    {
        var WillReturn = new Dictionary<int, int>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        for (int Val = 1; Val <= pDiceMaxVal; Val++) {
            WillPush.Level = 1;
            WillPush.SumVal = Val;
            Stk.Push(WillPush);
        }

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();
            if (Popped.Level == pN) {
                if (WillReturn.ContainsKey(Popped.SumVal))
                    WillReturn[Popped.SumVal]++;
                else WillReturn[Popped.SumVal] = 1;
                continue;
            }

            WillPush.Level = Popped.Level + 1;
            for (int Val = 1; Val <= pDiceMaxVal; Val++) {
                WillPush.SumVal = Popped.SumVal + Val;
                Stk.Push(WillPush);
            }
        }
        return WillReturn;
    }
}

実行結果

0.5731441

解説

Stackジェネリックで深さ優先探索をするのが一番分かりやすいと思います。