結果

問題 No.242 ビンゴゲーム
ユーザー rpy3cpprpy3cpp
提出日時 2015-07-11 00:24:38
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 2,216 bytes
コンパイル時間 80 ms
コンパイル使用メモリ 11,080 KB
実行使用メモリ 8,560 KB
最終ジャッジ日時 2023-09-22 10:32:06
合計ジャッジ時間 977 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
8,560 KB
testcase_01 AC 18 ms
8,524 KB
testcase_02 AC 17 ms
8,512 KB
testcase_03 AC 17 ms
8,424 KB
testcase_04 AC 18 ms
8,552 KB
testcase_05 AC 17 ms
8,424 KB
testcase_06 AC 18 ms
8,372 KB
testcase_07 AC 17 ms
8,384 KB
testcase_08 AC 17 ms
8,552 KB
testcase_09 AC 17 ms
8,444 KB
testcase_10 AC 17 ms
8,540 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def preprocess():
    Bingos = [0] * 26
    Counts = [0] * 26
    masks12 = get_masks()
    for pat in range(2**25):
        bits_on = bin(pat).count('1')
        Bingos[bits_on] += 12 - len([1 for mask in masks12 if ~pat & mask])
        Counts[bits_on] += 1
    return [bingo/count for bingo, count in zip(Bingos, Counts)]

def get_masks():
    bingo_patterns = [[0, 1, 2, 3, 4],
                      [5, 6, 7, 8, 9],
                      [10, 11, 12, 13, 14],
                      [15, 16, 17, 18, 19],
                      [20, 21, 22, 23, 24],
                      [0, 5, 10, 15, 20],
                      [1, 6, 11, 16, 21],
                      [2, 7, 12, 17, 22],
                      [3, 8, 13, 18, 23],
                      [4, 9, 14, 19, 24],
                      [0, 6, 12, 18, 24],
                      [4, 8, 12, 16, 20]]
    return [sum(1 << i for i in pat) for pat in bingo_patterns]

# E = preprocess()
# 2秒では計算が終わらなかったので、オフラインで事前に計算しました。。。
E = [0.0, 0.0, 0.0, 0.0, 0.0, 0.00022586109542631282, 0.0013551665725578769, 0.0047430830039525695, 0.012648221343873518, 0.028458498023715414, 0.05691699604743083, 0.10434782608695652, 0.17888198757763976, 0.2906832298136646, 0.45217391304347826, 0.6782608695652174, 0.9865612648221344, 1.3976284584980236, 1.9351778656126482, 2.6263128176171655, 3.501750423489554, 4.59604743083004, 5.947826086956522, 7.6, 9.6, 12.0]

def prob(N):
    '''1-99 までの N 個を選んだときに、1-25までの数字が n 個含まれる確率 prob[n] のリストを返す。
    1-25から n 個とり、26-99から N-n 個とればよい。
    '''
    probs = [0] * 26
    base = math.factorial(99) // math.factorial(N) // math.factorial(99 - N)
    fac25 = math.factorial(25)
    fac74 = math.factorial(74)
    for n in range(max(0, N - 74), min(25, N) + 1):
        pats1_25 = fac25 // math.factorial(n) // math.factorial(25 - n)
        pats26_99 = fac74 // math.factorial(N - n) // math.factorial(74 - N + n)
        probs[n] = pats1_25 * pats26_99 / base
    return probs

N = int(input())
probs = prob(N)
Expected = sum(e * p for e, p in zip(E, probs))
print(Expected)
0