概要

数直線上に並んだ \(N\) 個の望遠鏡に対して、「現在地から最も近い望遠鏡へ移動する」操作を \(Q\) 回繰り返したとき、最終的にいる望遠鏡の番号を求める問題です。\(Q\) が最大 \(10^{18}\) と非常に大きいため、周期検出（サイクル検出）を用いて効率的に求めます。

考察

重要な気づき①：最近傍は座標ソート上の隣接要素

ある望遠鏡 \(i\) に対して「最も距離が近い望遠鏡」は、座標でソートしたときの 左隣 か 右隣 のどちらかです。これはソート済み配列で自分より離れた望遠鏡は、隣接する望遠鏡よりも必ず遠くなるためです。

例えば座標が \([1, 3, 7, 10]\) のとき、座標 \(7\) の望遠鏡にとって最も近いのは \(3\)（距離4）か \(10\)（距離3）のいずれかで、\(1\)（距離6）は候補になりません。

したがって、各望遠鏡の「次に移動する先」は \(O(1)\) で前計算できます。

重要な気づき②：素朴なシミュレーションではTLE

\(Q\) が最大 \(10^{18}\) なので、1ステップずつシミュレーションすると到底間に合いません。

解決策：サイクル検出

移動先は現在いる望遠鏡だけで決まる（状態が望遠鏡番号1つ）ため、遷移関数 \(\text{nxt}[i]\) は 決定的 です。状態空間は \(N\) 個しかないので、最大 \(N\) ステップ以内に必ず以前訪れた状態に戻り、周期（サイクル） が発生します。

サイクルを検出すれば、残りのステップ数を周期で割った余りだけ進めれば答えが求まります。

アルゴリズム

1. 座標ソート: 望遠鏡を座標順にソートし、各望遠鏡のソート上の位置を記録する。
2. 遷移先の前計算: 各望遠鏡 \(i\) について、ソート上の左隣・右隣の距離を比較し、距離が小さい方（同距離なら番号が小さい方）を \(\text{nxt}[i]\) とする。
3. サイクル検出付きシミュレーション:
   • 望遠鏡 \(S\) からスタートし、訪問した望遠鏡とそのステップ番号を記録する。
   • すでに訪問済みの望遠鏡に到達したら、サイクルの開始位置 \(c\) と周期長 \(L\) を特定する。
   • 答えは、記録したパスの \(c + (Q - c) \mod L\) 番目の要素。
4. サイクル検出前に \(Q\) ステップ終了したら、その時点の望遠鏡が答え。

具体例

\(N=3, S=1, Q=5\)、座標 \(X = [0, 2, 3]\) の場合：

• \(\text{nxt}[0] = 1\)（望遠鏡1→2、距離2）
• \(\text{nxt}[1] = 2\)（望遠鏡2→3、距離1）
• \(\text{nxt}[2] = 1\)（望遠鏡3→2、距離1）

パス：\(0 \to 1 \to 2 \to 1 \to 2 \to 1\)（0-indexed）。ステップ3で状態1に再訪、周期は \(2\)。\(Q=5\) ステップ後の答えは \(\text{path}[1 + (5-1)\%2] = \text{path}[1] = 1\)、つまり望遠鏡 2。

計算量

• 時間計算量: \(O(N \log N)\)（ソート）+ \(O(N)\)（サイクル検出、最大 \(N\) ステップ）= \(O(N \log N)\)
• 空間計算量: \(O(N)\)（ソート配列、遷移配列、訪問記録）

実装のポイント

• 0-indexed と 1-indexed の変換: 内部処理は 0-indexed で行い、最後に \(+1\) して出力する。

• 距離が同じ場合の処理: 左隣と右隣が同距離の場合、元の番号が小さい方 を選ぶ。座標順の隣接ではなく、元の番号での比較であることに注意。

• サイクル検出の方法: 辞書（ハッシュマップ）で各状態の初出ステップを記録する方法がシンプルで実装しやすい。状態数が高々 \(N\) なので十分高速。

  ソースコード

import sys
from bisect import bisect_left

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    S = int(input_data[1])
    Q = int(input_data[2])
    X = [int(input_data[3 + i]) for i in range(N)]
    
    # For each telescope, precompute the nearest telescope (by distance, then by index)
    # Sort telescopes by coordinate
    # For telescope i, nearest is determined by coordinate neighbors in sorted order
    
    # Create sorted list of (coordinate, original_index)
    telescopes = sorted(range(N), key=lambda i: X[i])
    # sorted_coords[k] = coordinate of the k-th telescope in sorted order
    sorted_coords = [X[telescopes[k]] for k in range(N)]
    # pos_in_sorted[i] = position of telescope i in sorted order
    pos_in_sorted = [0] * N
    for k in range(N):
        pos_in_sorted[telescopes[k]] = k
    
    # For each telescope (by original index i), find nearest telescope
    def get_nearest(i):
        k = pos_in_sorted[i]
        xi = X[i]
        best_dist = float('inf')
        best_idx = -1
        
        # Check left neighbor in sorted order
        if k > 0:
            j = telescopes[k - 1]
            d = xi - X[j]  # positive since sorted
            if d < best_dist or (d == best_dist and j < best_idx):
                best_dist = d
                best_idx = j
        
        # Check right neighbor in sorted order
        if k < N - 1:
            j = telescopes[k + 1]
            d = X[j] - xi  # positive since sorted
            if d < best_dist or (d == best_dist and j < best_idx):
                best_dist = d
                best_idx = j
        
        return best_idx
    
    # The nearest telescope is always one of the adjacent telescopes in sorted coordinate order.
    # So we can precompute next[i] for each telescope i.
    
    nxt = [0] * N
    for i in range(N):
        nxt[i] = get_nearest(i)
    
    # Now we need to follow the chain starting from S-1 (0-indexed) for Q steps.
    # Q can be up to 10^12, so we need cycle detection.
    
    # Since the function is deterministic and the state space is finite (N states),
    # there must be a cycle. Find it.
    
    current = S - 1  # 0-indexed
    
    # Use Floyd's or just track visited states
    # With N up to 2*10^5, we can store the path until we find a repeat
    
    visited = {}
    path = []
    pos = 0
    
    while pos < Q:
        if current in visited:
            # Found cycle
            cycle_start = visited[current]
            cycle_len = pos - cycle_start
            remaining = Q - pos
            remaining_mod = remaining % cycle_len
            # We need to advance remaining_mod more steps from current position
            # But we also need to do the steps from cycle_start to cycle_start + remaining_mod
            # Actually current state at pos is same as at cycle_start
            # So answer is path[cycle_start + (Q - cycle_start) % cycle_len]
            total_remaining = Q - cycle_start
            idx = total_remaining % cycle_len
            print(path[cycle_start + idx] + 1)
            return
        
        visited[current] = pos
        path.append(current)
        current = nxt[current]
        pos += 1
    
    # If we exit without finding cycle, current is the answer
    print(current + 1)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。