概要

\(N\) 台のスマートフォンが \(K\) 日後に何台使える状態で残るかを求める問題です。各スマートフォンは毎日 \(D\) パーセントずつバッテリーが減少し、\(K\) 日後に残量が \(1\) 以上のものを数えます。

考察

重要な気づき

この問題で最も重要な観察は、各スマートフォンを独立に考えられるということです。

\(i\) 番目のスマートフォンについて： - 現在のバッテリー残量: \(W_i\) パーセント - \(1\) 日後の残量: \(W_i - D\) パーセント - \(2\) 日後の残量: \(W_i - 2D\) パーセント - … - \(K\) 日後の残量: \(W_i - K \times D\) パーセント

つまり、\(K\) 日後のバッテリー残量は単純な引き算で求められます。

具体例で確認

例えば、\(W_i = 50\)、\(D = 10\)、\(K = 3\) の場合： - \(K\) 日後の残量 = \(50 - 10 \times 3 = 20\) パーセント - \(20 \geq 1\) なので、このスマートフォンは使える状態で残ります。

一方、\(W_i = 30\)、\(D = 10\)、\(K = 5\) の場合： - \(K\) 日後の残量 = \(30 - 10 \times 5 = -20\) パーセント - \(-20 < 1\) なので、このスマートフォンは電源が切れてしまいます。

素朴なアプローチについて

この問題は単純な計算で解けるため、特に工夫は必要ありません。\(K\) が最大 \(10^9\) と大きいですが、シミュレーションで1日ずつ計算する必要はなく、\(K\) 日後の残量を直接計算できます。

もし1日ずつシミュレーションすると \(O(N \times K)\) となり、\(K\) が最大 \(10^9\) のためTLEになってしまいます。

アルゴリズム

1. 各スマートフォン \(i\) について、\(K\) 日後のバッテリー残量を計算する
   • 残量 = \(W_i - D \times K\)
2. 残量が \(1\) 以上であればカウントを増やす
3. 最終的なカウントを出力する

計算量

• 時間計算量: \(O(N)\)
  • 各スマートフォンについて定数時間の計算を行うため
• 空間計算量: \(O(N)\)
  • バッテリー残量のリストを保持するため

実装のポイント

• \(K\) が最大 \(10^9\) と大きいため、D * K の計算結果は非常に大きくなる可能性がありますが、Pythonでは整数のオーバーフローを気にする必要がありません。

• 条件は「\(1\) パーセント以上」なので、remaining >= 1 と等号を含めることに注意してください。

• バッテリー残量が負になるケースも正しく処理されます（負の値は当然 \(1\) より小さいため）。

  ソースコード

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

count = 0
for w in W:
    # K日後のバッテリー残量は W - D * K
    # これが1以上であれば使える
    remaining = w - D * K
    if remaining >= 1:
        count += 1

print(count)

---

この解説は claude4.5opus によって生成されました。