結果

問題 No.155 生放送とBGM
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:13:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,471 bytes
コンパイル時間 483 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 292,664 KB
最終ジャッジ日時 2025-04-16 00:15:11
合計ジャッジ時間 15,099 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math
from collections import defaultdict

def main():
    n, L = map(int, input().split())
    S_str = input().split()
    
    S = []
    for s in S_str:
        mm, ss = map(int, s.split(':'))
        S.append(mm * 60 + ss)
    
    T = L * 60
    S_total = sum(S)
    m_max = T // S_total
    
    if m_max >= 1:
        print(n)
        return
    
    ans = 0.0
    for i in range(n):
        other_songs = [S[j] for j in range(n) if j != i]
        max_sum = T - 1
        max_t = len(other_songs)
        
        dp = [defaultdict(int) for _ in range(max_t + 1)]
        dp[0][0] = 1
        
        for d in other_songs:
            for t in range(len(other_songs), 0, -1):
                current_sums = list(dp[t-1].items())
                for s, cnt in current_sums:
                    new_s = s + d
                    if new_s <= max_sum:
                        dp[t][new_s] += cnt
        
        sum_prob = 0.0
        for k in range(1, n + 1):
            t = k - 1
            if t < 0 or t > len(other_songs):
                continue
            valid = sum(dp[t].values())
            total = math.comb(len(other_songs), t) if len(other_songs) >= t else 0
            if total == 0:
                prob_k = 0.0
            else:
                prob_k = valid / total
            sum_prob += prob_k
        
        prob_i = sum_prob / n
        ans += prob_i
    
    print("{0:.10f}".format(ans))

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