結果
| 問題 | 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 |
ソースコード
#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;
}