結果

問題 No.2278 Time Bomb Game 2
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:25:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,382 bytes
コンパイル時間 397 ms
コンパイル使用メモリ 81,460 KB
実行使用メモリ 128,328 KB
最終ジャッジ日時 2025-04-16 16:27:54
合計ジャッジ時間 8,536 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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]); idx +=1
    T = int(input[idx]); idx +=1
    c = input[idx].strip()
    idx +=1
    
    INF = float('inf')
    
    # Precompute left_B and right_B
    left_B = [INF] * (N + 2)
    prev = -INF
    for i in range(1, N+1):
        if c[i-1] == 'B':
            prev = i
            left_B[i] = 0
        else:
            if prev != -INF:
                left_B[i] = i - prev
            else:
                left_B[i] = INF
    
    right_B = [INF] * (N + 2)
    prev = INF
    for i in range(N, 0, -1):
        if c[i-1] == 'B':
            prev = i
            right_B[i] = 0
        else:
            if prev != INF:
                right_B[i] = prev - i
            else:
                right_B[i] = INF
    
    # Precompute left_A and right_A
    left_A = [INF] * (N + 2)
    prev = -INF
    for i in range(1, N+1):
        if c[i-1] == 'A':
            prev = i
            left_A[i] = 0
        else:
            if prev != -INF:
                left_A[i] = i - prev
            else:
                left_A[i] = INF
    
    right_A = [INF] * (N + 2)
    prev = INF
    for i in range(N, 0, -1):
        if c[i-1] == 'A':
            prev = i
            right_A[i] = 0
        else:
            if prev != INF:
                right_A[i] = prev - i
            else:
                right_A[i] = INF
    
    # Determine next_i for each position
    next_i = [0] * (N + 2)
    for i in range(1, N+1):
        if c[i-1] == 'A':
            left_dist = left_B[i]
            right_dist = right_B[i]
            if left_dist < right_dist:
                next_i[i] = i - 1
            elif right_dist < left_dist:
                next_i[i] = i + 1
            else:
                # Tie, choose left if possible
                if i > 1:
                    next_i[i] = i - 1
                else:
                    next_i[i] = i + 1
        else:
            left_dist = left_A[i]
            right_dist = right_A[i]
            if left_dist < right_dist:
                next_i[i] = i - 1
            elif right_dist < left_dist:
                next_i[i] = i + 1
            else:
                # Tie, choose left if possible
                if i > 1:
                    next_i[i] = i - 1
                else:
                    next_i[i] = i + 1
    
    # Simulate the path with cycle detection
    path = []
    pos_map = dict()
    current_pos = K
    steps = 0
    final_pos = None
    while steps < T:
        if current_pos in pos_map:
            # Cycle detected
            cycle_start = pos_map[current_pos]
            cycle_length = steps - cycle_start
            remaining_steps = T - cycle_start
            if remaining_steps <= 0:
                final_pos = path[cycle_start + remaining_steps]
                break
            mod = remaining_steps % cycle_length
            final_pos_index = cycle_start + mod
            final_pos = path[final_pos_index]
            break
        else:
            pos_map[current_pos] = steps
            path.append(current_pos)
            current_pos = next_i[current_pos]
            steps += 1
    else:
        final_pos = current_pos
    
    if c[final_pos - 1] == 'A':
        print("Bob")
    else:
        print("Alice")

if __name__ == "__main__":
    main()
0