概要

敵の宇宙船は座標 \(D\) から速度 \(V\) で遠ざかり、ミサイルは座標 \(0\) から速度 \(S_i\) で追いかけます。
各ミサイルについて、宇宙船に追いつけるかどうかを判定し、その個数を数える問題です。

考察

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

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

ミサイルが到達できる条件は、ある \(t \geq 0\) について

\(S_i t \geq D + Vt\)

となることです。これを変形すると、

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

です。

ここで、制約より \(D \geq 1\) なので、右辺は正です。

\(S_i \leq V\) の場合

\((S_i - V) \leq 0\) なので、左辺は \(t \geq 0\) に対して正になりません。
つまり、宇宙船との距離は縮まらないため、到達できません。

\(S_i > V\) の場合

\((S_i - V) > 0\) なので、

\(t \geq \frac{D}{S_i - V}\)

となる十分大きな時刻を取れば、必ず宇宙船に到達できます。

したがって、ミサイルが到達できるかどうかは、単に

\(S_i > V\)

で判定できます。

例えば、\(D=10, V=3\) のとき、

• \(S_i=5\) なら、ミサイルの方が速いのでいつか追いつける
• \(S_i=3\) なら、同じ速度なので距離 \(10\) が縮まらず追いつけない
• \(S_i=2\) なら、さらに離されるので追いつけない

となります。

時刻をシミュレーションする必要はありません。連続時間を細かく調べる方法では、時間がかかるだけでなく、誤差や終了条件の扱いで間違いやすくなります。

アルゴリズム

各ミサイルの速度 \(S_i\) を順に読み込みます。

1. 答えを表す変数 ans を \(0\) にする
2. 各ミサイルについて、速度 \(S_i\) を読む
3. \(S_i > V\) なら、そのミサイルは到達可能なので ans を \(1\) 増やす
4. 最後に ans を出力する

判定に必要なのは速度の大小関係だけなので、距離 \(D\) は入力として受け取りますが、判定には使いません。

計算量

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

実装のポイント

\(N\) は最大で \(10^6\) と大きいので、すべての速度を配列に保存する必要はありません。
入力を読みながらその場で判定すれば、追加のメモリはほとんど使いません。

また、\(D, V, S_i\) は最大で \(10^9\) なので int でも収まりますが、計算式を扱う可能性を考えると long long を使っておくと安全です。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long D, V;
    cin >> N >> D >> V;

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        long long S;
        cin >> S;
        if (S > V) ++ans;
    }

    cout << ans << '\n';
    return 0;
}

---

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