結果

問題 No.2278 Time Bomb Game 2
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0