結果

問題 No.155 生放送とBGM
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:34:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,402 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 82,848 KB
実行使用メモリ 249,488 KB
最終ジャッジ日時 2025-03-31 17:34:55
合計ジャッジ時間 14,727 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math

def mmss_to_sec(s):
    mm, ss = map(int, s.split(':'))
    return mm * 60 + ss

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    L = int(input[1]) * 60
    S_list = [mmss_to_sec(s) for s in input[2:2+N]]
    sum_s = sum(S_list)
    
    total = 0.0
    
    for k in range(N):
        S_k = S_list[k]
        sum_other = sum_s - S_k
        s_other = [S_list[i] for i in range(N) if i != k]
        n_other = len(s_other)
        i_max = (L - 1) // sum_s if sum_s != 0 else 0
        phase_probs = []
        
        for i in range(i_max + 1):
            current_start = i * sum_s
            x = (L - 1) - current_start
            if x < 0:
                continue
            
            prob_i = 0.0
            for j in range(1, N + 1):
                required = j - 1
                if required < 0 or required > n_other:
                    continue
                
                if required == 0:
                    prob = 1.0 / N
                    prob_i += prob
                    continue
                
                sorted_s = sorted(s_other)
                min_sum = sum(sorted_s[:required])
                max_sum = sum(sorted_s[-required:])
                if x < min_sum:
                    c = 0
                elif x >= max_sum:
                    c = math.comb(n_other, required)
                else:
                    max_t = x
                    dp = [[0] * (max_t + 1) for _ in range(required + 1)]
                    dp[0][0] = 1
                    for s in s_other:
                        for jj in range(required, 0, -1):
                            for t in range(max_t, s - 1, -1):
                                if dp[jj - 1][t - s]:
                                    dp[jj][t] += dp[jj - 1][t - s]
                    c = sum(dp[required][:x + 1])
                
                total_comb = math.comb(n_other, required)
                if total_comb == 0:
                    continue
                prob = (c / total_comb) * (1.0 / N)
                prob_i += prob
            
            phase_probs.append(prob_i)
        
        # Calculate P_k = 1 - product of (1 - p_ik)
        P_k = 1.0
        for p in phase_probs:
            P_k *= (1 - p)
        P_k = 1 - P_k
        total += P_k
    
    print("{0:.10f}".format(total))
    
if __name__ == '__main__':
    main()
0