結果
| 問題 |
No.2278 Time Bomb Game 2
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:07:17 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,240 bytes |
| コンパイル時間 | 1,852 ms |
| コンパイル使用メモリ | 77,112 KB |
| 実行使用メモリ | 12,324 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:02 |
| 合計ジャッジ時間 | 6,278 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 8 TLE * 1 -- * 61 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric> // Not strictly needed, but good to include if potentially using vector ops
// Function to compute the next state vector based on the game rules
// Takes the current size N, the current AliceWins state vector `current_aw`,
// and the character configuration `c` of the squares.
// Returns the state vector for the next step (t' - 1).
std::vector<char> compute_next_state(int N, const std::vector<char>& current_aw, const std::vector<char>& c) {
// Initialize the state vector for the next step (t' - 1)
std::vector<char> next_aw(N + 1);
// N>=2 is guaranteed by problem constraints, so boundary squares 1 and N always have one neighbor.
// Iterate through all squares from 1 to N to compute their state for the next step
for (int p = 1; p <= N; ++p) {
// Handle boundary cases: square 1 and square N
if (p == 1) {
// At square 1, the only possible move is to square 2.
// The outcome depends solely on the state at square 2 in the previous step (current_aw[2]).
// This holds regardless of whether it's Alice's or Bob's turn at square 1.
next_aw[p] = current_aw[p + 1];
} else if (p == N) {
// At square N, the only possible move is to square N-1.
// The outcome depends solely on the state at square N-1 in the previous step (current_aw[N-1]).
next_aw[p] = current_aw[p - 1];
} else {
// Handle interior squares (1 < p < N)
// Get the outcomes from the adjacent squares in the previous step
char left_aw = current_aw[p - 1];
char right_aw = current_aw[p + 1];
// Determine the outcome based on whose turn it is at square p
if (c[p] == 'A') { // Alice's turn
// Alice wins if she can make *any* move to a state where she wins.
// Logical OR represents this choice.
next_aw[p] = left_aw || right_aw;
} else { // Bob's turn (c[p] == 'B')
// Bob wins if he can make *any* move to a state where Alice loses (Bob wins).
// Alice wins only if *all* of Bob's available moves lead to states where Alice wins.
// Logical AND represents this condition.
next_aw[p] = left_aw && right_aw;
}
}
}
return next_aw; // Return the computed state vector for the next step
}
int main() {
// Use fast I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
long long N_ll; // Use long long for input N potentially large, though problem says int range
int N;
long long K_ll; // Use long long for input K
int K;
long long T; // T can be very large (up to 10^9)
std::cin >> N_ll >> K_ll >> T;
N = (int)N_ll; // Cast N to int as it fits within int limits
K = (int)K_ll; // Cast K to int
std::string c_str; // Read the character string
std::cin >> c_str;
std::vector<char> c(N + 1); // Create 1-indexed character vector for squares
for(int i=0; i<N; ++i) c[i+1] = c_str[i];
// Initialize the state vector `initial_aw`. `initial_aw[p] = 1` means Alice wins if game ends at p after 0 moves remaining.
// This corresponds to the base case t'=0. Alice wins if c[p] == 'B'.
std::vector<char> initial_aw(N + 1); // Using char: 1 for True (Alice Wins), 0 for False (Bob Wins)
for (int p = 1; p <= N; ++p) {
initial_aw[p] = (c[p] == 'B');
}
// Handle the trivial case T=0: Game ends immediately at the start position K.
if (T == 0) {
if (initial_aw[K]) { // Check if Alice wins at square K with 0 moves.
std::cout << "Alice" << std::endl;
} else {
std::cout << "Bob" << std::endl;
}
return 0; // End program
}
// Use Floyd's cycle-finding algorithm (tortoise and hare) to detect periodicity in game states
std::vector<char> tortoise = initial_aw; // Tortoise starts at initial state
std::vector<char> hare = initial_aw; // Hare starts at initial state
long long steps_tortoise = 0; // Track steps taken by tortoise
long long steps_hare = 0; // Track steps taken by hare
bool cycle_found = false; // Flag to indicate if a cycle is detected
// The main loop for cycle detection
while (true) {
// Tortoise moves one step forward
if (steps_tortoise >= T) break; // If tortoise reaches T steps, stop detection
tortoise = compute_next_state(N, tortoise, c);
steps_tortoise++;
// Hare moves two steps forward
// First step for hare
if (steps_hare >= T) break; // If hare reaches T steps, stop detection
hare = compute_next_state(N, hare, c);
steps_hare++;
// Second step for hare
if (steps_hare >= T) break; // If hare reaches T steps after first move, stop detection
hare = compute_next_state(N, hare, c);
steps_hare++;
// Check if tortoise and hare meet
if (tortoise == hare) {
cycle_found = true; // Cycle detected
break; // Exit loop
}
// Safety break if hare somehow completed T steps (already checked, but good practice)
if (steps_hare >= T) break;
}
std::vector<char> final_state; // Vector to store the final state after T steps
if (cycle_found) {
// A cycle was detected within T steps. Now determine the cycle properties.
// Find the length of the preperiod (steps before cycle starts)
std::vector<char> ptr1 = initial_aw; // Pointer starting from initial state
long long preperiod = 0;
std::vector<char> tortoise_at_meet = tortoise; // State where tortoise and hare met
// Advance both pointers one step at a time until they meet. The meeting point is the start of the cycle.
while (ptr1 != tortoise_at_meet) {
ptr1 = compute_next_state(N, ptr1, c);
tortoise_at_meet = compute_next_state(N, tortoise_at_meet, c);
preperiod++;
}
// Now ptr1 is at the start of the cycle state (state V_preperiod)
// Find the length of the period (cycle length)
long long period = 1;
std::vector<char> ptr2 = compute_next_state(N, ptr1, c); // Start ptr2 one step into the cycle
// Advance ptr2 until it returns to the cycle start state (ptr1)
while (ptr1 != ptr2) {
ptr2 = compute_next_state(N, ptr2, c);
period++;
}
// Calculate the target state index corresponding to T steps remaining
long long target_T;
// If T is within the preperiod, the target state is simply V_T
if (T < preperiod) {
target_T = T;
} else {
// If T is beyond the preperiod, find the equivalent step within the cycle
// Period must be positive since cycle was detected
target_T = preperiod + (T - preperiod) % period;
}
// Compute the state at target_T steps starting from the initial state
final_state = initial_aw;
for (long long i = 0; i < target_T; ++i) {
final_state = compute_next_state(N, final_state, c);
}
} else {
// No cycle was detected within T steps.
// This implies T is small enough that the state sequence hasn't repeated yet,
// or the total number of steps T is less than required to complete the cycle detection logic.
// We need the state after exactly T steps. Recompute it from the start.
final_state = initial_aw;
for(long long i = 0; i < T; ++i) {
final_state = compute_next_state(N, final_state, c);
}
}
// Output the final result based on the state at square K after T steps
if (final_state[K]) { // Check if Alice wins in the final state at position K
std::cout << "Alice" << std::endl;
} else {
std::cout << "Bob" << std::endl;
}
return 0; // Successful execution
}