概要

この問題は、地球から遠ざかる敵の宇宙船に対して、発射したミサイルが追いつくことができるかを判定する問題です。 一見すると物理の追いつき算（旅人算）のように見えますが、数式を整理すると「ミサイルの速度が宇宙船の速度より大きいか」という非常にシンプルな条件に帰着されます。

考察

時刻 \(t \geq 0\) における敵の宇宙船の座標と、ミサイル \(i\) の座標を数式で表してみましょう。

• 敵の宇宙船の座標: \(D + V \cdot t\)
• ミサイル \(i\) の座標: \(S_i \cdot t\)

ミサイルが宇宙船に到達できるとは、ある時刻 \(t \geq 0\) において「ミサイルの座標 \(\geq\) 宇宙船の座標」となることです。 すなわち、以下の不等式を満たす \(t \geq 0\) が存在するかどうかを判定します。

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

この式を移行して整理すると、次のようになります。

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

ここで、問題の制約から初期位置は \(D \geq 1\)（常に正）です。この条件のもとで、上式を満たす \(t \geq 0\) が存在するかどうかを \(S_i\) と \(V\) の関係から分類します。

1. \(S_i \leq V\) のとき \(S_i - V \leq 0\) となります。\(t \geq 0\) であるため、左辺 \(t(S_i - V)\) は常に \(0\) 以下になります。 右辺は \(D \geq 1\) なので、不等式 \(t(S_i - V) \geq D\) を満たす \(t\) は絶対に存在しません。 （直感的にも、自分より速い、または同じ速度で逃げる相手に追いつくことはできません）

2. \(S_i > V\) のとき \(S_i - V > 0\) となります。このとき、十分に大きな時刻 \(t\)（具体的には \(t \geq \frac{D}{S_i - V}\)）を取れば、必ず不等式を満たすことができます。 （自分より遅い速度で逃げる相手には、初期位置がどれだけ離れていても、いつかは必ず追いつくことができます）

以上の考察から、ミサイルが宇宙船に到達できるための必要十分条件は \(S_i > V\) であることが分かります。初期位置 \(D\) の値は、追いつくかどうかの判定には一切影響しません。

アルゴリズム

1. 入力から \(N, D, V\) を受け取ります。
2. 各ミサイルの速度 \(S_i\) を順に受け取り、 \(S_i > V\) を満たしているかを判定します。
3. 条件を満たすミサイルの個数をカウントし、最終的なカウントを出力します。

各ミサイルの判定は独立して行えるため、配列などにすべての速度を保存しておく必要はなく、入力を受け取りながらその場で判定・カウントしていくことが可能です。

計算量

• 時間計算量: \(O(N)\) \(N\) 個のミサイルについて、それぞれ定数時間 \(O(1)\) で判定を行います。 \(N \leq 10^6\) であるため、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(1)\) 入力をその都度処理するため、要素数 \(N\) の配列を確保する必要がなく、極めて省メモリで動作します。

実装のポイント

• 高速入出力: \(N\) が最大で \(10^6\) と非常に大きいため、C++では std::cin や std::cout のボトルネックを解消するために、ios_base::sync_with_stdio(false); cin.tie(NULL); を main 関数の冒頭に記述して入出力を高速化しています。

• 変数の型: \(D\) や \(V\) の値は最大で \(10^9\) であり、一般的な32ビット整数型（int）の最大値（約 \(2 \times 10^9\)）に収まりますが、オーバーフローを防ぐために long long 型を使用すると安全です。

  ソースコード

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D, V;
    if (!(cin >> N >> D >> V)) return 0;

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

    cout << count << "\n";

    return 0;
}

この解説は gemini-3.5-flash-thinking によって生成されました。