結果

問題 No.2278 Time Bomb Game 2
ユーザー gew1fw
提出日時 2025-06-12 19:52:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,331 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 70,912 KB
最終ジャッジ日時 2025-06-12 19:53:01
合計ジャッジ時間 6,787 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 67 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, k, t = map(int, input().split())
c = input().strip()
k -= 1  # convert to 0-based index

# Precompute nearest B to the left and right for each position
left_B = [-1] * n
last_B = -1
for i in range(n):
    if c[i] == 'B':
        last_B = i
    left_B[i] = last_B

right_B = [-1] * n
last_B = -1
for i in range(n-1, -1, -1):
    if c[i] == 'B':
        last_B = i
    right_B[i] = last_B

# Precompute nearest A to the left and right for each position
left_A = [-1] * n
last_A = -1
for i in range(n):
    if c[i] == 'A':
        last_A = i
    left_A[i] = last_A

right_A = [-1] * n
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_steps = t
visited = {}

while remaining_steps > 0:
    current_char = c[current_pos]
    state = (current_pos, current_char)
    if state in visited:
        prev_remaining = visited[state]
        cycle_length = prev_remaining - remaining_steps
        if cycle_length <= 0:
            break  # no progress, avoid infinite loop
        num_cycles = remaining_steps // cycle_length
        remaining_steps -= num_cycles * cycle_length
        visited = {}  # reset to avoid reprocessing the same cycle
        continue
    visited[state] = remaining_steps

    if current_char == 'A':
        left_b = left_B[current_pos]
        right_b = right_B[current_pos]
        if left_b == -1 and right_b == -1:
            # All A's, Alice can't reach B, final cell is A
            print("Bob")
            exit()
        if left_b == -1:
            direction = 1
            distance = right_b - current_pos
        elif right_b == -1:
            direction = -1
            distance = current_pos - left_b
        else:
            left_dist = current_pos - left_b
            right_dist = right_b - current_pos
            if left_dist < right_dist:
                direction = -1
                distance = left_dist
            elif right_dist < left_dist:
                direction = 1
                distance = right_dist
            else:
                # equidistant, choose left
                direction = -1
                distance = left_dist
    else:
        left_a = left_A[current_pos]
        right_a = right_A[current_pos]
        if left_a == -1 and right_a == -1:
            # All B's, Bob can't reach A, final cell is B
            print("Alice")
            exit()
        if left_a == -1:
            direction = 1
            distance = right_a - current_pos
        elif right_a == -1:
            direction = -1
            distance = current_pos - left_a
        else:
            left_dist = current_pos - left_a
            right_dist = right_a - current_pos
            if left_dist < right_dist:
                direction = -1
                distance = left_dist
            elif right_dist < left_dist:
                direction = 1
                distance = right_dist
            else:
                # equidistant, choose left
                direction = -1
                distance = left_dist

    if distance <= remaining_steps:
        remaining_steps -= distance
        current_pos += direction * distance
    else:
        current_pos += direction * remaining_steps
        remaining_steps = 0

final_char = c[current_pos]
print("Alice" if final_char == 'B' else "Bob")
0