結果
| 問題 |
No.2278 Time Bomb Game 2
|
| コンテスト | |
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 19:55:53 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,060 bytes |
| コンパイル時間 | 178 ms |
| コンパイル使用メモリ | 82,552 KB |
| 実行使用メモリ | 127,960 KB |
| 最終ジャッジ日時 | 2025-06-12 19:56:52 |
| 合計ジャッジ時間 | 7,697 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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()