結果
問題 |
No.2278 Time Bomb Game 2
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:25:57 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,382 bytes |
コンパイル時間 | 397 ms |
コンパイル使用メモリ | 81,460 KB |
実行使用メモリ | 128,328 KB |
最終ジャッジ日時 | 2025-04-16 16:27:54 |
合計ジャッジ時間 | 8,536 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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]); idx +=1 T = int(input[idx]); idx +=1 c = input[idx].strip() idx +=1 INF = float('inf') # Precompute left_B and right_B left_B = [INF] * (N + 2) prev = -INF for i in range(1, N+1): if c[i-1] == 'B': prev = i left_B[i] = 0 else: if prev != -INF: left_B[i] = i - prev else: left_B[i] = INF right_B = [INF] * (N + 2) prev = INF for i in range(N, 0, -1): if c[i-1] == 'B': prev = i right_B[i] = 0 else: if prev != INF: right_B[i] = prev - i else: right_B[i] = INF # Precompute left_A and right_A left_A = [INF] * (N + 2) prev = -INF for i in range(1, N+1): if c[i-1] == 'A': prev = i left_A[i] = 0 else: if prev != -INF: left_A[i] = i - prev else: left_A[i] = INF right_A = [INF] * (N + 2) prev = INF for i in range(N, 0, -1): if c[i-1] == 'A': prev = i right_A[i] = 0 else: if prev != INF: right_A[i] = prev - i else: right_A[i] = INF # Determine next_i for each position next_i = [0] * (N + 2) for i in range(1, N+1): if c[i-1] == 'A': left_dist = left_B[i] right_dist = right_B[i] if left_dist < right_dist: next_i[i] = i - 1 elif right_dist < left_dist: next_i[i] = i + 1 else: # Tie, choose left if possible if i > 1: next_i[i] = i - 1 else: next_i[i] = i + 1 else: left_dist = left_A[i] right_dist = right_A[i] if left_dist < right_dist: next_i[i] = i - 1 elif right_dist < left_dist: next_i[i] = i + 1 else: # Tie, choose left if possible if i > 1: next_i[i] = i - 1 else: next_i[i] = i + 1 # Simulate the path with cycle detection path = [] pos_map = dict() current_pos = K steps = 0 final_pos = None while steps < T: if current_pos in pos_map: # Cycle detected cycle_start = pos_map[current_pos] cycle_length = steps - cycle_start remaining_steps = T - cycle_start if remaining_steps <= 0: final_pos = path[cycle_start + remaining_steps] break mod = remaining_steps % cycle_length final_pos_index = cycle_start + mod final_pos = path[final_pos_index] break else: pos_map[current_pos] = steps path.append(current_pos) current_pos = next_i[current_pos] steps += 1 else: final_pos = current_pos if c[final_pos - 1] == 'A': print("Bob") else: print("Alice") if __name__ == "__main__": main()