結果
問題 |
No.2278 Time Bomb Game 2
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()