結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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