OUPC2022 I「Huge Bingo」解説

はじめに

「Huge Bingo」writer の Badlylucky です。OUPC2020 時代からの原案を放流しました。

yukicoder 既出¹であり一時は出題が危ぶまれましたが、OUPC2022 は非常に難しい問題が揃ってしまったため全体のバランスを取るために出題することとしました。また、レイドチーム導入の観点では問題数が多い方が望ましいため、その意味でも出題するべきとなりました。

問題

I「Huge Bingo」

$N \times N$ マスの一般的なビンゴのシートが与えられるので、$K$ 回ビンゴのくじを回したときにビンゴができる個数の期待値を求めてください。

解説

Step1: 式を立てる

まず、最終状態の場合の数は $\dbinom{N^2}{K}$ です。

また、ビンゴが $1$ つできる場合の数は $K-N$ 回の試行中に特定の $5$ つ ではない 数字を当て、残りの $N$ 回でぴったりその $5$ つの数字を当てる場合の数と同じなので、$\dbinom{N^2 - N}{K-N}$ です。

それぞれの列にビンゴができる確率変数は独立ではありませんが、期待値の線形性が成り立つためこれにビンゴの数をかけることで問題の期待値を求めることができます。

よって、問題の答えは以下のようになります。

$$
\dfrac{(2N+2)\dbinom{N^2 -N}{K-N}}{\dbinom{N^2}{K}}
$$

Step2: 数学的に考察して高速化する

しかし、これを素直に計算しようとすると $N^2 \leq 9\times10^8$ のため $(9\times10^8)!$ が必要になり、実行時間制限を超過してしまいます。なので、上の式を工夫して高速化します。

二項係数の定義より、上の式は以下のように分解できます。

$$
\dfrac{(2N+2)\dfrac{(N^2 - N)!}{(K-N)!(N^2 - K)!}}{\dfrac{N^{2}!}{K!(N^{2}-K)!}}
$$

これを約分すると、最終的に以下の式になります。

$$
(2N+2)\dfrac{{}_{K}\mathrm{P}_N}{{}_{N^2}\mathrm{P}_N}
$$

${}_{K}\mathrm{P}_N = K \times (K-1) \times \dots \times (K-N+1)$、${}_{N^2}\mathrm{P}_N = N^2 \times (N^2 - 1) \times \dots \times (N^2 - N + 1)$ なので、この式の計算は $\mathrm{O}(N)$ でできます。よって、時間内に解を求めることができるようになりました。

ただし $K<N$ のときがコーナーケースとなり、ビンゴができないので期待値は $0$ となります。

Step2 の Python での実装例を以下に示します。

#!/usr/bin/env python3
MOD = int(1e9+7)
N, K = map(int, input().split())
if K < N:
    print(0)
    exit(0)
X = 1
Y = 2 * N + 2
for i in range(N):
    X = (X * (N * N - i)) % MOD
    Y = (Y * (K - i)) % MOD
Z = (Y * pow(X, MOD - 2, MOD)) % MOD
print(Z)

1. No.242 ビンゴゲーム。これ自体は解説にある高速化技法を使わなくても解けるが、sugarknri さんによる解説によってこの高速化手法が指摘されている。 ↩