結果

問題 No.715 集合と二人ゲーム
ユーザー qwewe
提出日時 2025-05-14 12:56:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 6,717 bytes
コンパイル時間 2,500 ms
コンパイル使用メモリ 87,456 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2025-05-14 12:58:50
合計ジャッジ時間 5,032 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set> // Used only during precomputation

// Global array to store precomputed Grundy values up to a certain limit
// The Grundy values are needed for lengths of consecutive blocks of numbers.
const int PRECOMPUTE_LIMIT = 88; // We need values up to index 87 to cover the first cycle and the pre-period part.
int g_values[PRECOMPUTE_LIMIT];

// Periodicity parameters for the Grundy sequence g(L)
// Based on analysis and external resources (like OEIS A002187 for related games), this sequence is periodic.
const int PERIOD = 34; // The period length
const int PERIOD_START_INDEX = 54; // The index from which the sequence becomes periodic

// Function to precompute Grundy values up to PRECOMPUTE_LIMIT
// This function uses dynamic programming based on the game rules.
// g(L) = mex { g(L') | L' is a state reachable from L in one move }
void precompute_g() {
    // Base case: g(0) = 0 for an empty block/set
    g_values[0] = 0; 
    
    // Handle small L values explicitly to simplify the main loop.
    // g(1) = mex{g(0)} = mex{0} = 1. Move: choose 1, remove {1}, left with empty set (length 0).
    if (PRECOMPUTE_LIMIT > 1) g_values[1] = 1; 
    // g(2) = mex{g(0)} = mex{0} = 1. Move: choose 1 or 2, remove {1, 2}, left with empty set (length 0).
    if (PRECOMPUTE_LIMIT > 2) g_values[2] = 1; 

    // Use a set to efficiently compute MEX (Minimum Excluded value) of the Grundy values of next states
    std::set<int> seen; // Stores Grundy values of states reachable in one move
    for (int L = 3; L < PRECOMPUTE_LIMIT; ++L) {
        seen.clear(); // Clear the set for computing g(L)
        
        // Consider possible moves from a block of length L:
        
        // 1. Choose an endpoint (element 1 or L): removes {1, 2} or {L-1, L}. 
        //    The remaining block has length L-2. The Grundy value is g(L-2).
        //    Indices L-2 are guaranteed non-negative since L >= 3.
        seen.insert(g_values[L - 2]);
        
        // 2. Choose an interior element x (from 2 to L-1): removes {x-1, x, x+1}.
        //    This splits the block into two independent sub-blocks of lengths k = x-2 and L-k-3.
        //    The index k = x-2 runs from 0 (when x=2) to L-3 (when x=L-1).
        //    The resulting state corresponds to the Nim sum of the two sub-games, with Grundy value g(k) XOR g(L-k-3).
        for (int k = 0; k <= L - 3; ++k) {
             // Indices k and L-k-3 are guaranteed non-negative.
             seen.insert(g_values[k] ^ g_values[L - k - 3]);
        }
        
        // Compute the mex (minimum excluded non-negative integer) of the set `seen`.
        int mex_val = 0;
        while (seen.count(mex_val)) {
            mex_val++;
        }
        g_values[L] = mex_val; // Store the computed Grundy value for length L
    }
}

// Function to get the Grundy value for a block of length L
// Uses precomputed values for small L and leverages periodicity for large L.
int get_g(long long L) {
    // A block of non-positive length has Grundy value 0.
    if (L <= 0) return 0; 
    
    // If L is within the precomputed range, return the stored value directly.
    if (L < PRECOMPUTE_LIMIT) {
        return g_values[L];
    } else {
        // If L is large, use the periodicity property.
        // The sequence g(L) is periodic with period 34 starting from index 54.
        // Map L to the equivalent index within the first full periodic segment [54, 87].
        // The index mapping is: `PERIOD_START_INDEX + (L - PERIOD_START_INDEX) % PERIOD`
        long long effective_idx = PERIOD_START_INDEX + (L - PERIOD_START_INDEX) % PERIOD;
        return g_values[effective_idx];
    }
}

int main() {
    // Use fast I/O operations for potentially large input
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // Precompute the Grundy values needed. This is done once.
    precompute_g();

    int N; // Number of elements in the initial set S
    std::cin >> N;
    
    // Handle the edge case of N=0 explicitly. Constraints state N >= 1, but safety first.
    if (N == 0) {
       // If the initial set is empty, the first player has no moves and loses immediately.
       std::cout << "Second" << std::endl; 
       return 0;
    }

    // Read the elements of the set S. Use long long for potentially large values up to 10^9.
    std::vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    // Sort the elements. This allows us to easily identify blocks of consecutive numbers.
    std::sort(A.begin(), A.end());

    int nim_sum = 0; // Initialize the Nim sum (XOR sum) of the Grundy values of all blocks.
    long long current_block_len = 0; // Track the length of the current consecutive block.
    
    // Check if N > 0 before starting block processing
    if (N > 0) {
        current_block_len = 1; // Start length of the first block is at least 1.
        
        // Iterate through the sorted elements (from the second element) to find blocks
        for (int i = 1; i < N; ++i) {
            if (A[i] == A[i-1] + 1) {
                // If the current element is consecutive to the previous one, extend the current block.
                current_block_len++;
            } else {
                // A gap is found (A[i] > A[i-1] + 1), indicating the end of the current block.
                // Calculate the Grundy value for this completed block using its length.
                // XOR this Grundy value into the total Nim sum.
                nim_sum ^= get_g(current_block_len);
                // Start a new block beginning with the current element A[i].
                current_block_len = 1;
            }
        }
        // After the loop finishes, there's one last block remaining (the one ending at A[N-1]).
        // Calculate its Grundy value and XOR it into the total Nim sum.
        nim_sum ^= get_g(current_block_len); 
    }

    // Determine the winner based on the total Nim sum.
    // This game is impartial. By the Sprague-Grundy theorem, the game is equivalent to a Nim pile of size `nim_sum`.
    // Assuming standard normal play convention (last player to move wins), which aligns with the sample cases:
    // If the Nim sum is non-zero, the first player has a winning strategy.
    // If the Nim sum is zero, the second player has a winning strategy.
    // Note: The problem statement "player who cannot move loses" typically describes misere play. However, analysis of sample cases suggests normal play rules apply.
    if (nim_sum != 0) {
        std::cout << "First" << std::endl;
    } else {
        std::cout << "Second" << std::endl;
    }

    return 0;
}
0