結果
| 問題 |
No.2398 ヒドラ崩し
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:57:13 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,039 bytes |
| コンパイル時間 | 1,710 ms |
| コンパイル使用メモリ | 112,396 KB |
| 実行使用メモリ | 688,296 KB |
| 最終ジャッジ日時 | 2025-05-14 12:59:06 |
| 合計ジャッジ時間 | 5,385 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 15 WA * 9 MLE * 1 -- * 6 |
ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <stdexcept> // For exception handling
#include <string_view> // Used for efficient substring operations without copying
using namespace std;
// Map for memoization: stores computed Grundy values for Hydra strings.
// Using std::string as key because std::string_view requires careful lifetime management
// which is tricky with recursive calls potentially creating temporary strings.
map<string, int> grundy_values;
// Forward declaration of the main recursive function
int calculate_grundy(const string& h);
/**
* @brief Parses a Hydra string `h` to identify its structure based on the problem definition.
* Finds the decomposition into `prefix` and `last_component`.
* The `last_component` is the rightmost primitive Hydra component, which is either "()"
* or of the form "(k)" where k is a Hydra.
*
* @param h The Hydra string to parse.
* @param prefix Output parameter for the part of the string before the last component.
* @param last_component Output parameter for the last primitive component string.
* @return true if parsing is successful, false otherwise.
*/
bool parse_hydra_last_component(const string& h, string& prefix, string& last_component) {
if (h.empty()) return false; // Cannot parse empty string
int balance = 0;
int split_pos = -1; // Position of the '(' that starts the last component
// Iterate from right to left to find the beginning of the last top-level component
for (int i = h.length() - 1; i >= 0; --i) {
if (h[i] == ')') {
balance++;
} else { // h[i] == '('
balance--;
}
// When balance becomes 0, we have found a potential component boundary.
// If this boundary starts with '(', it marks the beginning of the last primitive component.
if (balance == 0 && h[i] == '(') {
split_pos = i;
break;
}
}
// Case 1: Found a component like `(...)` covering the suffix
if (split_pos != -1) {
prefix = h.substr(0, split_pos);
last_component = h.substr(split_pos);
// Basic validation: check if it conforms to `(...)` structure. Length must be at least 2.
if (last_component.length() < 2 || last_component.front() != '(' || last_component.back() != ')') {
// This indicates potential parsing error or invalid Hydra structure.
return false;
}
return true;
}
// Case 2: The string ends with `()` but not as part of a larger `(...)` suffix component. E.g., `(())()`
// This check covers cases where the last primitive component is simply `()`.
if (h.length() >= 2 && h.substr(h.length() - 2) == "()") {
prefix = h.substr(0, h.length() - 2);
last_component = "()";
return true;
}
// Case 3: The entire string `h` is a single primitive hydra like `()` or `(())`.
// Check if `h` starts with '(' and ends with ')', and the content inside is a valid balanced Hydra structure.
if (h.length() >= 2 && h.front() == '(' && h.back() == ')') {
int check_balance = 0;
bool balanced_internal = true;
// Validate the balance of parentheses strictly inside the outer pair
for(size_t i = 1; i < h.length() - 1; ++i) {
if (h[i] == '(') check_balance++;
else check_balance--;
// If balance drops below 0, it means ')' appeared before matching '('. Invalid structure.
if (check_balance < 0) { balanced_internal = false; break; }
}
// Final balance must be 0 for the internal part to be a valid Hydra (or empty string).
if (balanced_internal && check_balance == 0) {
prefix = ""; // No prefix, the whole string is the last component.
last_component = h;
return true;
}
}
// If none of the known structures match, parsing fails.
return false;
}
/**
* @brief Computes the state h[1] for a given Hydra h.
* This function is used as a helper, particularly for Subcase 2.2 logic.
* Throws runtime_error on parsing failure or unexpected structure.
*
* @param h The Hydra string.
* @return The resulting Hydra string after applying the [1] operation.
*/
string compute_h_1(const string& h) {
string prefix, last_component;
// Attempt to parse the Hydra structure.
if (!parse_hydra_last_component(h, prefix, last_component)) {
// If standard parsing fails, re-attempt specific edge cases like h = "()"
// This logic could be integrated better into parse_hydra_last_component.
if (h == "()") {
prefix = ""; last_component = "()";
} else {
throw runtime_error("compute_h_1 parse failed: " + h);
}
}
// Case 1 based on definition: h = h'() => h[1] = h'
if (last_component == "()") {
return prefix;
}
// Case 2 based on definition: h = h0 + (h1)
else {
string h1 = last_component.substr(1, last_component.length() - 2);
// h1 must be non-empty because last_component is not "()"
if (h1.empty()) throw runtime_error("compute_h_1: h1 empty for " + h); // Should not happen
// Check if h1 fits Subcase 2.1: h1 = h1'()
bool h1_ends_in_empty_parens = (h1.length() >= 2 && h1.substr(h1.length() - 2) == "()");
if (h1_ends_in_empty_parens) { // Subcase 2.1 applies to h: h[1] = prefix + (h1')
string h1_prime = h1.substr(0, h1.length() - 2);
return prefix + "(" + h1_prime + ")";
} else { // Subcase 2.2 applies to h: h[1] = prefix + (h1[1])
// Recursively compute h1[1]
string h1_1 = compute_h_1(h1);
return prefix + "(" + h1_1 + ")";
}
}
}
// Define maximum string length and map size limits to prevent resource exhaustion.
const size_t MAX_STRING_LENGTH = 400000; // Heuristic based on typical contest limits + buffer
const size_t MAX_MAP_SIZE = 500000; // Max states to memoize. Adjust based on memory limits.
/**
* @brief Calculates the Grundy value (or Nim-sum) for a given Hydra state `h`.
* Uses memoization to store results and avoid recomputation.
* Implements the recursive definition of the game moves h -> h[n].
*
* @param h The Hydra string representing the current game state.
* @return The Grundy value of state h.
*/
int calculate_grundy(const string& h) {
// Base case: The empty string (dead Hydra) is a terminal state with Grundy value 0.
if (h.empty()) {
return 0;
}
// Check memoization table first.
auto it = grundy_values.find(h);
if (it != grundy_values.end()) {
return it->second;
}
// Limit state space explored to prevent excessive resource usage.
if (grundy_values.size() > MAX_MAP_SIZE) {
throw runtime_error("State space limit exceeded");
}
// Set to store Grundy values of reachable next states.
set<int> next_grundy_values;
string prefix, last_component;
// Parse the Hydra string to determine its structure for applying game rules.
if (!parse_hydra_last_component(h, prefix, last_component)) {
throw runtime_error("Failed to parse hydra: " + h);
}
// Apply game rules based on the Hydra structure:
// Case 1: h = prefix + "()". This corresponds to `h = h'()` in problem statement.
if (last_component == "()") {
// For any n >= 1, h[n] = prefix. There's only one next state.
next_grundy_values.insert(calculate_grundy(prefix));
}
// Case 2: h = prefix + "(h1)" where h1 is a non-empty Hydra. Corresponds to `h = h0 (h1)`.
else {
// Extract h1 from "(h1)" structure.
string h1 = last_component.substr(1, last_component.length() - 2);
// Ensure h1 is not empty. This should hold if last_component is not "()".
if (h1.empty()) throw runtime_error("Case 2 error: h1 is empty for " + h);
// Check if h1 matches Subcase 2.1 structure: h1 = h1'()
bool h1_ends_in_empty_parens = (h1.length() >= 2 && h1.substr(h1.length() - 2) == "()");
if (h1_ends_in_empty_parens) {
// Subcase 2.1: h1 = h1'()
string h1_prime = h1.substr(0, h1.length() - 2);
// Construct the component (h1') used in state transitions.
string P_h1_prime = "(" + h1_prime + ")";
// State for n=1: h[1] = prefix + (h1')
string h_1 = prefix + P_h1_prime;
// Check length before recursive call.
if (h_1.length() > MAX_STRING_LENGTH) throw runtime_error("String length limit exceeded: h[1]");
next_grundy_values.insert(calculate_grundy(h_1));
// States for n > 1: h[n] = h[n-1] + (h1'). Generates potentially infinite sequence H'P, H'P^2, ...
string current_h_n = h_1;
// Heuristic loop limit: compute limited number of next states. Grundy values are often small.
int max_k = 300;
for (int k = 2; k <= max_k; ++k) {
// Check string length before appending to prevent excessive growth.
if (current_h_n.length() + P_h1_prime.length() > MAX_STRING_LENGTH) break;
current_h_n += P_h1_prime;
next_grundy_values.insert(calculate_grundy(current_h_n));
// Optimization heuristic: stop early if enough small Grundy values are found
// to determine the mex, assuming mex won't be excessively large.
int current_mex = 0;
while(next_grundy_values.count(current_mex)) current_mex++;
if (k > current_mex + 5) break;
}
} else {
// Subcase 2.2: h1 is live and does not end in "()".
// Rule: h[n] = prefix + "(" + h1[n] + ")"
// This rule requires computing h1[n]. This is the most complex case.
// Full implementation requires a function `compute_h_k(h, k)`.
// Simplified approach: Compute only for k=1 as a heuristic. Assumes this is enough to determine the winner.
string h1_1;
try {
// Compute h1[1] using the helper function.
h1_1 = compute_h_1(h1);
} catch (const runtime_error& e) {
// Propagate errors from compute_h_1
throw runtime_error("Error computing h1[1] for h1=" + h1 + ": " + e.what());
} catch (...) {
// Catch any other exceptions during h1[1] computation.
throw runtime_error("Unknown error computing h1[1] for h1=" + h1);
}
// Construct the state h[1] = prefix + (h1[1])
string h_1_state = prefix + "(" + h1_1 + ")";
// Check length constraint.
if (h_1_state.length() > MAX_STRING_LENGTH) throw runtime_error("String length limit exceeded: h[1] in case 2.2");
// Compute Grundy value for this state.
next_grundy_values.insert(calculate_grundy(h_1_state));
// Note: This implementation only considers h[1] for Subcase 2.2.
// This is a major simplification and might be incorrect if moves with n > 1 are critical.
// A full solution would need to handle h[n] for n > 1 in this case.
}
}
// Compute the Mex (Minimum Excluded value) of the set of next state Grundy values.
int mex = 0;
while (next_grundy_values.count(mex)) {
mex++;
}
// Store the computed Grundy value in the memoization table and return it.
return grundy_values[h] = mex;
}
int main() {
// Optimize C++ standard streams
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string H; // Input Hydra string
cin >> H;
try {
// Calculate the Grundy value of the initial state H.
int result_grundy = calculate_grundy(H);
// Determine the winner based on the Grundy value.
// G > 0 means the first player has a winning strategy (N-position).
// G = 0 means the second player has a winning strategy (P-position).
if (result_grundy > 0) {
cout << 0 << endl; // First player (ヒドラ大好きbot) wins
} else {
cout << 1 << endl; // Second player (ヒドラ大好きbot大好きbot) wins
}
} catch (const exception& e) {
// Handle potential runtime errors (e.g., state space limit, parsing issues).
cerr << "Exception: " << e.what() << endl;
// Exit with error status. The problem implies a definite winner exists.
// Failure means our implementation hit limits or has bugs.
return 1;
} catch (...) {
// Catch any other unexpected exceptions.
cerr << "Unknown exception occurred." << endl;
return 1;
}
return 0; // Successful execution
}