🎱

2022/12/26に公開

# 解法

``````import math

N = 200
M = 63
K = 16

# dp1[i][j] := バケツ i までに、各バケツ K 個以下、合計 j 個のボールを入れる場合の数
dp1 = [[0] * (N + 1) for _ in range(M + 1)]
# dp2[i][j] := バケツ i までに、合計 j 個のボールを入れる場合の数
dp2 = [[0] * (N + 1) for _ in range(M + 1)]
dp1[0][0] = 1
dp2[0][0] = 1
for i in range(M):
for j in range(N + 1):
for x in range(N + 1):
if j + x <= N:
c = math.comb(N - j, x)  # バケツ i+1 に入れる x 個のボールの選び方
if x <= K:
dp1[i + 1][j + x] += dp1[i][j] * c
dp2[i + 1][j + x] += dp2[i][j] * c

print(1.0 - dp1[M][N] / dp2[M][N])  # 1.8985225437306852e-06
``````

# シミュレーション

``````package main

import (
"fmt"
"math/rand"
"sync"
"sync/atomic"
)

func main() {
const T = 16
const U = 6250000
const N = 200
const M = 63
const K = 16

var overflowCount uint64
var wg sync.WaitGroup

for t := 0; t < T; t++ {
go func(seed int64) {
r := rand.New(rand.NewSource(seed))
for u := 0; u < U; u++ {
var a [M]int
overflow := false
for j := 0; j < N; j++ {
p := r.Int31n(M)
a[p] += 1
if a[p] > K {
overflow = true
break
}
}
if overflow {
}
}

wg.Done()
}(int64(t))
}

wg.Wait()
total := uint64(T) * uint64(U)
fmt.Printf(
"%v / %v = %.10f\n",
overflowCount,
total,
float64(overflowCount)/float64(total),
)

// U = 6250000
// 211 / 100000000 = 0.0000021100

// U = 62500000
// 1902 / 1000000000 = 0.0000019020

// U = 625000000
// 18897 / 10000000000 = 0.0000018897
}
``````