結果
| 問題 |
No.335 門松宝くじ
|
| ユーザー |
 qwewe
|
| 提出日時 | 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;
}