概要

スマートフォンのバッテリー残量と減り方、充電器の到着日数から、充電器が届いた時点でまだ使えるスマートフォンの台数を求めます。

考察

各スマートフォンについて、充電器が届く \(K\) 日後までにバッテリーが \(0\) にならず、かつその時点でバッテリーが \(1\) 以上残っていれば「使える」とみなされます。

単純に考えると、1日ずつシミュレーションしていけばよいように思えますが、\(K\) が最大 \(10^9\) と非常に大きいため、日数ごとに処理すると時間内に終わらなくなります（TLE）。

しかし、実は各スマートフォンのバッテリー残量は一定の速度で減るだけなので、最終的な残量を直接計算できます。
具体的には、初期バッテリー残量 \(W_i\) から、1日に \(D\) ずつ \(K\) 日分引いた値が最終残量になります： $\( \text{最終残量} = W_i - D \times K \)\( この値が \)1$ 以上であれば、そのスマートフォンは使える状態で残ります。

よって、各スマートフォンに対してこの条件をチェックするだけで答えが求められます。

例

例えば、\(W_i = 10\), \(D = 3\), \(K = 3\) のとき： $\( 10 - 3 \times 3 = 10 - 9 = 1 \)\( これは \)1$ なので、このスマートフォンはギリギリ使える状態で残ります。

一方、\(W_i = 9\) のとき： $\( 9 - 3 \times 3 = 0 \)\( これは \)0$ なので使えない（電源が切れる）。

アルゴリズム

1. 各スマートフォンの初期バッテリー残量 \(W_i\) を読み込む。
2. 各 \(W_i\) に対して、最終残量 \(W_i - D \times K\) を計算。
3. 最終残量が \(1\) 以上であればカウントアップ。
4. カウント結果を出力。

計算量

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

※ \(N\) はスマートフォンの台数。各スマートフォンについて一度だけ確認すればよいので、線形時間で処理可能。

実装のポイント

• 各スマートフォンのバッテリー残量は独立に判定できるため、ループ内で一つずつ確認するだけでOK。

• 条件は「最終残量が1以上」であることに注意（0は不可）。

• 大きな数値（\(K\) が最大 \(10^9\)）を扱うため、オーバーフローには注意が必要ですが、Pythonでは特に気にせず計算可能です。

  ソースコード

N, D, K = map(int, input().split())
W = list(map(int, input().split()))

count = 0
for w in W:
    if w - D * K >= 1:
        count += 1

print(count)

この解説は qwen3-coder-480b によって生成されました。