概要

各スマートフォンのバッテリーが「\(K\) 日間で合計いくつ減るか」を一括で計算し、\(K\) 日後に残量が \(1\%\) 以上残る台数を数える問題です。

考察

重要な観察は「充電器が届くまでの \(K\) 日間、毎日一定量 \(D\%\) ずつ減る」という点です。
よって、\(K\) 日後のバッテリー残量は各端末ごとに

• 減少量：\(D \times K\)
• 残量：\(W_i - D \times K\)

と一発で求まります。

素朴に「1日ずつ \(K\) 回シミュレーションして減らす」方法だと、計算量が \(O(NK)\) になってしまいます。制約では \(K \le 10^9\) なので、これは現実的な時間では終わりません（TLE になります）。

そこで、\(K\) 日分の減少はまとめて \(D \times K\) として計算し、各 \(W_i\) について条件判定するだけにします。

また、問題文より「\(K\) 日後の時点で \(1\%\) 以上」なら使えるので、判定条件は - \(W_i - D \times K \ge 1\) です（\(0\) は不可）。

例：\(D=3, K=4, W_i=15\) なら減少量は \(12\)、残量は \(3\) なので生存。

アルゴリズム

1. 入力で \(N, D, K\) と配列 \(W\) を受け取る。
2. \(dec = D \times K\)（\(K\) 日間の合計減少量）を計算する。
3. 各 \(w \in W\) について、\(w - dec \ge 1\) を満たすものを数える。
4. その個数を出力する。

計算量

• 時間計算量: \(O(N)\)（各スマホを1回ずつ判定するだけ）
• 空間計算量: \(O(N)\)（入力配列を保持するため）

実装のポイント

• \(K\) が非常に大きいので、日数分ループするシミュレーションはしない（\(D \times K\) を一括計算）。

• 判定は「\(1\) 以上」なので、条件は \(w - dec \ge 1\)（\(>0\) と同値）。

• Python では整数は任意精度なので \(D \times K\) が大きくてもオーバーフローの心配はありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, D, K = map(int, input().split())
    W = list(map(int, input().split()))
    dec = D * K
    ans = sum(1 for w in W if w - dec >= 1)
    print(ans)

if __name__ == "__main__":
    main()

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