概要

\(N\) 台のスマートフォンがあり、1日ごとにバッテリーが \(D\) パーセント減少します。\(K\) 日後にバッテリー残量が \(1\) パーセント以上残っているスマートフォンの台数を求める問題です。

考察

この問題で最も重要なのは、「\(K\) 日後のバッテリー残量を効率よく計算すること」です。

1日ずつバッテリーを減らしていくシミュレーションを行うと、日数が \(K = 10^9\) と非常に大きいため、計算が終わらずに制限時間切れ（TLE）になってしまいます。 しかし、1日 \(D\) パーセントずつ減るということは、\(K\) 日間では合計で \(D \times K\) パーセント減ると言い換えることができます。

したがって、各スマートフォン \(i\) について、以下の条件を満たすかどうかを判定すればよいことになります。 $\((W_i - D \times K) \geq 1\)$

この式を変形すると、以下のようになります。 $\(W_i \geq (D \times K) + 1\)$

ここで、問題文の制約に注目すると、初期のバッテリー残量 \(W_i\) は最大でも \(100\) パーセントです。 もし \(D \times K\) が \(100\) 以上であれば、どのスマートフォンも必ず \(0\) パーセント以下になってしまうため、答えは \(0\) 台と即座に判断できます。

アルゴリズム

1. \(K\) 日間に減少するバッテリーの総量 \(loss = D \times K\) を計算します。
2. \(loss \geq 100\) の場合、すべてのスマートフォンのバッテリーが尽きるため、0 を出力して終了します。
3. \(loss < 100\) の場合、各スマートフォン \(W_i\) について以下の判定を行います。
   • \(W_i \geq loss + 1\) であれば、カウントを \(1\) 増やす。
4. 最終的なカウントを出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 台のスマートフォンに対して一度ずつ判定を行うため、入力の大きさに比例した時間で処理が完了します。\(K\) の大きさには依存しません。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個のバッテリー残量をリストに保持するために必要なメモリ量です。

実装のポイント

• 高速な入出力: スマートフォンの台数 \(N\) が最大 \(10^5\) と大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() を使って一括で読み込む方が実行時間を短縮できます。

• オーバーフローの心配: Pythonは非常に大きな整数も扱えるため、\(D \times K\) が大きな値になっても特別な対策なしで計算可能です。

  ソースコード

import sys

def solve():
    # 入力を一度にすべて読み込み、空白で分割してリストにする
    # これにより、大量のデータに対しても高速に処理が可能
    data = sys.stdin.read().split()
    if len(data) < 3:
        return
    
    # スマートフォンの台数 N, 1日あたりの減少量 D, 到着までの日数 K を取得
    n = int(data[0])
    d = int(data[1])
    k = int(data[2])
    
    # K日間に減少するバッテリーの総量
    loss = d * k
    
    # スマートフォンの初期バッテリー残量 W_i は最大で 100 パーセントである。
    # 減少量 loss が 100 以上のとき、どのスマートフォンも K 日後には 0 パーセント以下となる。
    # バッテリー残量が 1 パーセント以上残る必要があるため、この場合は生存数は 0 となる。
    if loss >= 100:
        print(0)
        return
    
    # 生存条件: W_i - loss >= 1  =>  W_i >= loss + 1
    # 判定の基準となる閾値を計算する
    threshold = loss + 1
    
    count = 0
    # 各スマートフォンの現在のバッテリー残量 W_i について判定を行う
    # W_i はリストの 4 番目（インデックス 3）から N 個分並んでいる
    for i in range(3, 3 + n):
        if int(data[i]) >= threshold:
            count += 1
            
    # 結果を出力
    print(count)

if __name__ == '__main__':
    solve()

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