#1084040 (C++17) No.335 門松宝くじ

• 問題: 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;
}