結果

問題 No.155 生放送とBGM
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:27:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,596 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 288,372 KB
最終ジャッジ日時 2025-06-12 18:27:33
合計ジャッジ時間 14,597 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math
from collections import defaultdict

def compute_p(n, s_list, R):
    dp = [defaultdict(int) for _ in range(n + 1)]
    dp[0][0] = 1

    for s in s_list:
        for t in range(n - 1, -1, -1):
            current_sums = list(dp[t].items())
            for sum_s, cnt in current_sums:
                new_sum = sum_s + s
                if new_sum < R:
                    dp[t + 1][new_sum] += cnt

    C = [0] * (n + 1)
    for t in range(n + 1):
        C[t] = sum(dp[t].values())

    sum_ratio = 0.0
    for t in range(n + 1):
        if t > n:
            continue
        comb_nt = math.comb(n, t) if n >= t else 0
        if comb_nt == 0:
            ratio = 0.0
        else:
            ratio = C[t] / comb_nt
        sum_ratio += ratio

    p_k = sum_ratio / (n + 1)
    return p_k

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    L = int(input[idx])
    idx += 1
    S_list = input[idx:idx + N]
    idx += N

    s_total = []
    total = 0
    for s in S_list:
        mm, ss = map(int, s.split(':'))
        sec = mm * 60 + ss
        s_total.append(sec)
        total += sec

    L_sec = L * 60
    K = L_sec // total
    if K >= 1:
        print(N)
        return

    R = L_sec
    res = 0.0
    for k in range(N):
        s_list = s_total[:k] + s_total[k+1:]
        n = len(s_list)
        p_k = compute_p(n, s_list, R)
        res += p_k

    print("{0:.10f}".format(res).rstrip('0').rstrip('.') if '.' in "{0:.10f}".format(res) else "{0:.10f}".format(res))

if __name__ == "__main__":
    main()
0