#1083874 (C++17) No.1515 Making Many Multiples

• 問題: No.1515 Making Many Multiples
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:06:42
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,592 bytes
• コンパイル時間: 1,230 ms
• コンパイル使用メモリ: 86,608 KB
• 実行使用メモリ: 37,096 KB
• 最終ジャッジ日時: 2025-05-14 13:08:03
• 合計ジャッジ時間: 4,605 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	-- * 3
other	AC * 2 TLE * 1 -- * 25

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <vector> // Required for vector
#include <utility> // Required for pair

// Use -1 to indicate an unreachable state, since scores are non-negative (0 or more).
const int INF = -1; 

int main() {
    // Use fast I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N; // Number of cards in the deck
    int K; // The divisor for checking multiples
    long long X, Y; // Initial cards values (can be large)
    std::cin >> N >> K >> X >> Y;
    
    // Read the N card values from the deck
    std::vector<long long> A(N); // Card values can be large
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }
    
    // DP table: dp[x][y] stores the maximum score achieved ending with cards
    // having values modulo K equal to x and y, where x <= y.
    // Initialize all states to INF (-1), indicating unreachable.
    std::vector<std::vector<int>> dp(K, std::vector<int>(K, INF));
    
    // Calculate initial state based on X and Y modulo K.
    int x0 = X % K;
    int y0 = Y % K;
    // Problem statement says X, Y are positive integers, so X, Y >= 1.
    // If K=1, X%K and Y%K will be 0.
    // If K > 1, X%K and Y%K will be in range [0, K-1].
    // No need for negative modulo result handling.
    
    // Ensure x <= y for the state representation (canonical form).
    if (x0 > y0) std::swap(x0, y0);
    dp[x0][y0] = 0; // The initial score is 0. Mark this state as reachable.

    // Keep track of reachable states {x, y} in the current DP table.
    // This optimization avoids iterating through all K*K possible states.
    std::vector<std::pair<int, int>> reachable_states;
    // Add the initial state to the list if it's valid (score >= 0).
    if (dp[x0][y0] != INF) {
       reachable_states.push_back({x0, y0});
    }

    // Temporary storage for updates to be applied in the next step.
    // Each update is a pair: { {next_state_x, next_state_y}, new_score }.
    std::vector<std::pair<std::pair<int, int>, int>> next_updates;
    // Reserve some memory to potentially avoid reallocations.
    // The maximum number of updates generated from M reachable states is 3*M.
    // In worst case M can be up to K*(K+1)/2.
    next_updates.reserve(3 * K * (K+1) / 2); // Heuristic reservation size

    // Simulate the N steps of the game.
    for (int i = 0; i < N; ++i) {
        // Get the value of the card drawn at step i, modulo K.
        int ai = A[i] % K; 
        // Problem states A_i are positive integers. Modulo result is non-negative.

        next_updates.clear(); // Clear updates from the previous step.
        
        // Iterate through only the states that were reachable after the previous step.
        for (const auto& state : reachable_states) {
            int x = state.first;  // First card value mod K
            int y = state.second; // Second card value mod K (x <= y)
            int current_score = dp[x][y];
            
            // Defensive check: if state somehow is invalid, skip.
            if (current_score == INF) continue; 

            // Check if the sum of cards in hand (x, y, and newly drawn ai) is a multiple of K.
            int score_increment = 0;
            // Use long long for the sum calculation to prevent potential overflow before modulo.
            // Max sum can be approx 3*10^9 if K=2000, X,Y,A_i near 10^9. Oh wait, x, y, ai are mod K.
            // Max sum is (K-1)+(K-1)+(K-1) = 3K-3. Fits in int if 3K < 2^31. K=2000 -> 3K=6000. Fits.
            // Let's use long long anyway just to be safe / standard practice.
            if (((long long)x + y + ai) % K == 0) {
                score_increment = 1; // Score increases by 1 if sum is multiple of K.
            }
            int new_score = current_score + score_increment; // The score after this step, if transition occurs.
            
            // Calculate the 3 possible next states based on discarding one card.
            // Queue these potential updates.
            
            // Option 1: Discard the card corresponding to x mod K. Keep cards y and ai.
            int next_y1 = y;
            int next_a1 = ai;
            // Ensure canonical state representation (smaller value first).
            if (next_y1 > next_a1) std::swap(next_y1, next_a1); 
            next_updates.push_back({{next_y1, next_a1}, new_score});

            // Option 2: Discard the card corresponding to y mod K. Keep cards x and ai.
            int next_x2 = x;
            int next_a2 = ai;
            // Ensure canonical state representation.
            if (next_x2 > next_a2) std::swap(next_x2, next_a2); 
            next_updates.push_back({{next_x2, next_a2}, new_score});

            // Option 3: Discard the newly drawn card ai. Keep cards x and y.
            int next_x3 = x;
            int next_y3 = y;
            // The state (x, y) is already in canonical form (x <= y).
            next_updates.push_back({{next_x3, next_y3}, new_score});
        }

        // Before applying the updates for the current step, we must reset the DP scores
        // for the states that were reachable from the *previous* step. This effectively
        // clears the "current" DP state layer to prepare for the "next" layer.
        for (const auto& state : reachable_states) {
            dp[state.first][state.second] = INF;
        }
        // Clear the list of reachable states; it will be rebuilt based on the updates.
        reachable_states.clear(); 

        // Apply the collected updates.
        // Rebuild the `reachable_states` list for the next iteration.
        for (const auto& update : next_updates) {
            int nx = update.first.first;  // Next state x component
            int ny = update.first.second; // Next state y component
            int score = update.second;    // The score achieved reaching this state
            
            // Update the DP table if this path provides a better score,
            // or if the state becomes reachable for the first time.
            if (dp[nx][ny] == INF || score > dp[nx][ny]) {
                 // If the state was previously unreachable (INF), add it to the list of
                 // reachable states for the next iteration.
                 if (dp[nx][ny] == INF) {
                    reachable_states.push_back({nx, ny}); 
                 }
                 // Update the DP table with the maximum score found so far for state (nx, ny).
                 dp[nx][ny] = score; 
            }
            // If score <= dp[nx][ny], this path is not better, so do nothing.
        }
        // Optional optimization: Deduplicate reachable_states vector.
        // This might be beneficial if many updates lead to the same states.
        // Can be done using sort + unique, but adds O(M log M) complexity where M is size.
        // Decided against it for simplicity and potential overhead. The current loop structure handles duplicates correctly.
    }
    
    // After N steps, find the maximum score among all reachable states.
    int max_score = 0; // Minimum possible score is 0.
    // Check all possible states (x, y) with x <= y in the final DP table.
    for (int x = 0; x < K; ++x) {
        for (int y = x; y < K; ++y) { 
            if (dp[x][y] != INF) { // If the state is reachable
                max_score = std::max(max_score, dp[x][y]);
            }
        }
    }
    
    // Output the final maximum score.
    std::cout << max_score << std::endl; 
    
    return 0; // Indicate successful execution.
}