結果
問題 |
No.2278 Time Bomb Game 2
|
ユーザー |
![]() |
提出日時 | 2025-06-12 14:47:02 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,060 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,592 KB |
実行使用メモリ | 128,052 KB |
最終ジャッジ日時 | 2025-06-12 14:49:10 |
合計ジャッジ時間 | 6,855 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 67 WA * 3 |
ソースコード
def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]); idx +=1 K = int(input[idx])-1 # convert to 0-based idx +=1 T = int(input[idx]); idx +=1 c = input[idx] idx +=1 # Precompute for A positions: nearest B to left and right left_B = [-1]*N right_B = [-1]*N # Precompute left_B last_B = -1 for i in range(N): if c[i] == 'B': last_B = i left_B[i] = last_B # Precompute right_B last_B = -1 for i in range(N-1, -1, -1): if c[i] == 'B': last_B = i right_B[i] = last_B # Precompute for B positions: nearest A to left and right left_A = [-1]*N right_A = [-1]*N last_A = -1 for i in range(N): if c[i] == 'A': last_A = i left_A[i] = last_A last_A = -1 for i in range(N-1, -1, -1): if c[i] == 'A': last_A = i right_A[i] = last_A current_pos = K remaining = T visited = dict() steps = 0 cycle_found = False while remaining > 0: key = (current_pos, remaining % 2) if key in visited: # Cycle detected cycle_start = visited[key] cycle_length = steps - cycle_start if cycle_length <= 0: break # no progress, avoid infinite loop remaining_steps = remaining remaining_after_cycle = remaining_steps % cycle_length # Simulate remaining_after_cycle steps for _ in range(remaining_after_cycle): # Compute next_pos current_char = c[current_pos] if current_char == 'A': left = left_B[current_pos] right = right_B[current_pos] if left == -1 and right == -1: # move left if possible else right if current_pos > 0: current_pos -=1 else: current_pos +=1 else: dist_left = current_pos - left if left != -1 else float('inf') dist_right = right - current_pos if right != -1 else float('inf') if dist_left < dist_right: current_pos -=1 elif dist_right < dist_left: current_pos +=1 else: # equidistant, choose left if possible if left != -1 and current_pos > 0: current_pos -=1 else: current_pos +=1 else: # current_char is 'B' left = left_A[current_pos] right = right_A[current_pos] if left == -1 and right == -1: # move left if possible else right if current_pos > 0: current_pos -=1 else: current_pos +=1 else: dist_left = current_pos - left if left != -1 else float('inf') dist_right = right - current_pos if right != -1 else float('inf') if dist_left < dist_right: current_pos -=1 elif dist_right < dist_left: current_pos +=1 else: if left != -1 and current_pos > 0: current_pos -=1 else: current_pos +=1 remaining -=1 if remaining ==0: break cycle_found = True break else: visited[key] = steps # Compute next_pos current_char = c[current_pos] if current_char == 'A': left = left_B[current_pos] right = right_B[current_pos] if left == -1 and right == -1: # move left if possible else right if current_pos > 0: current_pos -=1 else: current_pos +=1 else: dist_left = current_pos - left if left != -1 else float('inf') dist_right = right - current_pos if right != -1 else float('inf') if dist_left < dist_right: current_pos -=1 elif dist_right < dist_left: current_pos +=1 else: # equidistant, choose left if possible if left != -1 and current_pos > 0: current_pos -=1 else: current_pos +=1 else: # current_char is 'B' left = left_A[current_pos] right = right_A[current_pos] if left == -1 and right == -1: # move left if possible else right if current_pos > 0: current_pos -=1 else: current_pos +=1 else: dist_left = current_pos - left if left != -1 else float('inf') dist_right = right - current_pos if right != -1 else float('inf') if dist_left < dist_right: current_pos -=1 elif dist_right < dist_left: current_pos +=1 else: if left != -1 and current_pos > 0: current_pos -=1 else: current_pos +=1 remaining -=1 steps +=1 final_char = c[current_pos] if final_char == 'A': print('Bob') else: print('Alice') if __name__ == '__main__': main()