結果

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

ソースコード

diff #

N, K, T = map(int, input().split())
c = input().strip()

# Precompute nearest B to the left and right for each position (1-based)
leftB = [-1] * (N + 2)  # 1-based indexing
rightB = [-1] * (N + 2)
leftA = [-1] * (N + 2)
rightA = [-1] * (N + 2)

current = -1
for i in range(1, N + 1):
    if c[i-1] == 'B':
        current = i
    leftB[i] = current

current = -1
for i in range(N, 0, -1):
    if c[i-1] == 'B':
        current = i
    rightB[i] = current

current = -1
for i in range(1, N + 1):
    if c[i-1] == 'A':
        current = i
    leftA[i] = current

current = -1
for i in range(N, 0, -1):
    if c[i-1] == 'A':
        current = i
    rightA[i] = current

# Compute next move for each position
next_pos = [0] * (N + 2)  # 1-based

for i in range(1, N + 1):
    if c[i-1] == 'A':
        # Alice's turn: move to nearest B
        left_b = leftB[i]
        right_b = rightB[i]
        left_available = (left_b != -1) and (i > 1)
        right_available = (right_b != -1) and (i < N)
        if not left_available and not right_available:
            next_pos[i] = i
            continue
        left_dist = i - left_b if left_available else float('inf')
        right_dist = right_b - i if right_available else float('inf')
        if left_dist < right_dist:
            next_pos[i] = i - 1
        elif right_dist < left_dist:
            next_pos[i] = i + 1
        else:
            if left_available:
                next_pos[i] = i - 1
            else:
                next_pos[i] = i + 1
    else:
        # Bob's turn: move to nearest A
        left_a = leftA[i]
        right_a = rightA[i]
        left_available = (left_a != -1) and (i > 1)
        right_available = (right_a != -1) and (i < N)
        if not left_available and not right_available:
            next_pos[i] = i
            continue
        left_dist = i - left_a if left_available else float('inf')
        right_dist = right_a - i if right_available else float('inf')
        if left_dist < right_dist:
            next_pos[i] = i - 1
        elif right_dist < left_dist:
            next_pos[i] = i + 1
        else:
            if left_available:
                next_pos[i] = i - 1
            else:
                next_pos[i] = i + 1

# Simulate the moves to detect cycles
current = K
visited = {}
path = []
loop_found = False
final_pos = K
step = 0

while step <= T:
    if current in visited:
        # Found a cycle
        loop_start = visited[current]
        loop_length = step - loop_start
        remaining = T - loop_start
        if remaining < 0:
            final_pos = path[T]
        else:
            final_pos = path[loop_start + (remaining % loop_length)]
        loop_found = True
        break
    visited[current] = step
    path.append(current)
    # Check if next is same as current (no move possible)
    if next_pos[current] == current:
        # Stay here for all remaining steps
        final_pos = current
        loop_found = True
        break
    current = next_pos[current]
    step += 1

if not loop_found:
    # T is within the path length
    final_pos = path[T]

# Determine the winner
final_char = c[final_pos - 1]  # c is 0-based
print("Alice" if final_char == 'B' else "Bob")
0