結果

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

ソースコード

diff #
raw source code 

import sys
from math import factorial

def main():
    # 读取输入
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    L = int(input[idx])
    idx +=1
    S = []
    for s in input[idx:idx+N]:
        mm, ss = map(int, s.split(':'))
        S.append(mm *60 + ss)
    idx +=N

    T = sum(S)
    L_total = L *60
    M_max = L_total // T if T !=0 else 0

    # 对于每首歌i计算其被播放的概率
    total_expectation = 0.0
    for i in range(N):
        prob_i = 1.0
        for k in range(M_max +1):
            R_total = L_total - k*T
            if R_total <=0:
                continue
            R_play = min(R_total, T)
            R_needed = R_play -1  # 至少播放1秒

            if R_needed <0:
                continue

            # 准备其他歌曲的列表
            S_without_i = []
            for j in range(N):
                if j != i:
                    S_without_i.append(S[j])
            n = len(S_without_i)

            # 对于每个p，计算sum <= R_needed的概率
            # 并计算q_k

            q_k = 0.0
            for p in range(1, N+1):
                # 计算选择p-1首歌的总和 <= R_needed的概率
                m = p-1
                if m > n:
                    continue
                if m ==0:
                    # p=1，sum=0 <= R_needed
                    count = 1
                    total =1
                    prob_p = 1.0
                else:
                    # 动态规划计算
                    max_sum = R_needed
                    dp = [ [0]*(max_sum +1) for _ in range(m+1) ]
                    dp[0][0] =1
                    for s in S_without_i:
                        for current_m in range(m, 0, -1):
                            for current_sum in range(max_sum, -1, -1):
                                if dp[current_m-1][current_sum] >0:
                                    if current_sum + s <= max_sum:
                                        dp[current_m][current_sum + s] += dp[current_m-1][current_sum]
                    # 计算符合条件的总数
                    count =0
                    for s in range(0, R_needed +1):
                        count += dp[m][s]
                    total = factorial(n) // ( factorial(m) * factorial(n -m) )
                    if total ==0:
                        prob_p =0.0
                    else:
                        prob_p = count / total
                # 概率为 prob_p 乘以 1/N
                q_k += (prob_p / N)
            prob_i *= (1.0 - q_k)
        prob_i = 1.0 - prob_i
        total_expectation += prob_i

    # 输出结果，保留一位小数
    print("{0:.1f}".format(total_expectation))

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