結果
問題 |
No.2278 Time Bomb Game 2
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:19:09 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,745 bytes |
コンパイル時間 | 458 ms |
コンパイル使用メモリ | 81,896 KB |
実行使用メモリ | 132,736 KB |
最終ジャッジ日時 | 2025-04-16 00:21:03 |
合計ジャッジ時間 | 12,368 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 67 WA * 3 |
ソースコード
import sys def main(): import sys N, K, T = map(int, sys.stdin.readline().split()) c = sys.stdin.readline().strip() # Precompute left_B and right_B for each position left_B = [-1] * (N + 2) # 1-based to N last_B = -1 for i in range(1, N + 1): if c[i-1] == 'B': last_B = i left_B[i] = last_B right_B = [-1] * (N + 2) next_B = N + 1 for i in range(N, 0, -1): if c[i-1] == 'B': next_B = i right_B[i] = next_B # Precompute left_A and right_A for each position left_A = [-1] * (N + 2) last_A = -1 for i in range(1, N + 1): if c[i-1] == 'A': last_A = i left_A[i] = last_A right_A = [-1] * (N + 2) next_A = N + 1 for i in range(N, 0, -1): if c[i-1] == 'A': next_A = i right_A[i] = next_A # Compute next_i for each cell next_i = [0] * (N + 2) # 1-based to N for i in range(1, N + 1): if c[i-1] == 'A': # Alice's turn, find nearest B if left_B[i] == -1 and right_B[i] == N + 1: # No B's, move left if possible else right if i > 1: next_i[i] = i - 1 else: next_i[i] = i + 1 else: dl = i - left_B[i] if left_B[i] != -1 else float('inf') dr = right_B[i] - i if right_B[i] != N + 1 else float('inf') if dl < dr: desired_dir = 'left' elif dr < dl: desired_dir = 'right' else: desired_dir = 'left' # tie-breaker if desired_dir == 'left': if i > 1: next_i[i] = i - 1 else: next_i[i] = i + 1 else: if i < N: next_i[i] = i + 1 else: next_i[i] = i - 1 else: # Bob's turn, find nearest A if left_A[i] == -1 and right_A[i] == N + 1: # No A's, move left if possible else right if i > 1: next_i[i] = i - 1 else: next_i[i] = i + 1 else: dl = i - left_A[i] if left_A[i] != -1 else float('inf') dr = right_A[i] - i if right_A[i] != N + 1 else float('inf') if dl < dr: desired_dir = 'left' elif dr < dl: desired_dir = 'right' else: desired_dir = 'left' # tie-breaker if desired_dir == 'left': if i > 1: next_i[i] = i - 1 else: next_i[i] = i + 1 else: if i < N: next_i[i] = i + 1 else: next_i[i] = i - 1 # Build binary lifting table log_max = T.bit_length() up = [[0] * (N + 2) for _ in range(log_max + 1)] for i in range(1, N + 1): up[0][i] = next_i[i] for k in range(1, log_max + 1): for i in range(1, N + 1): up[k][i] = up[k-1][up[k-1][i]] # Compute final position after T steps current = K remaining = T for k in range(log_max, -1, -1): if (1 << k) <= remaining: current = up[k][current] remaining -= (1 << k) if remaining == 0: break # Determine the winner if c[current - 1] == 'B': print("Alice") else: print("Bob") if __name__ == '__main__': main()