No.567 コンプリート

■■■問題■■■

6面のサイコロをn回投げます。サイコロの目が全て出る確率を求めて下さい。

■■■入力■■■

N

●1 <= N <= 100万

■■■出力■■■

n回投げて全ての面が出る確率を出力してください
絶対誤差または相対誤差が10の-7乗以下なら許容されます。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("1");
            //0
            //1回投げて全部揃うことはありません
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            //0.015432098765432
            //(1/6)の6乗 * 6の階乗
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("7");
            //0.054012345
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("50");
            //0.99934071
            //このくらいになるとほぼ確実に全て出ますね
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        //確率[登場した目の数]なDP表
        double[] PrevDP = new double[7];
        PrevDP[0] = 1D;

        for (int I = 1; I <= N; I++) {
            double[] CurrDP = new double[7];

            for (int J = 0; J <= 6; J++) {
                //登場した目の数が増えない確率
                double HuenaiP = J / 6D;
                CurrDP[J] += PrevDP[J] * HuenaiP;

                //登場した目の数が1増える確率
                double HueruP = 1D - HuenaiP;

                if (J <= 5) {
                    CurrDP[J + 1] += PrevDP[J] * HueruP;
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[6]);
    }
}

解説

登場した目の数が0個の状態でサイコロを振ると
6/6の確率で、登場した目の数が1個になります。

登場した目の数が1個の状態でサイコロを振ると
5/6の確率で、登場した目の数が2個になります。

登場した目の数が2個の状態でサイコロを振ると
4/6の確率で、登場した目の数が3個になります。

登場した目の数が3個の状態でサイコロを振ると
3/6の確率で、登場した目の数が4個になります。

登場した目の数が4個の状態でサイコロを振ると
2/6の確率で、登場した目の数が5個になります。

登場した目の数が5個の状態でサイコロを振ると
1/6の確率で、登場した目の数が6個になります。

以上をふまえて、動的計画法で解いてます。