概要

高橋君と青木君がマラソンを走り、各チェックポイントで高橋君が青木君より先に到着する（追い越す）チェックポイントをすべて求める問題です。

考察

問題の理解

• 高橋君：一定速度 \(V\) メートル/秒で走る
• 青木君：各チェックポイント \(i\) に時刻 \(T_i\) に到着する（ペースにムラがある）
• 「追い越す」とは、高橋君がチェックポイントに真に早く到着すること

高橋君の到着時刻の計算

チェックポイント \(k\) への高橋君の到着時刻は： $\(\text{高橋君の到着時刻} = \frac{D_1 + D_2 + \cdots + D_{k-1}}{V}\)$

例えば、チェックポイント2への到着時刻は \(\frac{D_1}{V}\) 秒です。

追い越しの判定条件

チェックポイント \(k\) で追い越すかどうかは： $\(\frac{D_1 + D_2 + \cdots + D_{k-1}}{V} < T_k\)$

浮動小数点数の問題を回避する

上の不等式を素朴に計算すると、割り算によって浮動小数点数の誤差が生じる可能性があります。

これを避けるため、不等式を変形します： $\(D_1 + D_2 + \cdots + D_{k-1} < T_k \times V\)$

こうすることで、整数同士の比較だけで判定できます。

オーバーフローへの注意

\(T_i\) は最大 \(10^{18}\)、\(V\) は最大 \(10^9\) なので、\(T_i \times V\) は最大 \(10^{27}\) 程度になります。Pythonでは多倍長整数を自動的に扱えるため、オーバーフローの心配はありません。

アルゴリズム

1. 距離の累積和 total_distance を0で初期化する
2. \(i = 1, 2, \ldots, N-1\) について以下を繰り返す：
   • total_distance に \(D_i\) を加算（チェックポイント \(i+1\) への総距離）
   • total_distance < T[i] * V なら、チェックポイント \(i+1\) で追い越している
   • 追い越していれば結果リストに追加
3. 結果リストが空なら -1 を、そうでなければチェックポイント番号を出力

具体例

\(N=3, V=2, D=[10, 20], T=[6, 20]\) の場合：

チェックポイント	高橋君の到着時刻	青木君の到着時刻	追い越し判定
2	\(10/2=5\) 秒	\(6\) 秒	\(5 < 6\) → 追い越す
3	\(30/2=15\) 秒	\(20\) 秒	\(15 < 20\) → 追い越す

出力：2 3

計算量

• 時間計算量: \(O(N)\)
  • 各チェックポイントについて1回ずつ判定するため
• 空間計算量: \(O(N)\)
  • 入力の格納と結果リストの保持に必要

実装のポイント

1. 浮動小数点数を避ける: total_distance / V < T[i] ではなく total_distance < T[i] * V で比較することで、誤差なく正確に判定できます。

2. インデックスの対応関係:

   • D[i] はチェックポイント \(i+1\) から \(i+2\) への距離（0-indexed）
   • T[i] は青木君のチェックポイント \(i+2\) への到着時刻（0-indexed）
   • 出力するチェックポイント番号は1-indexedなので i + 2

3. 累積和の更新: 距離を毎回最初から足し直すのではなく、前の値に加算していくことで効率的に計算できます。

   ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, V = map(int, input().split())
    D = list(map(int, input().split()))
    T = list(map(int, input().split()))
    
    # 高橋君がチェックポイントiに到着する時刻を計算
    # チェックポイント1からスタート（時刻0）
    # チェックポイントi+1に到着する時刻 = (D_1 + D_2 + ... + D_i) / V
    
    # 青木君のチェックポイントiへの到着時刻はT[i-2]（i >= 2）
    # T_2, T_3, ..., T_N が T[0], T[1], ..., T[N-2] に対応
    
    result = []
    total_distance = 0
    
    for i in range(N - 1):
        # i番目からi+1番目のチェックポイントへ
        total_distance += D[i]
        # チェックポイント i+2 番（0-indexedでi+1）に到着
        # 実際のチェックポイント番号は i+2
        checkpoint = i + 2
        
        # 高橋君の到着時刻: total_distance / V
        # 青木君の到着時刻: T[i] (T_2, T_3, ... の順で格納)
        
        # 高橋君が先に到着 <=> total_distance / V < T[i]
        # <=> total_distance < T[i] * V
        
        takahashi_time_numerator = total_distance  # 分子
        takahashi_time_denominator = V  # 分母
        aoki_time = T[i]
        
        # total_distance / V < T[i]
        # <=> total_distance < T[i] * V
        if total_distance < aoki_time * V:
            result.append(checkpoint)
    
    if result:
        print(' '.join(map(str, result)))
    else:
        print(-1)

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。