結果

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

ソースコード

diff #
raw source code 

import math

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

    secs = []
    for s in S:
        m, s_part = s.split(':')
        sec = int(m) * 60 + int(s_part)
        secs.append(sec)
    sum_total = sum(secs)
    T = L * 60

    if sum_total <= T:
        print(N)
        return

    R_lim = T - 1
    res = 0.0

    for i in range(N):
        s = [secs[j] for j in range(N) if j != i]
        m = len(s)  # m = N-1

        # Initialize DP table
        dp = [[0] * (R_lim + 1) for _ in range(m + 1)]
        dp[0][0] = 1

        for sk in s:
            for j in range(m, 0, -1):
                for t in range(R_lim, sk - 1, -1):
                    dp[j][t] += dp[j - 1][t - sk]

        p_i = 0.0
        for j in range(1, N + 1):
            j_1 = j - 1
            if j_1 > m:
                continue
            total = sum(dp[j_1][t] for t in range(R_lim + 1))
            if total == 0:
                continue
            comb = math.comb(m, j_1)
            if comb == 0:
                continue
            prob = total / comb
            p_i += prob * (1.0 / N)
        res += p_i

    print("{0:.10f}".format(res))

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