概要

数直線上に配置された望遠鏡の間を移動するシミュレーションを行い、\(Q\) 回の移動後にどの望遠鏡にいるかを求める問題。

考察

この問題では、各望遠鏡の座標が与えられ、参加者は現在地から最も近い別の望遠鏡に移動していきます。ただし、直前の位置に戻ることはできません。

愚直に1回ずつ移動をシミュレーションすると、最悪ケースで \(Q = 10^{18}\) 回の移動が必要になり、現実的ではありません（時間的に無理）。しかし、移動は deterministically に行われるため、十分時間が経てば必ずどこかの状態に戻る（周期性を持つ）ことが保証されています。

したがって、「サイクル検出法」を用いて、移動のループを見つけ出し、\(Q\) 回後の状態を効率的に求めることができます。

また、各望遠鏡について最も近い隣接点を高速に見つけるために、座標でソートした配列上で隣接要素だけを候補として考えれば十分です。これにより、毎回全探索する必要がなくなります。

アルゴリズム

1. まず、望遠鏡の座標 \(X_i\) とその番号 \(i\) のペアを持ち、座標順にソートします。
2. 各望遠鏡について、ソート後のリストにおける左隣と右隣の望遠鏡を前処理しておきます。
3. 現在位置から次に移動する望遠鏡を求める関数 get_next を定義します：
   • 現在の望遠鏡の左右隣の望遠鏡との距離を比較し、最も近い（かつ番号が小さい）ものを選びます。
4. 最初の位置からシミュレーションを行いながら、訪れた状態を記録していき、サイクルを見つけ出します。
5. サイクルの開始位置と長さを求め、\(Q\) がどれに対応するかを計算します。
6. 最終的な位置に対応する望遠鏡の番号を出力します。

計算量

• 時間計算量: \(O(N \log N)\)（主にソートと二分探索による初期化）
• 空間計算量: \(O(N)\)

実装のポイント

• ソート後のインデックスと元のインデックスの対応を正確に管理すること。

• サイクル検出は、訪問済みの位置を辞書などで記録しながら行う。

• bisect_left を使って初期位置をソート後の配列上のインデックスに変換している。

• 左右の隣接要素の更新は不要（移動しないので）ため、前処理だけで十分。

  ソースコード

import sys
from bisect import bisect_left

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    S = int(data[1])
    Q = int(data[2])
    X = list(map(int, data[3:3+N]))
    
    # 座標とインデックスのペアを作成し、座標でソート
    indexed_X = [(X[i], i+1) for i in range(N)]
    indexed_X.sort()
    sorted_X = [x[0] for x in indexed_X]
    original_index = [x[1] for x in indexed_X]
    
    # 座標から元のインデックスへのマップ
    pos_to_idx = {x[0]: x[1] for x in indexed_X}
    
    # 各位置における左右の隣接要素を前処理
    left_neighbor = [-1] * N
    right_neighbor = [-1] * N
    
    for i in range(N):
        if i > 0:
            left_neighbor[i] = i - 1
        if i < N - 1:
            right_neighbor[i] = i + 1
    
    # シミュレーション用の関数
    def get_next(current_idx_zero):
        x_curr = sorted_X[current_idx_zero]
        candidates = []
        
        # 左の候補
        l = left_neighbor[current_idx_zero]
        if l != -1:
            dist_l = abs(x_curr - sorted_X[l])
            candidates.append((dist_l, original_index[l], l))
            
        # 右の候補
        r = right_neighbor[current_idx_zero]
        if r != -1:
            dist_r = abs(x_curr - sorted_X[r])
            candidates.append((dist_r, original_index[r], r))
            
        if not candidates:
            return None
            
        candidates.sort()
        _, _, next_idx_zero = candidates[0]
        return next_idx_zero
    
    # 現在位置（ソート後のインデックス）
    current_pos = bisect_left(sorted_X, X[S-1])
    
    # パスの検出
    visited = {}
    path = []
    steps = 0
    pos_in_path = current_pos
    
    while True:
        if current_pos in visited:
            cycle_start = visited[current_pos]
            cycle_length = steps - cycle_start
            break
        visited[current_pos] = steps
        path.append(current_pos)
        steps += 1
        next_pos = get_next(current_pos)
        if next_pos is None:
            # 移動できない場合（あり得ないが念のため）
            cycle_start = steps
            cycle_length = 1
            path.append(current_pos)
            break
        current_pos = next_pos
        
    # Qステップ後の位置を計算
    if Q < cycle_start:
        final_pos_sorted = path[Q]
    else:
        Q_adjusted = (Q - cycle_start) % cycle_length
        final_pos_sorted = path[cycle_start + Q_adjusted]
        
    print(original_index[final_pos_sorted])

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。