概要

各チェックポイント \(i\) について「高橋君の到着時刻」と「青木君の到着時刻 \(T_i\)」を比較し、高橋君の方が早い（追い越しが起きる）チェックポイント番号を列挙します。

考察

重要なのは「追い越しはチェックポイント到着時刻の比較だけで判定できる」点です。コース上のどこか途中で並んだとしても、この問題ではチェックポイント \(i\) に高橋君が青木君より先に到着したか（高橋君の到着時刻 \(<\) \(T_i\)）だけを見ます。

高橋君は一定速度 \(V\) で走るので、チェックポイント \(i\) までの累積距離を \(S_i\)（\(1\) 番目を \(0\) とする）とすると、高橋君の到着時刻は - \(S_i / V\) 秒

一方、青木君はチェックポイント \(i\) に時刻 \(T_i\) で到着することが分かっています。

したがって判定は - \(S_i / V < T_i\)

ですが、ここで割り算（特に浮動小数）を使うと誤差で WA になり得ます。また \(S_i\) や \(T_i\) は最大で非常に大きくなるため、正確に整数で比較したいです。

両辺に \(V\) を掛ければ（\(V>0\)） - \(S_i < V \cdot T_i\)

となり、整数同士の比較だけで判定できます。

素朴に「各チェックポイントまでの距離を毎回 1 から足し直す」と \(O(N^2)\) になり、\(N \le 2\times 10^5\) では TLE します。
そこで累積距離を前から 1 回の走査で更新すれば \(O(N)\) で済みます。

（具体例） - \(V=2\), \(D_1=3, D_2=1\) のとき、\(S_2=3, S_3=4\) - \(T_2=2, T_3=3\) なら - \(i=2\): \(S_2 < VT_2 \iff 3 < 4\) → 追い越し - \(i=3\): \(S_3 < VT_3 \iff 4 < 6\) → 追い越し

アルゴリズム

1. 入力を受け取る（\(D_1 \ldots D_{N-1}\) と \(T_2 \ldots T_N\)）。
2. 累積距離 dist を \(0\) で初期化する（これはチェックポイント \(1\) からの距離）。
3. \(i=2\) から \(N\) まで順に
   • dist += D[i-2] としてチェックポイント \(i\) までの距離 \(S_i\) を得る
   • もし dist < V * T[i] なら、チェックポイント \(i\) は追い越しなので答えに追加
4. 答えが空なら -1、そうでなければ番号を小さい順（走査順のまま）に出力する。

計算量

• 時間計算量: \(O(N)\)（1 回の走査のみ）
• 空間計算量: \(O(N)\)（入力配列・出力保持のため）

実装のポイント

• 判定は \(S_i / V < T_i\) ではなく、誤差回避のため \(S_i < V \cdot T_i\) の形で行う。

• 値の最大は大きくなり得ますが、Python の整数は多倍長なのでオーバーフローしません（他言語なら 128bit などに注意）。

• 入力が大きいので sys.stdin.buffer.read() を使って高速に読み取ると安全です。

  ソースコード

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    V = next(it)

    D = [next(it) for _ in range(N - 1)]
    T = [0] * (N + 1)
    for i in range(2, N + 1):
        T[i] = next(it)

    ans = []
    dist = 0
    for i in range(2, N + 1):
        dist += D[i - 2]
        if dist < V * T[i]:
            ans.append(str(i))

    if ans:
        sys.stdout.write(" ".join(ans))
    else:
        sys.stdout.write("-1")

if __name__ == "__main__":
    main()

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