概要

高橋君と青木君が \(N\) 個のチェックポイントを順に通過する際、各チェックポイント \(i\) (\(i \geq 2\)) において、高橋君の到着時刻が青木君の到着時刻 \(T_i\) より早くなる（追い越す）場所をすべて求める問題です。

考察

高橋君の到着時刻の計算

高橋君は一定の速さ \(V\) で走ります。チェックポイント \(1\) から \(i\) までの合計距離を \(S_i\) とすると、高橋君がチェックポイント \(i\) に到着する時刻 \(A_i\) は以下の式で表せます。 $\(A_i = \frac{S_i}{V}\)\( ここで、\)S_i\( はチェックポイント間の距離 \)D_j\( を用いて、\)Si = \sum{j=1}^{i-1} D_j$ と計算できます。

追い越しの判定条件

問題文より、追い越しの条件は \(A_i < T_i\) です。これを代入すると以下のようになります。 $\(\frac{S_i}{V} < T_i\)$

浮動小数点の回避

コンピュータで小数を扱う場合、精度誤差（丸め誤差）が発生する可能性があります。特に今回の制約では \(T_i\) が \(10^{18}\)、合計距離 \(S_i\) が最大で \((2 \times 10^5) \times 10^9 = 2 \times 10^{14}\) と非常に大きいため、割り算を行うと正確な判定ができない恐れがあります。

そこで、不等式の両辺に \(V\)（常に正）を掛けることで、整数のみの比較に変形します。 $\(S_i < T_i \times V\)$ この変形により、誤差を気にせず正確に判定できるようになります。

数値の大きさ

\(T_i \times V\) の最大値は \(10^{18} \times 10^9 = 10^{27}\) に達します。一般的な 64bit 整数型（C++の long long など）の最大値は約 \(9 \times 10^{18}\) であるため、通常のプログラミング言語ではオーバーフローに注意が必要です。しかし、Python の int 型は自動的に多倍長整数（任意精度）として扱われるため、このような非常に大きな値もそのまま計算・比較することができます。

アルゴリズム

1. 累積距離を保持する変数 current_dist を \(0\) で初期化する。
2. チェックポイント \(i = 2, 3, \dots, N\) について、以下の処理を繰り返す。
   • current_dist に \(D_{i-1}\) を加算する（これで \(S_i\) が求まる）。
   • 不等式 current_dist < T_i * V が成り立つか判定する。
   • 成り立つ場合、その番号 \(i\) を答えのリストに追加する。
3. リストが空なら -1、そうでなければリストの中身を順に出力する。

計算量

• 時間計算量: \(O(N)\)
  • チェックポイントを \(1\) 回ずつ走査するため、入力の読み込みを含めて \(N\) に比例した時間で処理が終わります。
• 空間計算量: \(O(N)\)
  • 入力データおよび答えを格納するリストのサイズが \(N\) に比例します。

実装のポイント

• 高速な入出力: \(N\) が \(2 \times 10^5\) と大きいため、input() を繰り返すよりも sys.stdin.read().split() などで一括して読み込む方が実行時間を短縮できます。

• インデックスの管理: 距離 \(D_i\) と時刻 \(T_i\)、およびチェックポイントの番号の対応関係（1-indexed か 0-indexed か）を間違えないように注意しましょう。コード内では i + 2 を使ってチェックポイント番号を管理しています。

  ソースコード

import sys

def solve():
    # 使用するメモリと時間を最小限にするため、sys.stdin.read().split() で入力を一括読み込みします
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 全ての入力データを整数に変換します
    # Python 3 の int 型は任意精度（多倍長整数）をサポートしているため、
    # 10^27 などの非常に大きな数値でもオーバーフローの心配なく扱えます
    data = list(map(int, input_data))
    
    # N: チェックポイントの数, V: 高橋君の速さ
    N = data[0]
    V = data[1]
    
    # 2行目の D_i (チェックポイント間の距離) は N-1 個与えられます
    # data[2] から data[N] までが D_1, D_2, ..., D_{N-1} です
    # 3行目の T_i (青木君の到着時刻) は N-1 個与えられます
    # data[N+1] から data[2N-1] までが T_2, T_3, ..., T_N です
    
    ans = []
    current_dist = 0
    
    # 高橋君と青木君は時刻 0 にチェックポイント 1 をスタートします
    # チェックポイント i = 2, 3, ..., N について追い越したかどうかを判定します
    for i in range(N - 1):
        # d_i はチェックポイント i+1 から i+2 までの距離 (D_{i+1})
        d_i = data[i + 2]
        # t_i_plus_2 はチェックポイント i+2 に青木君が到着する時刻 (T_{i+2})
        t_i_plus_2 = data[i + N + 1]
        
        # current_dist はチェックポイント 1 から i+2 までの合計距離 (S_{i+2})
        current_dist += d_i
        
        # 高橋君がチェックポイント i+2 に到着する時刻 A_{i+2} は S_{i+2} / V です
        # 問題文の定義により、A_{i+2} < T_{i+2} のとき、高橋君は追い越したことになります
        # 浮動小数点の精度問題を避けるため、不等式を A_{i+2} < T_{i+2} 
        # すなわち S_{i+2} / V < T_{i+2} を S_{i+2} < T_{i+2} * V に変形して判定します
        if current_dist < t_i_plus_2 * V:
            ans.append(i + 2)
            
    # 追い越したチェックポイントが一つもない場合は -1 を出力します
    if not ans:
        print("-1")
    else:
        # 追い越したチェックポイントの番号を小さい順にスペース区切りで出力します
        print(*(ans))

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-preview によって生成されました。