概要

望遠鏡が数直線上に並んでいるとき、「最も近い望遠鏡への移動」は各望遠鏡から次に行く先が一意に決まるので、これは 有向グラフ（各頂点の出次数が1）上の \(Q\) 回遷移に帰着できます。あとは サイクル（周期）を見つけて \(Q\) が大きくても高速に答えを求めます。

考察

重要な気づき

数直線上の点について、ある望遠鏡 \(i\)（座標 \(X_i\)）から最も近い望遠鏡は、座標でソートしたときの 左右どちらかの隣に限られます。

• 例えば、座標順に \(\cdots < a < b < c < \cdots\) と並んでいて現在が \(b\) なら、\(b\) から見て一番近い候補は \(a\) または \(c\) だけです。
  \(a\) より左の点は \(a\) より必ず遠く、\(c\) より右の点は \(c\) より必ず遠いからです。

よって、各望遠鏡の「次に移動する望遠鏡」は - 端なら隣の1つに確定 - それ以外なら左右の隣を比べて近い方 - 距離が同じなら番号が小さい方
で \(O(1)\) で決定できます（左右の隣さえ分かればよい）。

素朴なアプローチがダメな理由

• 1回の移動ごとに「全ての望遠鏡との距離」を調べると \(O(N)\)、それを \(Q\) 回で \(O(NQ)\) になり、\(Q \le 10^{18}\) なので不可能です。
• たとえ次の移動先が分かっても、\(Q\) 回をそのままシミュレーションすると \(O(Q)\) でやはり不可能です。

どう解決するか

• まず各望遠鏡 \(i\) からの遷移先 \(nxt[i]\) を前処理で作る（座標ソート＋隣比較）。
• すると「現在地 → 次の望遠鏡」が常に一意に決まるので、全体は 出次数1のグラフ（Functional Graph）になります。
• Functional Graph 上を進むと、必ず 同じ頂点に再到達してサイクルに入るため、
  • サイクルに入るまでの長さ（前置部分）
  • サイクルの長さ
    を求めれば、\(Q\) が巨大でも 剰余で一発で位置が分かります。

アルゴリズム

1. 座標で望遠鏡をソートし、配列 pts = [(座標, 番号), ...] を作る。
2. 各要素 pts[k] について、次の移動先 nxt[番号] を決める。
   • \(k=0\)（最左）なら右隣へ
   • \(k=N-1\)（最右）なら左隣へ
   • それ以外は左右隣 pts[k-1], pts[k+1] の距離
     • \(dl = X_k - X_{k-1}\)、\(dr = X_{k+1} - X_k\)
     • \(dl<dr\) なら左、\(dr<dl\) なら右
     • \(dl=dr\) なら 番号が小さい方
3. 初期位置 S から pos = nxt[pos] を辿り、各望遠鏡を最初に訪れた時刻を visited[pos] に記録する。
   • まだ未訪問なら進む
   • 既訪問の頂点に到達したら、そこからがサイクル
4. cycle_start（サイクル開始時刻）と cycle_len（サイクル長）を使って答えを計算する。
   • \(Q < cycle\_start\) のとき：前置部分にいるので order[Q]
   • それ以外：サイクル内なので
     order[cycle_start + (Q - cycle_start) % cycle_len]

計算量

• 時間計算量: \(O(N \log N)\)（座標ソート） + \(O(N)\)（遷移先決定とサイクル検出）で、全体 \(O(N \log N)\)
• 空間計算量: \(O(N)\)（nxt, visited, order など）

実装のポイント

• 「最も近い望遠鏡」は 座標順の隣だけ見ればよい（この観察が最重要）。

• 距離が同じ場合のタイブレークは 望遠鏡番号が小さい方なので、左右が同距離のとき min(iL, iR) にする。

• サイクル検出は visited に「初めて訪れたステップ数」を入れると、

  • サイクル開始位置 cycle_start = visited[pos]
  • サイクル長 cycle_len = step - cycle_start を簡単に求められます。

• \(Q\) は \(10^{18}\) なので、必ず サイクル長での剰余を使って計算します。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    S = int(next(it))
    Q = int(next(it))
    X = [int(next(it)) for _ in range(N)]

    pts = sorted((X[i], i + 1) for i in range(N))  # (coord, index)
    nxt = [0] * (N + 1)

    for k, (x, idx) in enumerate(pts):
        if k == 0:
            nxt[idx] = pts[1][1]
        elif k == N - 1:
            nxt[idx] = pts[N - 2][1]
        else:
            xL, iL = pts[k - 1]
            xR, iR = pts[k + 1]
            dl = x - xL
            dr = xR - x
            if dl < dr:
                nxt[idx] = iL
            elif dr < dl:
                nxt[idx] = iR
            else:
                nxt[idx] = iL if iL < iR else iR

    visited = [-1] * (N + 1)
    order = []
    pos = S
    step = 0
    while visited[pos] == -1:
        visited[pos] = step
        order.append(pos)
        pos = nxt[pos]
        step += 1

    cycle_start = visited[pos]
    cycle_len = step - cycle_start

    if Q < cycle_start:
        ans = order[Q]
    else:
        ans = order[cycle_start + (Q - cycle_start) % cycle_len]

    sys.stdout.write(str(ans) + "\n")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。