川添さん問題02 スロット・マシン

■■■問題■■■

     

n個のリール (数字が描かれている部分です) を持つスロットマシンを回します。
各リールには、0から9のいずれかの数字がランダムに出ます。
このとき、「最も多く出現した数字の出現回数」に等しいドルが賞金として得られます。

例えばn=6のスロットマシンを考えましょう。
各リールに、左から順に775107という数字が出たとします。
このとき、7の数字が最も多く3回出現していますので、賞金は3ドルです。

リールの数字が020926のとき、賞金は2ドルです。
リールの数字が123456のとき、賞金は1ドルです。
リールの数字が888888のとき、賞金は6ドルです。

このスロットマシンをn回まわしたときの賞金の期待値を F(n)とします。
例えば F(1) = 1，F(2) = 1.1，F(3) = 1.29 となることが確かめられます。

■ 第1問 (Normal)
F(6) の値を求めて下さい (四捨五入は不要です)

■ 第2問 (Hard)
F(12) の値を求めて下さい (四捨五入は不要です)

C#のソース

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

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        for (int N = 1; N <= 12; N++) {
            //数字の組み合わせを列挙
            List<int[]> wkNumCombiArrList = DeriveNumCombiArrList(N);

            //数字の組み合わせごとの賞金合計を求める
            decimal Kitaiti = wkNumCombiArrList.Sum(X => DeriveSyoukinSum(X));

            Kitaiti /= (decimal)Math.Pow(10, N);
            Console.WriteLine("N={0}での期待値={1}", N, Kitaiti);
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

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

    //数字の組み合わせを列挙
    static List<int[]> DeriveNumCombiArrList(int pN)
    {
        var WillReturn = new List<int[]>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (int I = 0; I <= 9; I++) {
            WillPush.CurrNum = I;
            WillPush.NumList = new List<int>() { I };
            stk.Push(WillPush);
        }

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

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

            //Push処理
            for (int I = Popped.CurrNum; I <= 9; I++) {
                WillPush.CurrNum = I;
                WillPush.NumList = new List<int>(Popped.NumList) { I };
                stk.Push(WillPush);
            }
        }
        return WillReturn;
    }

    //数字の組み合わせごとの賞金合計を求める
    static decimal DeriveSyoukinSum(int[] pNumCombiArr)
    {
        //件数の配列
        int[] CntArr = pNumCombiArr.GroupBy(X => X).Select(X => X.Count()).ToArray();

        //最頻値の件数
        decimal ModeCnt = CntArr.Max();

        //同じものを含む順列の公式で件数を求める
        decimal PatternCnt = DeriveKaijyou(pNumCombiArr.Length);
        foreach (int EachInt in CntArr) {
            if (EachInt > 1) PatternCnt /= DeriveKaijyou(EachInt);
        }

        return ModeCnt * PatternCnt;
    }

    //階乗を求める
    static decimal DeriveKaijyou(int pN)
    {
        decimal WillReturn = 1;
        for (int I = 1; I <= pN; I++) {
            WillReturn *= I;
        }
        return WillReturn;
    }
}

C#の実行結果

N=1での期待値=1
N=2での期待値=1.1
N=3での期待値=1.29
N=4での期待値=1.534
N=5での期待値=1.7879
N=6での期待値=2.01966
N=7での期待値=2.22019
N=8での期待値=2.399318
N=9での期待値=2.57237595
N=10での期待値=2.74868911
N=11での期待値=2.9288005274
N=12での期待値=3.10849098132
経過時間=00:00:09.1362083

解説

n=12の場合に、
順列で考えると、10の12乗通りありますので、計算量多すぎですが、
重複組み合わせで、10H12なら、(10-1+12)C12 = 293930通りですので、
ナイーブに解けると判断し、下記の手順で進めてます。

手順1
深さ優先探索で、数字の組み合わせを列挙
(計算量を減らすため、順列ではなく、組み合わせで列挙)

手順2
列挙した数字の組み合わせごとの賞金合計を求める。
最頻値の件数と、
列挙した数字の組み合わせで可能な順列の個数
の積を累計する。

手順3
手順2で求めた累計 / (10のn乗)
が期待値