結果
| 問題 |
No.155 生放送とBGM
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:08:10 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 395 ms / 6,000 ms |
| コード長 | 10,252 bytes |
| コンパイル時間 | 730 ms |
| コンパイル使用メモリ | 86,944 KB |
| 実行使用メモリ | 18,048 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:55 |
| 合計ジャッジ時間 | 3,564 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 15 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iomanip>
#include <cstdio> // For sscanf
using namespace std;
// Define types for clarity and potential future changes
typedef long long ll;
// Use long double for higher precision floating point arithmetic
typedef long double ld;
// Precomputed combinations table C(n, k)
// Using a fixed size array based on max N=50
ll combinations_table[51][51];
// Function to precompute combinations using Pascal's identity
// C(n, k) = C(n-1, k-1) + C(n-1, k)
void precompute_combinations(int N_max) {
// Ensure N_max doesn't exceed allocated array size
if (N_max > 50) N_max = 50;
for (int i = 0; i <= N_max; ++i) {
combinations_table[i][0] = 1; // Base case: C(i, 0) = 1
for (int j = 1; j <= i; ++j) {
// Check for potential overflow before adding.
// With N <= 50, the maximum value C(50, 25) is approx 1.26e14, which fits within a 64-bit long long.
// So standard addition should be safe. We add the check just in case.
if (combinations_table[i-1][j] > __LONG_LONG_MAX__ - combinations_table[i-1][j-1]) {
// Handle overflow - Set to MAX or throw error.
// For competitive programming contexts, we often rely on problem constraints ensuring intermediate values fit standard types.
combinations_table[i][j] = __LONG_LONG_MAX__; // Indicate overflow
} else {
combinations_table[i][j] = combinations_table[i-1][j-1] + combinations_table[i-1][j];
}
}
}
}
// Function to retrieve combinations value C(n, k) from the precomputed table
ll combinations(int n, int k) {
// Basic validation for indices n and k
if (k < 0 || k > n || n < 0 || n > 50) return 0;
// Return the precomputed value. Assuming no overflow occurred during computation.
return combinations_table[n][k];
}
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of songs
int L_minutes; // Broadcast length in minutes
cin >> N >> L_minutes;
vector<int> T_songs(N); // Vector to store song lengths in seconds
ll S_total = 0; // Total length of all songs in seconds
for (int i = 0; i < N; ++i) {
string s; // Song length input in MM:SS format
cin >> s;
int mm, ss;
// Parse the MM:SS string using sscanf
sscanf(s.c_str(), "%d:%d", &mm, &ss);
T_songs[i] = mm * 60 + ss; // Convert MM:SS to total seconds
// Constraint check: MM:SS != 00:00 means T_songs[i] > 0.
// Add assertion or check if needed, though problem statement guarantees this.
// if (T_songs[i] <= 0) { /* handle error or invalid input */ }
S_total += T_songs[i]; // Accumulate total length of all songs
}
// Calculate total broadcast duration in seconds
ll T_broadcast = (ll)L_minutes * 60;
// Handle edge case: If broadcast time is 0, no songs can be played. Expected value is 0.
if (T_broadcast == 0) {
cout << fixed << setprecision(10) << 0.0 << endl;
return 0;
}
// Handle edge case: If N=0 or total song length S_total is 0 (only possible if all T_k=0, disallowed by constraints)
if (N == 0 || S_total <= 0) {
cout << fixed << setprecision(10) << 0.0 << endl;
return 0;
}
// Case: If broadcast duration is long enough to play all songs at least once (one full cycle).
// This occurs if T_broadcast >= S_total. In this case, all N songs are guaranteed to be played.
if (T_broadcast >= S_total) {
cout << fixed << setprecision(10) << (ld)N << endl;
return 0;
}
// Main case: T_broadcast < S_total.
// We need to calculate the expected number of distinct songs played using DP.
// Precompute combinations C(n,k) up to N.
precompute_combinations(N);
// DP state: C_counts[j][s] stores the number of subsets of songs of size j with total length exactly s.
// Dimensions: (N+1) for number of songs j (from 0 to N), (T_broadcast+1) for sum s (from 0 to T_broadcast).
vector<vector<ll>> C_counts(N + 1, vector<ll>(T_broadcast + 1, 0));
C_counts[0][0] = 1; // Base case: There's 1 way to choose 0 songs with total sum 0 (the empty set).
// Fill the DP table C_counts using all N songs. This is a variation of the subset sum / knapsack problem.
for(int i = 0; i < N; ++i) { // Iterate through each song T_songs[i] (0-indexed)
int current_song_len = T_songs[i];
// Update the DP table considering the inclusion of song i.
// Iterate j (number of songs in subset) downwards from N to 1.
for (int j = N; j >= 1; --j) {
// Iterate s (total sum) downwards from T_broadcast to current_song_len.
for (int s = T_broadcast; s >= current_song_len; --s) {
// If there exists a subset of size j-1 with sum s-current_song_len...
if (C_counts[j-1][s - current_song_len] > 0) {
// ...then we can form a subset of size j with sum s by adding song i.
// Add the count. Check for potential overflow before adding.
if (C_counts[j-1][s - current_song_len] > __LONG_LONG_MAX__ - C_counts[j][s]) {
C_counts[j][s] = __LONG_LONG_MAX__; // Indicate overflow if it occurs
} else {
C_counts[j][s] += C_counts[j-1][s - current_song_len];
}
}
}
}
}
// Calculate the overall expected value E[X] = sum P(E_k) for k=1..N
ld total_expected_value = 0.0;
// Iterate through each song k (0-indexed) to calculate its probability P(E_k) of being played.
for (int k = 0; k < N; ++k) {
int Tk = T_songs[k]; // Length of the current song k
// DP state: Ck_counts[j][s] = number of subsets of S\{k} (all songs except k) of size j with sum s.
// Dimensions: N for j (0 to N-1 songs), T_broadcast+1 for s.
vector<vector<ll>> Ck_counts(N, vector<ll>(T_broadcast + 1, 0));
Ck_counts[0][0] = 1; // Base case: empty subset for j=0, s=0.
// Compute Ck_counts using the recurrence relation: C_k(j, s) = C(j, s) - C_k(j-1, s - Tk)
// C(j, s) is the count using all N songs (stored in C_counts)
// C_k(j-1, s - Tk) is count of subsets from S\{k} size j-1 sum s-Tk.
for (int j = 1; j <= N - 1; ++j) { // Compute counts row by row for j from 1 to N-1
for (int s = 0; s <= T_broadcast; ++s) { // Compute counts for each sum s
// Initialize Ck_counts[j][s] with C_counts[j][s] (subsets from full set)
Ck_counts[j][s] = C_counts[j][s];
// If sum s is large enough to potentially subtract the term C_k(j-1, s-Tk)
if (s >= Tk) {
// Check if C_k(j-1, s - Tk) is positive before subtracting
if (Ck_counts[j-1][s - Tk] > 0) {
// Basic sanity check: ensure subtraction doesn't result in negative count.
// This should not happen with correct logic and exact integer arithmetic.
if (Ck_counts[j-1][s - Tk] > Ck_counts[j][s]) {
// Indicates an issue, likely C(j, s) < Ck(j-1, s-Tk), which is impossible.
// Could hint at prior overflow or logic error. Clamp to 0 as fallback.
Ck_counts[j][s] = 0;
} else {
// Subtract the count of subsets including song k to get count of subsets excluding k.
Ck_counts[j][s] -= Ck_counts[j-1][s - Tk];
}
}
}
// Another safety check: ensure count is non-negative after subtraction.
if (Ck_counts[j][s] < 0) {
Ck_counts[j][s] = 0; // Clamp to 0 if negative.
}
}
}
// Calculate the sum of probabilities component for song k: sum_{j=0}^{N-1} p_{k,j}
// where p_{k,j} = P(sum of random j songs from S\{k} < T_broadcast)
ld Pk_sum_probs = 0.0; // Accumulator for this sum
for (int j = 0; j <= N - 1; ++j) { // Iterate over prefix size j (number of songs preceding k)
ll sum_s_count = 0; // Count subsets of S\{k} of size j with sum < T_broadcast
// Sum the counts Ck_counts[j][s] for s from 0 up to T_broadcast - 1
for (int s = 0; s < T_broadcast; ++s) {
if(Ck_counts[j][s] > 0) { // Add only positive counts
// Check for potential overflow before summing up counts.
if (Ck_counts[j][s] > __LONG_LONG_MAX__ - sum_s_count) {
sum_s_count = __LONG_LONG_MAX__; // Indicate overflow
break; // Stop summing for this j if overflow detected
} else {
sum_s_count += Ck_counts[j][s];
}
}
}
// If sum overflowed, the result might be inaccurate. Assuming it fits long long.
// Total number of ways to choose j songs from N-1 songs (the set S\{k})
ll num_subsets = combinations(N - 1, j);
// Calculate probability p_{k,j} = sum_s_count / num_subsets
// Avoid division by zero if num_subsets is 0.
if (num_subsets > 0) {
ld p_kj = (ld)sum_s_count / num_subsets;
Pk_sum_probs += p_kj; // Add p_{k,j} to the sum for song k
}
}
// The probability song k is played is P(E_k) = (1/N) * Pk_sum_probs
// Add this probability to the total expected value.
total_expected_value += Pk_sum_probs / N;
}
// Output the final calculated expected value with the required precision.
cout << fixed << setprecision(10) << total_expected_value << endl;
return 0;
}