概要

地球から逃げる宇宙船に追いつけるミサイルの数を数える問題。ミサイルの速度が宇宙船の速度より大きいかどうかを判定すればよい。

考察

時刻 \(t\) における各物体の位置を考えます。

• 敵の宇宙船の位置: \(D + Vt\)
• \(i\) 番目のミサイルの位置: \(S_i \cdot t\)

ミサイルが宇宙船に到達する条件は、ある \(t \geq 0\) が存在して：

\[S_i \cdot t \geq D + V \cdot t\]

これを整理すると：

\[(S_i - V) \cdot t \geq D\]

ここで場合分けを行います：

• \(S_i > V\) の場合: \(t = \frac{D}{S_i - V}\) のとき等号が成立し、ミサイルは宇宙船に追いつけます。
• \(S_i = V\) の場合: 左辺は常に \(0\) で、\(D > 0\) なので不等式を満たす \(t\) は存在しません。ミサイルと宇宙船の速度が同じでは、初期距離 \(D\) を縮められません。
• \(S_i < V\) の場合: \(S_i - V < 0\) なので、\(t\) を大きくするほど左辺は負に発散し、絶対に追いつけません。

結論: ミサイルが宇宙船に到達できる条件は、単純に \(S_i > V\) です。

具体例で確認します。\(D = 10, V = 3\) のとき： - \(S_i = 5\) なら、\(t = \frac{10}{5-3} = 5\) で追いつける ✓ - \(S_i = 3\) なら、速度が同じなので距離 \(10\) は永遠に縮まらない ✗ - \(S_i = 2\) なら、距離はどんどん開く ✗

アルゴリズム

1. \(N, D, V\) を読み込む
2. 各ミサイルの速度 \(S_i\) について \(S_i > V\) かどうかを判定する
3. 条件を満たすミサイルの個数を数えて出力する

\(D\) の値は条件判定に直接使用しないことに注意してください（\(D \geq 1\) が保証されているため、\(S_i > V\) であれば必ず有限時刻で追いつけます）。

計算量

• 時間計算量: \(O(N)\)（各ミサイルについて1回の比較）
• 空間計算量: \(O(N)\)（入力データの保持）

実装のポイント

• \(N\) が最大 \(10^6\) と大きいため、sys.stdin.buffer.read() を使って高速に入力を読み込んでいます。

• 浮動小数点数を使った計算は不要で、整数の大小比較のみで判定できます。

• \(D\) は問題設定上必要ですが、\(D \geq 1\) が保証されているため、判定条件は \(S_i > V\)（等号を含まない）となる点に注意してください。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    D = int(data[1])
    V = int(data[2])
    count = sum(1 for i in range(3, 3 + N) if int(data[i]) > V)
    print(count)

main()

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