結果

問題 No.2278 Time Bomb Game 2
ユーザー lam6er
提出日時 2025-03-20 20:30:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,287 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 75,384 KB
最終ジャッジ日時 2025-03-20 20:31:56
合計ジャッジ時間 6,584 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 61 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff #

def main():
    import sys
    N, K, T = map(int, sys.stdin.readline().split())
    c = sys.stdin.readline().strip()
    K -= 1  # 0-based index
    
    # Preprocess leftB, rightB, leftA, rightA
    leftB = [-1]*N
    rightB = [-1]*N
    leftA = [-1]*N
    rightA = [-1]*N
    
    # Compute leftB and leftA
    last_B = -1
    last_A = -1
    for i in range(N):
        if c[i] == 'B':
            last_B = i
        if c[i] == 'A':
            last_A = i
        leftB[i] = last_B
        leftA[i] = last_A
    
    # Compute rightB and rightA
    last_B = -1
    last_A = -1
    for i in range(N-1, -1, -1):
        if c[i] == 'B':
            last_B = i
        if c[i] == 'A':
            last_A = i
        rightB[i] = last_B
        rightA[i] = last_A
    
    pos = K
    t = T
    while t > 0:
        current_char = c[pos]
        if current_char == 'A':
            # Alice's turn, find nearest B
            lb = leftB[pos]
            rb = rightB[pos]
            valid_directions = []
            if lb != -1:
                valid_directions.append( (pos - lb, -1) )
            if rb != -1:
                valid_directions.append( (rb - pos, 1) )
        else:
            # Bob's turn, find nearest A
            la = leftA[pos]
            ra = rightA[pos]
            valid_directions = []
            if la != -1:
                valid_directions.append( (pos - la, -1) )
            if ra != -1:
                valid_directions.append( (ra - pos, 1) )
        
        if not valid_directions:
            # No possible moves, game ends here
            break
        
        # Choose the closest direction, if tie, choose any
        valid_directions.sort()
        min_dist = valid_directions[0][0]
        possible = [d for d in valid_directions if d[0] == min_dist]
        # Prefer the one that allows higher steps to get out?
        # Let's choose any (e.g., direction=possible[0][1])
        direction = possible[0][1]
        if current_char == 'A':
            if direction == -1:
                target = leftB[pos]
            else:
                target = rightB[pos]
        else:
            if direction == -1:
                target = leftA[pos]
            else:
                target = rightA[pos]
        
        dist = abs(target - pos)
        if dist == 0:
            # Already at target (not possible here, as target is valid)
            break
        
        if dist > t:
            # Can't reach target, move as much as possible
            new_pos = pos + direction * t
            t = 0
        else:
            # Move to target, update pos and t
            t -= dist
            pos = target
        
        # Check if in boundary and handle oscillation
        if t > 0:
            # Check if at boundary
            left_end = (pos == 0)
            right_end = (pos == N-1)
            if left_end or right_end:
                # Can't move further, no more steps matter
                t = 0
            else:
                # Check if next move is possible and leads to oscillation
                # next direction is only possible to move back (since we are in target)
                # Determine the direction of oscillation based on remaining steps
                # For example, after reaching target, we might oscillate between pos and pos + direction
                # but since the player may change, it's unclear. Instead, check if we can start oscillations
                # However, the optimal strategy would be to move back and forth in the same direction
                # This part is complex and might require considering remaining steps and the current player
                # But given the optimal strategy, if the next move's player's target is back, it will oscillate
                cycle = 2  # time to complete one cycle (back and forth)
                cycles = t // cycle
                remaining = t % cycle
                if remaining == 0:
                    # ends at current position
                    pos = pos
                else:
                    # move one step back
                    pos += -direction
                t = 0
    
    # Determine the result
    if c[pos] == 'A':
        print("Bob")
    else:
        print("Alice")

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