結果
| 問題 |
No.2398 ヒドラ崩し
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:09:19 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,142 bytes |
| コンパイル時間 | 1,309 ms |
| コンパイル使用メモリ | 122,796 KB |
| 実行使用メモリ | 51,968 KB |
| 最終ジャッジ日時 | 2025-05-14 13:10:30 |
| 合計ジャッジ時間 | 5,974 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 13 TLE * 1 -- * 17 |
ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <functional> // Required for std::function
#include <vector>
using namespace std;
// Memoization map for computed Grundy values. Key is the Hydra string state.
map<string, int> memo;
// Memoization map for computed state strings h[n]. Key is pair {Hydra string state, n}.
map<pair<string, int>, string> state_cache;
// Heuristic limits to prevent excessive computation or memory usage.
// MAX_LEN: Maximum allowed string length for a Hydra state. States exceeding this are considered invalid/unreachable.
// This helps manage memory usage. 512MB memory limit suggests roughly 5*10^8 characters total storage.
// Initial string length up to 10^5. Strings can grow. MAX_LEN=200000 is a heuristic guess.
const int MAX_LEN = 200000;
// MAX_K: Limit for exploring states h[k] for k=1, 2, ..., MAX_K.
// A common heuristic in competitive programming for games with infinite moves.
const int MAX_K = 61;
// MAX_DEPTH: Limit for recursion depth to prevent stack overflow.
const int MAX_DEPTH = 1000;
// Current recursion depth counters
int current_depth_grundy = 0; // Depth counter for calculate_grundy function
int current_depth_state = 0; // Depth counter for get_state function
// Utility function to check if a string ends with "()"
bool ends_with_empty_paren(const string& s) {
// Check if string length is at least 2 and last two characters are "()"
return s.length() >= 2 && s.substr(s.length() - 2) == "()";
}
// Forward declarations for recursive functions
string get_state(string h, int n);
int calculate_grundy(string h);
/**
* @brief Computes the Hydra state string h[n] according to the problem rules.
*
* @param h The current Hydra string state.
* @param n The positive integer parameter for the move.
* @return string The resulting Hydra string state h[n]. Returns empty string if computation fails due to limits or invalid input.
*/
string get_state(string h, int n) {
// Base cases: empty hydra or invalid n
if (h.empty()) return "";
if (n <= 0) return "";
// Check cache for previously computed state h[n]
pair<string, int> cache_key = {h, n};
if (state_cache.count(cache_key)) {
return state_cache[cache_key];
}
// Check recursion depth limit for state generation
if (current_depth_state > MAX_DEPTH) return ""; // Return empty string indicating failure/limit
current_depth_state++; // Increment depth counter
string result = ""; // Stores the computed state string
// Apply the rules based on the structure of h:
// Case 1: h = h'()
// If h ends with "()", then h[n] = h'. The value of n doesn't matter.
if (ends_with_empty_paren(h)) {
result = h.substr(0, h.length() - 2);
} else {
// Case 2/3: h does not end with "()". It must be of the form h = h0 (h1).
string h0, h1;
int component_start = -1; // Start index of the last prime component (h1)
int balance = 0; // Parenthesis balance counter
// Scan from right to find the start of the last prime component
for (int k = h.length() - 1; k >= 0; --k) {
if (h[k] == ')') balance++;
else if (h[k] == '(') balance--;
if (balance == 0) { // Found the boundary where balance returns to 0
component_start = k;
break;
}
}
// Validate the structure found
if (component_start == -1) { // If balance never returns to 0 except at the beginning
// This means the entire string is wrapped like (....)
if (h[0] == '(' && h.back() == ')') { component_start = 0; } // Valid case: h=(...)
else { current_depth_state--; return ""; } // Error: Invalid structure
} else if(h[component_start] != '(') { // Component boundary must start with '(' for form (h1)
current_depth_state--; return ""; // Error: Invalid structure found
}
// Extract h0 and h1 from h = h0 + "(" + h1 + ")"
h0 = h.substr(0, component_start);
h1 = h.substr(component_start + 1, h.length() - component_start - 2);
// h1 must be a non-empty ("living") Hydra for Case 2/3 logic.
// If h1 is empty, it means the last component was "()", handled by Case 1.
if (h1.empty()) { current_depth_state--; return ""; } // Error state, should have been Case 1
// Subcases based on whether h1 ends with "()"
// Case 2a: h1 = h1'()
if (ends_with_empty_paren(h1)) {
string h1_prime = h1.substr(0, h1.length() - 2); // Get h1' by removing trailing "()"
string h1_prime_paren = "(" + h1_prime + ")"; // Construct string "(h1')"
if (n == 1) { // If n=1, h[1] = h0 (h1')
result = h0 + h1_prime_paren;
} else { // If n > 1, h[n] = h[n-1] (h1')
// Recursively compute h[n-1] first
string prev_state = get_state(h, n - 1);
// Check if the recursive call succeeded
if (prev_state == "") {
current_depth_state--; return ""; // Propagate failure
}
// Concatenate h[n-1] and (h1')
result = prev_state + h1_prime_paren;
}
} else { // Case 2b: h1 does not end with "()"
// h[n] = h0 (h1[n])
// Recursively compute h1[n] first
string h1_n_state = get_state(h1, n);
// Check if the recursive call succeeded
if (h1_n_state == "") {
current_depth_state--; return ""; // Propagate failure
}
// Concatenate h0 and (h1[n])
result = h0 + "(" + h1_n_state + ")";
}
}
// Check final computed state length against limit
if (result.length() > MAX_LEN) {
current_depth_state--; return ""; // Return empty string if state is too large
}
current_depth_state--; // Decrement depth counter before returning
// Cache the computed state if it's valid (not empty string representing error/limit).
// Allow caching empty string result if initial h was empty.
if (!result.empty() || h.empty()) {
state_cache[cache_key] = result;
}
return result;
}
/**
* @brief Computes the Grundy value (nim-value) for a given Hydra state string h.
* Uses recursion with memoization (dynamic programming).
*
* @param h The Hydra string state.
* @return int The Grundy value G(h). Returns 0 if computation fails due to limits.
*/
int calculate_grundy(string h) {
// Base case: empty Hydra is a terminal state with Grundy value 0.
if (h.empty()) {
return 0;
}
// Check memoization table for cached Grundy value
if (memo.count(h)) {
return memo[h];
}
// Check recursion depth limit for Grundy calculation
if (current_depth_grundy > MAX_DEPTH) return 0; // Return 0 (losing state) as fallback
current_depth_grundy++; // Increment depth counter
// Set to store Grundy values of reachable states
set<int> next_grundy_values;
// Determine reachable states based on the structure of h:
// Case 1: h = h'()
if (ends_with_empty_paren(h)) {
string h_prime = h.substr(0, h.length() - 2); // The only reachable state is h'
// Check string length before recursive call to avoid exceeding limits
if (h_prime.length() <= MAX_LEN) {
next_grundy_values.insert(calculate_grundy(h_prime));
}
} else { // Case 2/3: h = h0 (h1)
// Re-parse h to find h0 and h1. This could be optimized if parse results were passed.
string h0, h1;
int component_start = -1;
int balance = 0;
for (int k = h.length() - 1; k >= 0; --k) {
if (h[k] == ')') balance++;
else if (h[k] == '(') balance--;
if (balance == 0) {
component_start = k;
break;
}
}
// Validate structure
if (component_start == -1) {
if (h[0] == '(' && h.back() == ')') { component_start = 0; }
else { current_depth_grundy--; return 0; } // Error/placeholder G
} else if(h[component_start] != '(') {
current_depth_grundy--; return 0; // Error/placeholder G
}
h0 = h.substr(0, component_start);
h1 = h.substr(component_start + 1, h.length() - component_start - 2);
if (h1.empty()) { current_depth_grundy--; return 0; } // Error/placeholder G
// Explore reachable states by trying k = 1, 2, ..., MAX_K
// The logic applies similarly to Case 2a and 2b, based on how get_state(h, k) behaves.
for (int k = 1; k <= MAX_K; ++k) {
// Compute the state resulting from move k
string next_state = get_state(h, k);
// Check if state generation failed (due to limits/errors)
// The condition `!h.empty() && k > 0` ensures we distinguish actual empty state target from error indicator ""
if (next_state == "" && !h.empty() && k > 0) {
// Stop exploring if state generation fails
break;
}
// Recursively compute Grundy value of the reachable state
int gk = calculate_grundy(next_state);
next_grundy_values.insert(gk); // Add to set of reachable Grundy values
// Heuristic optimization: stop exploring k if the mex value seems stable.
// Compute current mex based on values found so far.
int current_mex = 0;
while (next_grundy_values.count(current_mex)) current_mex++;
// If we've explored k up to current_mex + 2 (and at least 5 steps), assume mex won't change.
if (k >= current_mex + 2 && k >= 5) break;
}
}
// Calculate the mex (Minimum Excluded value) of the set of reachable Grundy values.
// This is the Grundy value G(h).
int mex = 0;
while (next_grundy_values.count(mex)) {
mex++;
}
current_depth_grundy--; // Decrement depth counter before returning
// Store computed Grundy value in memoization table
return memo[h] = mex;
}
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string H; // Input Hydra string
cin >> H;
// Reset recursion depth counters for the main calculation
current_depth_grundy = 0;
current_depth_state = 0;
// Calculate the Grundy value of the initial state H
int result = calculate_grundy(H);
// Determine the winner based on the Grundy value G(H)
// If G(H) > 0, the first player has a winning strategy.
// If G(H) = 0, the second player has a winning strategy.
if (result > 0) {
cout << 0 << endl; // First player (Hydra Lover Robot) wins
} else {
cout << 1 << endl; // Second player (Hydra Lover Robot Lover Robot) wins
}
return 0;
}