結果

問題 No.155 生放送とBGM
ユーザー lam6er
提出日時 2025-03-20 20:41:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,912 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 267,104 KB
最終ジャッジ日時 2025-03-20 20:41:42
合計ジャッジ時間 14,549 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def compute_prob(s_list, r):
    n = len(s_list)
    if r == 0:
        return 0.0
    max_c = n
    max_r = r - 1
    # dp[c][s] initialized to 0, dp[0][0] =1
    dp = [[0]*(max_r + 1) for _ in range(max_c + 1)]
    dp[0][0] = 1
    for s in s_list:
        for c in range(max_c, 0, -1):
            for prev_sum in range(max_r, -1, -1):
                if dp[c-1][prev_sum]:
                    new_sum = prev_sum + s
                    if new_sum <= max_r:
                        dp[c][new_sum] += dp[c-1][prev_sum]
    total_prob = 0.0
    for i in range(1, len(s_list) + 2):
        c = i - 1
        if c > n:
            continue
        valid = 0
        if c == 0:
            valid = 1
        else:
            valid = sum(dp[c][:max_r + 1])
        comb = math.comb(n, c) if c <= n else 0
        if comb == 0:
            prob = 0.0
        else:
            prob = valid / comb
        total_prob += prob
    return total_prob / (len(s_list) + 1)

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    L = int(input[idx])
    idx +=1
    S_str = input[idx:idx+N]
    S = []
    for s in S_str:
        mm, ss = map(int, s.split(':'))
        S.append(mm * 60 + ss)
    T = L * 60
    C = sum(S)
    m_max = (T -1) // C if C !=0 else 0

    ans = 0.0

    for k in range(N):
        s_k = S[k]
        other_s = S[:k] + S[k+1:]
        sum_rest = sum(other_s)
        product = 1.0
        for m in range(m_max + 1):
            current_cycle_start = m * C
            r = T - current_cycle_start
            if r <= 0:
                continue
            if sum_rest < r:
                q_mk = 1.0
            else:
                q_mk = compute_prob(other_s, r)
            product *= (1.0 - q_mk)
        p_k = 1.0 - product
        ans += p_k
    print("{0:.10f}".format(ans))

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