#1083955 (C++17) No.937 Ultra Sword

• 問題: No.937 Ultra Sword
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:10:56
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 6,963 bytes
• コンパイル時間: 1,242 ms
• コンパイル使用メモリ: 92,432 KB
• 実行使用メモリ: 15,692 KB
• 最終ジャッジ日時: 2025-05-14 13:12:52
• 合計ジャッジ時間: 3,909 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
other	AC * 45 WA * 2

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
#include <map>
#include <vector> // Ensure vector is included

// Define constants based on problem constraints
// Use a sufficiently large number for infinity if needed, but not required here
// const long long INF = 1e18; 
// Max value of A_i is 10^5, array size needs to be 100001 for 0-based indexing up to 100000
const int MAX_A_VAL = 100001; 

int N; // Number of monsters
std::vector<int> A; // Store initial HPs
int M = 0; // Maximum HP value encountered

std::vector<int> Basis; // Basis for the XOR span
std::set<int> L_V; // Set to store unique non-zero elements of the XOR span L(V)

/**
 * @brief Computes the basis of the vector space spanned by initial HPs under XOR operation.
 * Uses Gaussian elimination method.
 */
void build_basis() {
    // Basis stores the linearly independent elements under XOR
    std::vector<int> basis_temp;
    // Iterate through each initial HP value
    for(int x : A) {
        if (x == 0) continue; // Ignore HP=0, as A_i >= 1 per constraints
        // Reduce x by XORing with existing basis elements to find its unique contribution
        for(int b : basis_temp) {
            // If XORing with b reduces x, update x. Standard basis reduction step.
            x = std::min(x, x ^ b);
        }
        // If x is still > 0 after reduction, it means x adds a new dimension (is linearly independent)
        if (x > 0) {
            basis_temp.push_back(x);
            // Keep the basis sorted in descending order. This helps in reducing elements faster.
             std::sort(basis_temp.rbegin(), basis_temp.rend());
        }
     }
    Basis = basis_temp; // Assign the computed basis
}

/**
 * @brief Recursively generates all elements in the XOR span L(V) from the basis.
 * Stores unique non-zero generated values into the set L_V.
 * @param k Current index of the basis element being considered.
 * @param current_xor_sum The XOR sum accumulated so far.
 */
void generate_span(int k, int current_xor_sum) {
    // Base case: If we have considered all basis elements
    if (k == Basis.size()) {
        // Add the generated value to the set if it's non-zero
        if (current_xor_sum > 0) {
            L_V.insert(current_xor_sum);
        }
        return;
    }
    // Recursive step: Explore two possibilities for the k-th basis element
    // 1. Don't include the k-th basis element in the XOR sum
    generate_span(k + 1, current_xor_sum);
    // 2. Include the k-th basis element in the XOR sum
    generate_span(k + 1, current_xor_sum ^ Basis[k]);
}

// Using arrays for counts and Delta sum for efficiency
// Cnt[v] stores the number of monsters with HP v
int Cnt[MAX_A_VAL]; 
// Delta[K] stores the total HP reduction achieved by sacrificing K
// Delta[K] = sum over v=mK ( Cnt[v] * (v - v/K) )
long long Delta[MAX_A_VAL]; 

int main() {
    // Faster I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // Read input N
    std::cin >> N;
    A.resize(N); // Resize vector A to hold N elements
    long long S_total = 0; // Total initial HP sum, use long long for potentially large sums
    M = 0; // Reset max HP M
    
    // Read initial HPs, compute total sum S_total, find max HP M, and fill Cnt array
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
        if (A[i] > M) {
            M = A[i]; // Update max HP
        }
        // Ensure HP is within bounds [1, MAX_A_VAL-1] before accessing Cnt array
        if (A[i] > 0 && A[i] < MAX_A_VAL) { 
             Cnt[A[i]]++; // Increment count for this HP value
        }
         S_total += A[i]; // Accumulate total HP
    }
    
    // Handle edge case M=0 (if N=0 or all A_i=0), ensure M >= 1 for array indexing and loops.
    // Based on constraints N>=2 and A_i>=1, M will be at least 1.
    if (M == 0) M = 1; 

    // Precompute Delta[K] for all K from 1 to M
    // This takes O(M log M) time using a harmonic series summation approach
    for (int K = 1; K <= M; ++K) {
        // Iterate through all multiples v of K up to M
        for (int v = K; v <= M; v += K) {
            // If there are monsters with HP v
            if (Cnt[v] > 0) {
                // Add the total reduction achieved for these monsters to Delta[K]
                // Reduction per monster is (v - v/K)
                Delta[K] += (long long)Cnt[v] * (v - v / K);
            }
        }
    }

    // Compute the XOR basis from initial HPs A
    build_basis();
    // If basis is not empty, generate all values in its XOR span L(V)
    if (!Basis.empty()) {
        // Start generating span from basis index 0 with initial XOR sum 0
        generate_span(0, 0); 
    }

    // Final candidate set C_final stores all possible values K for sacrifice
    std::set<int> C_final;
    // Add all initial HPs A_i to the candidate set
    for (int val : A) {
        if (val > 0) { // Ensure K > 0, as sacrifice value must be positive
            C_final.insert(val);
        }
    }

    // Add values generated by XOR span L(V) and its doublings (2^p * x)
    for (int x : L_V) {
        // Use long long for K to handle potential intermediate large values during doubling
        long long K_ll = x; 
        // Iterate through K = x, 2x, 4x, ... as long as K is positive and <= M
        while (K_ll > 0 && K_ll <= M) {
            C_final.insert((int)K_ll); // Add K to candidate set
             
             // Optimization: Check if doubling K would exceed M to avoid unnecessary work and potential overflow.
             // If K_ll > M/2, then 2*K_ll > M. Check K_ll != 0 to prevent infinite loop if M/2<0 (not possible here).
             if (K_ll > M / 2 && K_ll != 0) { 
                 break; // Stop doubling if next value will exceed M
             }
             if(K_ll == 0) break; // Safety break if somehow K becomes 0
            K_ll *= 2; // Double K for the next iteration
        }
    }

    // Calculate the minimum possible total HP after applying the best operation
    // Initialize minimum HP with the initial total HP (represents the case of performing no operation)
    long long min_total_hp = S_total; 
    
    // Iterate through all candidate K values in the final set
    for (int K : C_final) {
        // K must be a positive integer to be a valid sacrifice HP
        // Also K must be within bounds [1, M] to access Delta[K]
        if (K > 0 && K <= M) { // Check K > 0 and K <= M
           // The final HP sum after sacrificing K is S_total - Delta[K]
           min_total_hp = std::min(min_total_hp, S_total - Delta[K]);
        } 
        // Note: If K > M, Delta[K] would effectively be 0 because no A_i can be a multiple of K > M (since A_i <= M). 
        // The sum would be S_total. This case is already covered by initializing min_total_hp = S_total.
    }

    // Output the minimum total HP found
    std::cout << min_total_hp << std::endl;

    return 0;
}