結果
問題 |
No.155 生放送とBGM
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:16:26 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,066 bytes |
コンパイル時間 | 261 ms |
コンパイル使用メモリ | 81,900 KB |
実行使用メモリ | 275,680 KB |
最終ジャッジ日時 | 2025-04-16 00:18:13 |
合計ジャッジ時間 | 14,695 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 14 |
ソースコード
import sys def main(): from math import factorial N, L = map(int, sys.stdin.readline().split()) L_seconds = L * 60 S_list = [] total_S = 0 for s in sys.stdin.readline().split(): mm, ss = map(int, s.split(':')) total = mm * 60 + ss S_list.append(total) total_S += total K = L_seconds // total_S if total_S != 0 else 0 R = L_seconds % total_S if total_S != 0 else L_seconds if K >= 1: print(N) return # Precompute combinations using Pascal's triangle max_n = N - 1 comb = [[0] * (max_n + 1) for _ in range(max_n + 1)] for i in range(max_n + 1): comb[i][0] = 1 for j in range(1, i + 1): comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j] expected = 0.0 for idx in range(N): s_i = S_list[idx] other_s = S_list[:idx] + S_list[idx + 1:] n = len(other_s) if n == 0: # Only this song, check if R >=1 expected += 1.0 if s_i >= 1 else 0.0 continue # DP to compute C(m): number of ways to choose m songs with sum < R R_current = R dp = [ [0] * (R_current) for _ in range(n + 1) ] dp[0][0] = 1 for s in other_s: for m in range(n - 1, -1, -1): for t in range(R_current): if dp[m][t]: nt = t + s if nt < R_current: dp[m + 1][nt] += dp[m][t] # Compute C(m) C = [0] * (n + 1) for m in range(n + 1): C[m] = sum(dp[m][t] for t in range(R_current)) # Calculate sum(C[m] / comb(n, m)) for m from 0 to n total = 0.0 for m in range(n + 1): if comb[n][m] == 0: continue if C[m] == 0: continue total += C[m] / comb[n][m] # Probability for this song prob = total / N expected += prob print("{0:.10f}".format(expected)) if __name__ == '__main__': main()