結果

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

ソースコード

diff #
raw source code 

import sys
from math import comb

def main():
    n, L = map(int, sys.stdin.readline().split())
    s_list = sys.stdin.readline().split()
    
    S = []
    for s in s_list:
        mm, ss = map(int, s.split(':'))
        S.append(mm * 60 + ss)
    
    T = L * 60
    S_total = sum(S)
    
    if S_total <= T:
        print(n)
        return
    
    E = 0.0
    for i in range(n):
        song_i = S[i]
        others = S[:i] + S[i+1:]
        m_max = len(others)
        
        total_prob = 0.0
        
        for k in range(1, n + 1):
            m = k - 1
            if m > m_max:
                continue
            
            a_max = T - 1  # 因为 t <= T-1
            if a_max < 0:
                continue
            
            # 初始化动态规划表
            dp = [[0] * (a_max + 1) for _ in range(m + 1)]
            dp[0][0] = 1
            for s in others:
                for current_m in range(m, 0, -1):
                    for current_a in range(a_max, s - 1, -1):
                        if dp[current_m - 1][current_a - s]:
                            dp[current_m][current_a] += dp[current_m - 1][current_a - s]
            
            count = sum(dp[m][a] for a in range(a_max + 1))
            total = comb(len(others), m)
            if total == 0:
                prob = 0.0
            else:
                prob = count / total
            
            total_prob += (1.0 / n) * prob
        
        E += total_prob
    
    print("{0:.10f}".format(E))

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