概要

高橋君が青木君を追い越すチェックポイントを求める問題です。

考察

高橋君は一定の速度 \(V\) で進み、青木君は各チェックポイントに到着する時刻 \(T_i\) が与えられています。
高橋君がチェックポイント \(i\) に到着する時刻は、そこまでの累積距離を速度 \(V\) で割った値になります。
チェックポイント \(i\) までの累積距離を \(S_i = D_1 + D_2 + \cdots + D_{i-1}\) とすると、到着時刻は \(\frac{S_i}{V}\) です。
この値が \(T_i\) よりも小さければ、高橋君は青木君よりも先にそのチェックポイントに到着しているので「追い越し」となります。

素朴な方法として、各チェックポイントごとに累積和を毎回計算すると、時間計算量が \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) ではTLEします。
そこで、累積和を前計算しておけば、各チェックポイントに対して定数時間で判定できます。

また、浮動小数点数を使うと誤差が発生する可能性があるため、比較の際には整数のまま扱う工夫が必要です。
具体的には、\(\frac{S_i}{V} < T_i\) の不等式を \(S_i < V \cdot T_i\) という形で比較することで、整数同士の計算だけで判定できます。

アルゴリズム

1. 各チェックポイントまでの距離の累積和 \(S_i = D_1 + \cdots + D_{i-1}\) を前計算する（Python の itertools.accumulate を使うと便利）。
2. 各チェックポイント \(i = 2, 3, ..., N\) について、
   $\( S_{i-1} < V \cdot T_{i-1} \)\( を判定し、条件を満たせばその \)i$ を答えに追加する。
3. 答えがあれば昇順に出力、なければ -1 を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 累積和は1-indexedのように扱い、チェックポイント \(i\) に対応させるために添字の調整が必要です。
• 浮動小数点演算を使わず、整数同士の比較を行うことで精度を保ちます。
• 入力を高速に読み込むために sys.stdin.read を使用しています。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    V = int(data[1])
    
    D = [int(d) for d in data[2 : 2 + N - 1]]
    T = [int(t) for t in data[2 + N - 1 : 2 + N - 1 + N - 1]]
    
    # 累積距離 (1-indexed from checkpoint 2)
    cum_dist = list(accumulate(D))
    
    # 条件: cum_dist[i-2] / V < T[i-2] => cum_dist[i-2] < V * T[i-2]
    overtakes = [str(i + 2) for i in range(N - 1) if cum_dist[i] < V * T[i]]
    
    if overtakes:
        print(' '.join(overtakes))
    else:
        print(-1)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。