パリピ誕生日問題 自分の解法

呼びにくいので適当に名前つけました（ごめんなさい）

何気ない 私の疑問が 東大生インターンを きずつけた pic.twitter.com/Wr96JGtfjm

— Miku Nozaki (@mikupaccho) August 6, 2018

パリピ誕生日問題とは@mikupacchoさんがtwitterでつぶやいていた問題のことです　面白かったので解きました

問題概略(1)
365人の誕生日がかぶらない確率（うるう年は考えない）

解法(1)
一人ずつ見ていき、〇〇人目まで誕生日がかぶらない確率というのを考えていきます。
まず、１人目の誕生日は絶対にかぶらないので確率は1です（1を100%とする）
二人目の誕生日がかぶらない確率は、2人目の誕生日が1人目と異なる確率なので364/365です
同じよぅに考えていくと（365）! / （365）^365になります

問題概略(2)
365日、全ての誕生日が50%以上の確率で集まる最小の人数を求めよ。

解法(2)
今考えている人数で誕生日がコンプリートできるという事をコンプと書くことにします。
N人でコンプ出来る場合、ありえるコンプしたタイミングは365,366,367……N-1,N人目の時です。
なので、N人でコンプできる確率は上記の確率達の合計です。

上記の確率を求める方法を考えます。
たとえば8人目に5種類コンプ出来る確率は
4人目に4種類コンプして、8人目に5種類目をコンプする場合の確率
5人目に4種類コンプして、8人目に5種類目をコンプする場合の確率
6人目に4種類コンプして、8人目に5種類目をコンプする場合の確率
7人目に4種類コンプして、8人目に5種類目をコンプする場合の確率
の合計です。
つまりこれらの確率（〇〇人目に△△種類をコンプする確率）は漸化的に求められます。

dp[i][j]をi人目にj種類をコンプする確率と定義し（動的計画法）、それらを漸化的に埋めていき〇〇人目までに365種類集まる確率を合計していって、50%を超えたiが答えです

高速な実装は実装は思い付けませんでした

ソースコード(java)

package com.company;

import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        long s = System.currentTimeMillis();
        int p = 365;
        int max = 3000;
        //dp[i][j] := i回目にj種類の誕生日が集まる確率（i回より前にj種類埋まる場合は除く）
        double[][] dp = new double[max + 1][p + 1];
        dp[1][1] = 1;
        //選ぶ個数
        for (int cn = 2; cn < p + 1; cn++)
        {
            //選ぶ回数
            for (int k = cn; k < max + 1; k++)
            {
                double res = 0;
                for (int i = 0; i < k - cn + 1; i++)
                {
                    //i回目にj個集まる確率を求めるため
                    //j-1回目にj-1個集まる場合
                    //j回目にj-1個集まる場合
                    //…
                    //…
                    //k-1回目にj-1個集まる場合
                    //の時、k回目にj個集まる確率を合計する
                    double part = 1;
                    //          何回目   //個数
                    part *= dp[cn - 1 + i][cn - 1];
                    //k-1回目までcn-1個しか出ない確率
                    part *= Math.pow((cn - 1) * 1.0 / p, (k - cn - i));
                    //今回あたらしい物が出る確率
                    part *= (p - (cn - 1)) * 1.0 / p;
                    res += part;
                }
                //k回目にcn種類の誕生日が集まる確率
                dp[k][cn] = res;
            }
        }
        double res = 0;
        for (int i = p; i < max + 1; i++)
        {
            //resはi回以内にp種類の誕生日が集まる確率
            res += dp[i][p];
            System.out.println(i + "人いる時 : " + res * 100 + "%");
            if (res >= 0.5)
            {
                long e = System.currentTimeMillis();
                System.out.println("実行時間" + (e - s) / 1000 + "秒");
                return;
            }
        }
    }
}