概要

各ミサイルについて、敵の宇宙船に追いつけるかどうかを判定します。結論として、ミサイルの速度 \(S_i\) が宇宙船の速度 \(V\) より大きい場合だけ到達できます。

考察

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

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

ミサイルが敵の宇宙船に到達する条件は、

\(S_i t \geq D + Vt\)

となる時刻 \(t \geq 0\) が存在することです。

式を変形すると、

\((S_i - V)t \geq D\)

です。

ここで \(D \geq 1\) なので、最初からミサイルと宇宙船は離れています。

• \(S_i > V\) の場合
  \((S_i - V)\) が正なので、十分大きい時刻 \(t\) を取れば必ず追いつけます。

• \(S_i = V\) の場合
  速度が同じなので、最初の距離 \(D\) は縮まりません。追いつけません。

• \(S_i < V\) の場合
  宇宙船の方が速いので、距離は広がっていきます。追いつけません。

したがって、答えは単に \(S_i > V\) であるミサイルの個数です。

例えば、\(V = 10\) のとき、ミサイル速度が \(8, 10, 12, 15\) なら、追いつけるのは \(12, 15\) の 2 機です。

素朴に各ミサイルについて時刻をシミュレーションすると、どこまで時間を進めればよいか分からず、TLE や誤差による WA の原因になります。今回は数式で条件を整理することで、各ミサイルを \(1\) 回見るだけで判定できます。

アルゴリズム

1. \(N, D, V\) を入力する。
2. ミサイル速度 \(S_i\) を順に見る。
3. \(S_i > V\) なら答えを \(1\) 増やす。
4. 最後に答えを出力する。

判定に \(D\) は直接使いません。これは、制約より \(D \geq 1\) であり、初期位置でミサイルがすでに到達していることがないためです。

計算量

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

実装のポイント

条件は \(S_i \geq V\) ではなく、必ず \(S_i > V\) です。速度が同じ場合、初期距離 \(D\) があるため追いつけません。

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

ソースコード

import sys

input = sys.stdin.buffer.readline

N, D, V = map(int, input().split())
ans = sum(1 for s in map(int, sys.stdin.buffer.read().split()) if s > V)

print(ans)

---

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