ビンゴの確率を求めよう（１）

TL;DR

数え上げの問題。AtCoderの緑コーダーくらいなら解けると思います。
github
magicodeとやらにも上げてみてます。

Intro

みなさんは子供の頃や、宴会の席などでビンゴをやったことがあるでしょう。一番最初にビンゴになった人は歓喜に湧いてアドレナリンが大量に分泌されることとなっていた記憶があります。

……冗談はともかく、ビンゴをしていたら誰もが気になることがあります。

いつビンゴになるのだろうかと。

もう結構数字がコールされているのに、一向にビンゴにならない時など特にですね。

気になった私はWebでプログラムを探しましたが、意外なことに存在しなかったのです。

日本語のサイトはビンゴカードに出てくる数字は完全ランダムで現実とは違いました。海外のサイトでもシミュレーションが多く、探索アルゴリズムは少ないです。（調べ方は甘いと思うのでソースあればコメントで）

ですので、現実に則ったビンゴの確率――正確には数字$a_0, a_1, ... , a_n$ がコールされた際のビンゴ確率を求めていきます。

ビンゴカードについて

ビンゴカードには3つのルールがあります。

• 書かれる数字は1以上75以下
• 中央はFreeマス
• $i$ 列目に入る数字 $n$ は $15i-14 \le n \le 15i$ を満たす

最後の条件が少しややこしく感じるかもしれませんが、言及していることは一列目は1 ~ 15、二列目は16 ~ 30しか入らないということですね。
一例はこんな感じです。

どんな時にビンゴになるのか？

（ここではFreeマスは一旦考慮しないことにします）

ご存知のとおり、縦横斜めのいずれかの方向に5つ数字が当たればビンゴになります。もしビンゴカードの数字が完全ランダムに配置されていた場合は5個数字が呼ばれた瞬間ビンゴの可能性が出てきます。

しかし、実際のビンゴカードは数字の範囲が決まっているので数字が5個呼ばれたとしても、その数字の種類によってはビンゴの可能性が０の場合が出てきます。

example 1

$3, 9, 10, 11, 15$ がコールされた場合、一列目のビンゴの可能性がある。

example 2

$3, 9, 10, 11, 24$ がコールされた場合、ビンゴの可能性は存在しない。（最大でも一列目がリーチになるだけ）

example 3

$1, 16, 32, 44, 69$ が コールされた場合、ヨコナナメでビンゴの可能性がある。

※実際にはFreeマスがあるのでビンゴの可能性は数字が4個コールされた時点でビンゴの可能性は生じます。

アルゴリズムの方針

ここまでの条件を踏まえてアルゴリズムを考えていきましょう。

カード全てを列挙してシミュレート

まず初めに誰もが思いつく方法ですね。全てのカードを予め作成しておき、数字がコールされるごとに全てのカードに穴を開けていくということです。しかし残念ながらこの方法は使えません。

理由はすぐに分かります。まずはカードの種類は高校数学の数え上げで計算しましょう。三列目に入る数字の種類は ${}_{15}P_4$ 、それ以外の列は ${}_{15}P_5$ より

$$({}_{15}P_5) ^ 4 \cdot {}_{15}P_4 \simeq 5 \times 10^{26}$$

以上より、計算量は $O(10^{26})$ にも上り、とてもじゃないけど私が生きている間には計算できそうにないです。そこでなんとかカードを全て見ずとも確率を計算したいです。

そんな時は発想を逆転させましょう。今は「カード生成 → 数字コール → 確率計算」という順序で考えていましたがこれを、「数字コール → カード → 確率計算」という順序に持っていきたいです。そこで何を使うか考えてみましょう！

呼ばれた数字からビンゴカードを復元

例えば $1,2,3,4,5$ がコールされた場合、どんなカードがビンゴになりうるでしょうか？　これは簡単で一列目に$1,2,3,4,5$ が含まれているビンゴカードになります。これは

となります。つまりシミュレーションをしなくともコールされた数字が分かればビンゴが発生するカードの種類を計算できるということです。

唐突に登場するbit全探索

bit全探索はアルゴリズムとしてはかなり有名ではないでしょうか。bitで集合を管理することによってとある集合の部分集合を全て調べることができます。

n = 4
bit = 1 << n
for b in range(bit):
  # 例えば1011なら1,2,4番目の要素をとってきた集合
  print("{:04b}".format(b))

これも全探索だから変わらないだろうと思う方もいらっしゃるかもしれませんが、全探索するのはカードの種類ではありません。ここからは次の記事（未執筆）以降で紹介していこうと思います。

Next 〇〇's ヒーント!
「0,1で表せる情報」

次回をお楽しみに！？（やる気でたら書きます）