結果
問題 |
No.2278 Time Bomb Game 2
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:52:51 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,205 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 129,144 KB |
最終ジャッジ日時 | 2025-06-12 19:53:52 |
合計ジャッジ時間 | 8,580 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 67 WA * 3 |
ソースコード
N, K, T = map(int, input().split()) c = input().strip() # Precompute nearest B to the left and right for each position (1-based) leftB = [-1] * (N + 2) # 1-based indexing rightB = [-1] * (N + 2) leftA = [-1] * (N + 2) rightA = [-1] * (N + 2) current = -1 for i in range(1, N + 1): if c[i-1] == 'B': current = i leftB[i] = current current = -1 for i in range(N, 0, -1): if c[i-1] == 'B': current = i rightB[i] = current current = -1 for i in range(1, N + 1): if c[i-1] == 'A': current = i leftA[i] = current current = -1 for i in range(N, 0, -1): if c[i-1] == 'A': current = i rightA[i] = current # Compute next move for each position next_pos = [0] * (N + 2) # 1-based for i in range(1, N + 1): if c[i-1] == 'A': # Alice's turn: move to nearest B left_b = leftB[i] right_b = rightB[i] left_available = (left_b != -1) and (i > 1) right_available = (right_b != -1) and (i < N) if not left_available and not right_available: next_pos[i] = i continue left_dist = i - left_b if left_available else float('inf') right_dist = right_b - i if right_available else float('inf') if left_dist < right_dist: next_pos[i] = i - 1 elif right_dist < left_dist: next_pos[i] = i + 1 else: if left_available: next_pos[i] = i - 1 else: next_pos[i] = i + 1 else: # Bob's turn: move to nearest A left_a = leftA[i] right_a = rightA[i] left_available = (left_a != -1) and (i > 1) right_available = (right_a != -1) and (i < N) if not left_available and not right_available: next_pos[i] = i continue left_dist = i - left_a if left_available else float('inf') right_dist = right_a - i if right_available else float('inf') if left_dist < right_dist: next_pos[i] = i - 1 elif right_dist < left_dist: next_pos[i] = i + 1 else: if left_available: next_pos[i] = i - 1 else: next_pos[i] = i + 1 # Simulate the moves to detect cycles current = K visited = {} path = [] loop_found = False final_pos = K step = 0 while step <= T: if current in visited: # Found a cycle loop_start = visited[current] loop_length = step - loop_start remaining = T - loop_start if remaining < 0: final_pos = path[T] else: final_pos = path[loop_start + (remaining % loop_length)] loop_found = True break visited[current] = step path.append(current) # Check if next is same as current (no move possible) if next_pos[current] == current: # Stay here for all remaining steps final_pos = current loop_found = True break current = next_pos[current] step += 1 if not loop_found: # T is within the path length final_pos = path[T] # Determine the winner final_char = c[final_pos - 1] # c is 0-based print("Alice" if final_char == 'B' else "Bob")