結果

問題 No.1816 MUL-DIV Game
ユーザー qwewe
提出日時 2025-05-14 12:58:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 44 ms / 2,000 ms
コード長 4,450 bytes
コンパイル時間 561 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2025-05-14 12:59:24
合計ジャッジ時間 2,173 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm> // Needed for std::prev

// Main function
int main() {
    // Faster I/O for competitive programming
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N; // Number of integers
    std::cin >> N;
    
    // Use std::multiset to store the numbers on the blackboard.
    // A multiset keeps elements sorted automatically, which is useful for finding
    // the smallest and largest elements efficiently.
    // Use long long type to handle potentially large products, up to 10^18.
    // The maximum initial value is 10^9, so 10^9 * 10^9 = 10^18 fits within long long.
    std::multiset<long long> board;
    for (int i = 0; i < N; ++i) {
        long long A_i;
        std::cin >> A_i;
        board.insert(A_i);
    }
    
    // If N=1, the game ends immediately before any move.
    // The only number on the board is the answer.
    if (N == 1) {
        // Since N >= 1 and A_i >= 1 are guaranteed by constraints,
        // the board is non-empty. We can safely access the first element.
        std::cout << *board.begin() << std::endl;
        return 0;
    }
    
    // Game simulation for N > 1
    bool alice_turn = true; // Alice goes first
    
    // The game continues until only one number remains.
    // This requires exactly N-1 moves in total.
    for (int k = 0; k < N - 1; ++k) {
        // The loop invariant ensures board.size() >= 2 before each iteration starts.
        // This is because we start with N >= 2, and each step reduces the size by 1.
        // The loop runs N-1 times, ending when the size becomes 1.
        
        if (alice_turn) {
            // Alice's move: Maximize the final result.
            // Her operation is multiplication. Intuitively, multiplying larger numbers leads to larger results.
            // However, Bob wants to minimize and can remove large numbers.
            // A strategy analysis suggests Alice might want to protect large numbers.
            // Multiplying the smallest two numbers seems to be a good strategy for Alice.
            // It avoids creating extremely large numbers early that Bob can target,
            // potentially allowing more moderately large numbers to survive.
            
            long long x = *board.begin(); // Get the smallest element
            board.erase(board.begin());   // Remove it from the multiset
            long long y = *board.begin(); // Get the new smallest element (second smallest originally)
            board.erase(board.begin());   // Remove it
            
            // Calculate the product and insert it back.
            // Potential overflow is handled by using long long.
            board.insert(x * y); 
        } else {
            // Bob's move: Minimize the final result.
            // His operation is ceiling division: ceil(x/y).
            // Bob can always choose x and y such that ceil(min(x,y)/max(x,y)) = 1.
            // For example, pick any two numbers a, b. Let x=min(a,b), y=max(a,b). Then ceil(x/y)=1.
            // Since Bob wants to minimize the final result, making a 1 is generally his best move.
            // To make this move most effective, Bob should remove the largest numbers from the board.
            // This prevents Alice from using them in later multiplications.
            
            // Get an iterator to the largest element (which is the last element in std::multiset)
            auto it_y = std::prev(board.end()); 
            board.erase(it_y); // Remove the largest element
            
            // Get an iterator to the new largest element (which was the second largest initially)
            // Since the board size was >= 2 before this move, after removing one element,
            // it's guaranteed to have at least one element left.
            auto it_x = std::prev(board.end());
            board.erase(it_x); // Remove this element as well
            
            // Insert 1 into the multiset, representing the result of Bob's division.
            board.insert(1LL); 
        }
        
        // Switch turns for the next iteration
        alice_turn = !alice_turn; 
    }
    
    // After N-1 moves, exactly one number remains on the board.
    // This number is the final answer. Since the board contains exactly one element,
    // *board.begin() gives that element.
    std::cout << *board.begin() << std::endl;
    
    return 0;
}
0