概要

赤点（最終得点が \(0\) 以下）になっているテストを、補習（1回につき任意のテストに \(+P\)）を最大 \(K\) 回まで使ってできるだけ救済し、赤点数の最小値を求める問題です。

考察

重要な観察は次の2点です。

1. 赤点かどうかは各テストごとに独立に決まる

   • あるテストの得点 \(H_i\) に補習を \(t\) 回割り当てると最終得点は \(H_i + tP\)。
   • 赤点を回避するには \(H_i + tP \ge 1\)（\(0\) 点も赤点なので「1以上」が必要）となる最小の \(t\) を求めればよい。
   • つまり「各赤点テストを救うのに必要な補習回数」が分かれば、あとは限られた回数 \(K\) の中で何個救えるかの問題になる。

2. 最小回数で救えるものから貪欲に救うのが最適

   • 目的は「救えるテスト数（赤点を減らす数）」を最大化すること。
   • 1つ救うと価値は常に「赤点が1つ減る」で同じなので、コスト（必要補習回数）が小さいものから順に救うのが最適です（典型的な「同価値アイテムの予算内最大個数」）。

素朴に「補習を1回ずつどこに入れるか」をシミュレーションすると、\(K\) が最大 \(10^9\) なので当然間に合いません。そこで、各テストを救うための必要回数を直接計算し、ソートして貪欲に選びます。

必要回数の導出

赤点のテスト（\(H_i \le 0\)）に対し、最小の \(t\) を求めます： - 条件：\(H_i + tP \ge 1\) - よって：\(t \ge \dfrac{1 - H_i}{P}\)

整数の最小値を取るので [ t = \left\lceil \frac{1 - H_i}{P} \right\rceil ] これをコードでは次と等価な形で計算しています（\(H_i \le 0\) のとき）： [ t = \left\lfloor \frac{-H_i}{P} \right\rfloor + 1 ] （例：\(H=-5, P=3\) なら \((-H)//P+1 = 5//3+1=2+1=3\) 回で \(-5+9=4\ge1\)）

アルゴリズム

1. 全テストを見て、まず赤点の個数 red（\(H_i \le 0\) の数）を数える。
2. 赤点の各テストについて、「赤点回避に必要な補習回数」
   \(c_i = (-H_i)//P + 1\) を配列 costs に入れる。
3. costs を昇順ソートする。
4. 小さいものから順に、合計使用回数が \(K\) を超えない限り救済していく（貪欲）。救えた数を fixed とする。
5. 答えは red - fixed（救えなかった赤点が最終的な赤点数）。

計算量

• 時間計算量: \(O(N \log N)\)（赤点テスト数を \(M\) とするとソートが \(O(M \log M)\)、最悪 \(M=N\)）
• 空間計算量: \(O(N)\)（必要回数を格納する配列）

実装のポイント

• \(0\) 点も赤点なので、目標は \(H_i + tP \ge 1\) です。ここを \(0\) 以上と勘違いすると1回少なく見積もってWAになります。

• \(K\) は最大 \(10^9\) と大きいですが、実際にループするのは costs の長さ（高々 \(N\)）だけなので安全です。

• Pythonの整数はオーバーフローしませんが、他言語では \(H_i\) や計算途中が \(10^9\) オーダーなので型に注意します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K, P = map(int, input().split())
    H = list(map(int, input().split()))
    
    costs = []
    red = 0
    for h in H:
        if h <= 0:
            red += 1
            costs.append((-h) // P + 1)
    
    costs.sort()
    used = 0
    fixed = 0
    for c in costs:
        if used + c <= K:
            used += c
            fixed += 1
        else:
            break
    
    print(red - fixed)

if __name__ == "__main__":
    main()

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