概要

数直線上に配置された \(N\) 個の望遠鏡を、現在地から最も近いものへ移動するというルールに従って \(Q\) 回移動した後の位置を求める問題です。

考察

\(Q\) が最大 \(10^{18}\) と非常に大きいため、1回ずつ愚直に移動をシミュレーションするとTLE（実行時間制限超過）になってしまいます。

しかし、この問題の移動ルールには「次に移動する先は、現在いる望遠鏡のみによって一意に決まる」という性質があります。望遠鏡は全部で \(N\) 個（最大 \(2 \times 10^5\)）しかないため、移動を続けていくと必ず \(N\) 回以内に過去に訪れたことのある望遠鏡に到達します。一度訪れた望遠鏡に戻ってくると、以降は全く同じ経路を無限に繰り返す（ループに入る）ことになります。 この「ループ（周期性）」を利用すれば、残りの莫大な移動回数を割り算の余りを使って一気にスキップすることができます。

また、ある望遠鏡から最も近い望遠鏡を探す際、毎回すべての望遠鏡を調べると \(O(N)\) かかってしまいますが、あらかじめ望遠鏡を座標順にソートしておけば、最も近い望遠鏡の候補は「左隣」か「右隣」の2つだけに絞られます。

アルゴリズム

1. 前計算（移動先の決定）
   • 望遠鏡の情報を (座標, 元の番号) のペアとして配列に格納し、座標の昇順にソートします。
   • ソート後の各望遠鏡について、次に移動する望遠鏡の番号 nxt[i] を求めます。
     • 一番左端の望遠鏡は右隣へ、一番右端の望遠鏡は左隣へ必ず移動します。
     • それ以外の望遠鏡は、左隣と右隣への距離を比較し、距離が短い方へ移動します。距離が等しい場合は、問題文の条件に従って「元の番号」が小さい方を選びます。
2. ループ検出とシミュレーション
   • 初期位置 \(S\) から出発し、nxt に従って移動をシミュレーションします。
   • このとき、各望遠鏡に「何ステップ目で到達したか」を配列 visited に記録し、移動の履歴を配列 path に順次追加していきます。
   • \(Q\) 回移動しきる前に、すでに visited に記録がある（過去に訪れた）望遠鏡に到達した場合、ループに入ったことがわかります。
3. 答えの算出
   • ループの開始ステップを loop_start、ループの周期（1周の長さ）を loop_len とします。
   • ループを検出した時点で、残っている移動回数は Q - loop_start 回です。これを周期 loop_len で割った余りを rem とします。
   • 最終的な位置は、移動履歴 path の loop_start + rem 番目に記録されている望遠鏡になります。

計算量

• 時間計算量: \(O(N \log N)\)
  • 望遠鏡の座標のソートに \(O(N \log N)\) かかります。
  • 各望遠鏡の移動先の決定（nxt の構築）に \(O(N)\) かかります。
  • シミュレーションは最大でも \(N\) 回でループを検出するため \(O(N)\) で完了します。
  • 全体として \(O(N \log N)\) となり、制約下で十分に高速です。
• 空間計算量: \(O(N)\)
  • 望遠鏡の座標データ、移動先配列 nxt、訪問記録 visited、経路記録 path などを保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 元の番号の保持: 座標でソートすると元の番号（1〜N）の順番がバラバラになるため、ソート前に (座標, 番号) の形でデータを保持しておくことが重要です。

• 距離が同じ場合の処理: 距離が同じ場合は「番号が最も小さい望遠鏡」を選びますが、ここで比較するのは「ソート後のインデックス」ではなく「元の望遠鏡の番号」であることに注意してください。

• インデックスの管理: Python等の言語では配列のインデックスが 0 始まりですが、望遠鏡の番号は 1 始まりです。配列 nxt や visited のサイズを \(N+1\) にして、望遠鏡の番号をそのままインデックスとして使えるようにすると、実装がシンプルでバグを防ぎやすくなります。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    S = int(input_data[1])
    Q = int(input_data[2])
    
    X = [(int(input_data[3+i]), i+1) for i in range(N)]
    X.sort(key=lambda x: x[0])
    
    nxt = [0] * (N + 1)
    nxt[X[0][1]] = X[1][1]
    nxt[X[-1][1]] = X[-2][1]
    
    for j in range(1, N - 1):
        idx = X[j][1]
        l_idx = j - 1
        r_idx = j + 1
        
        dist_l = X[j][0] - X[l_idx][0]
        dist_r = X[r_idx][0] - X[j][0]
        
        if dist_l < dist_r:
            nxt[idx] = X[l_idx][1]
        elif dist_l > dist_r:
            nxt[idx] = X[r_idx][1]
        else:
            nxt[idx] = min(X[l_idx][1], X[r_idx][1])
            
    visited = [-1] * (N + 1)
    path = []
    
    curr = S
    step = 0
    
    while True:
        if step == Q:
            print(curr)
            return
            
        if visited[curr] != -1:
            loop_start = visited[curr]
            loop_len = step - loop_start
            rem = (Q - loop_start) % loop_len
            print(path[loop_start + rem])
            return
            
        visited[curr] = step
        path.append(curr)
        curr = nxt[curr]
        step += 1

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。