結果
問題 | No.335 門松宝くじ |
ユーザー |
![]() |
提出日時 | 2025-05-14 13:15:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,524 ms / 2,000 ms |
コード長 | 7,221 bytes |
コンパイル時間 | 1,289 ms |
コンパイル使用メモリ | 85,052 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-05-14 13:16:52 |
合計ジャッジ時間 | 10,686 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 10 |
ソースコード
#include <iostream> #include <vector> #include <numeric> #include <algorithm> #include <iomanip> // Include for potential future use with floating point precision settings using namespace std; // Use long long for prize sums to avoid potential overflow. // While N=800 might barely fit N^3/2 into a 32-bit signed integer, using long long is safer. using ll = long long; // Function to check if sequence (a, b, c) is a Kadomatsu sequence. // A sequence of three distinct integers A, B, C is Kadomatsu if B is not the median. // This means B must be either the minimum or the maximum of the three. // Made inline for potential minor speed optimization. inline bool is_kadomatsu(int a, int b, int c) { // The problem guarantees that for any distinct indices i, j, k, the values E[i], E[j], E[k] // are distinct because the ticket sequence is a permutation of distinct numbers 1..N. // Therefore, we don't need to check for distinctness explicitly here. return (b < a && b < c) || (b > a && b > c); } // Function to find the maximum of three integers. // Made inline for potential minor speed optimization. inline int max3(int a, int b, int c) { // std::max is generally efficient, possibly implemented as an intrinsic function or inline. return max(a, max(b, c)); } int main() { // Enable faster I/O operations. Crucial for performance in competitive programming. ios_base::sync_with_stdio(false); cin.tie(NULL); int N, M; // N: number of integers on a ticket, M: number of tickets cin >> N >> M; // Read ticket data into a vector of vectors. tickets[i] stores the sequence for ticket i. vector<vector<int>> tickets(M, vector<int>(N)); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { cin >> tickets[i][j]; } } double max_expected_value = -1.0; // Initialize max expected value to a value lower than any possible EV (EV >= 0) int best_ticket_idx = 0; // Initialize best ticket index to 0. This handles cases where all EVs are 0, or the first ticket is the best. // Preallocate the max_prize table outside the main loop over tickets. // This avoids repeated allocation/deallocation overhead. // Size (N+1)x(N+1) allows using 1-based indexing for numbers 1 to N, matching their values. vector<vector<int>> max_prize(N + 1, vector<int>(N + 1)); // Process each ticket one by one for (int t = 0; t < M; ++t) { // Reset the max_prize table for the current ticket. // We only need to clear the portion [1..N][1..N] that we actually use. // Using nested loops or std::fill per row are options. std::fill is used here. for (int i = 1; i <= N; ++i) { fill(max_prize[i].begin() + 1, max_prize[i].begin() + N + 1, 0); } // Get a reference to the current ticket's sequence for easier access. const vector<int>& current_ticket = tickets[t]; // The core logic: Iterate through all possible triples of indices (i, j, k) such that i < j < k. // This corresponds to selecting three numbers A, B, C from the ticket in their original order. for (int i = 0; i < N; ++i) { // Small optimization: If fewer than 2 elements remain after index i, we cannot form a triple (i, j, k). if (N - 1 - i < 2) break; for (int j = i + 1; j < N; ++j) { // Small optimization: If fewer than 1 element remains after index j, we cannot complete a triple. if (N - 1 - j < 1) break; // Extract values A and B. These are fixed for the innermost loop over k. int A = current_ticket[i]; int B = current_ticket[j]; for (int k = j + 1; k < N; ++k) { // Extract value C. int C = current_ticket[k]; // Check if the triple (A, B, C) forms a Kadomatsu sequence. if (is_kadomatsu(A, B, C)) { // If it is Kadomatsu, calculate the prize value P, which is the maximum of A, B, C. int P = max3(A, B, C); // This Kadomatsu triple (A, B, C) implies that if any pair from {A, B, C} is announced, // we can choose the third element and potentially win prize P. // We update the maximum possible prize for each pair associated with this triple. // max_prize[X][Y] stores the maximum prize P obtainable if pair {X, Y} is announced. // Update checks `if (P > max_prize...)` can potentially save memory writes but impact is minimal. // Directly using max() ensures correctness simply. max_prize[A][B] = max(max_prize[A][B], P); max_prize[B][A] = max_prize[A][B]; // Keep the table symmetric for consistency if needed elsewhere (not strictly necessary here) max_prize[A][C] = max(max_prize[A][C], P); max_prize[C][A] = max_prize[A][C]; max_prize[B][C] = max(max_prize[B][C], P); max_prize[C][B] = max_prize[B][C]; } } } } // After checking all triples for the current ticket, calculate the total sum of maximum prizes. // Sum over all distinct pairs {X, Y} where 1 <= X < Y <= N. ll total_prize_sum = 0; for (int X = 1; X <= N; ++X) { for (int Y = X + 1; Y <= N; ++Y) { total_prize_sum += max_prize[X][Y]; } } // Calculate the expected value for the current ticket. // Expected Value = Sum of (Prize for pair {X,Y} * Probability of pair {X,Y}) // Since probability is uniform 1 / (N C 2) for all pairs: // EV = (Sum of Prizes P(X,Y)) / (Number of pairs) double expected_value = 0; // Total number of distinct pairs {X, Y} from {1, ..., N} is N * (N - 1) / 2. ll num_pairs = (ll)N * (N - 1) / 2; if (num_pairs > 0) { // Check required to avoid division by zero, although N >= 3 guarantees num_pairs > 0. expected_value = (double)total_prize_sum / num_pairs; } // Compare the calculated expected value with the current maximum found so far. // Update the best ticket index if the current ticket provides a higher expected value. // The check `t == 0` handles initialization correctly for the first ticket. if (t == 0 || expected_value > max_expected_value) { max_expected_value = expected_value; best_ticket_idx = t; } // Tie-breaking rule: If `expected_value == max_expected_value`, we DO NOT update `best_ticket_idx`. // This ensures that among tickets with the same maximum expected value, the one with the smallest index `t` is chosen. } // Output the 0-indexed identifier of the ticket with the highest expected value. cout << best_ticket_idx << endl; return 0; }