概要

\(N\) 回の小テストのうち、点数が \(0\) 以下（赤点）のテストに対して、最大 \(K\) 回の補習授業（1回で \(P\) 点加算）を最適に割り振り、赤点のテスト数を最小化する問題です。

考察

重要な気づき

1. すでに合格しているテスト（\(H_i > 0\)）には何もしなくてよい。 補習を使う必要があるのは \(H_i \leq 0\) のテストだけです。

2. 各赤点テストを合格にするのに必要な補習回数は決まっている。 テスト \(i\) の点数が \(H_i \leq 0\) のとき、最終的に \(H_i + k \cdot P > 0\) にする必要があります。これを満たす最小の \(k\) は：

\[k = \left\lceil \frac{1 - H_i}{P} \right\rceil\]

例えば、\(H_i = -5\), \(P = 3\) の場合、\(1 - (-5) = 6\) なので \(\lceil 6/3 \rceil = 2\) 回の補習が必要です。実際 \(-5 + 2 \times 3 = 1 > 0\) で合格になります。

1. コストの小さいテストから優先的に救うべき。 補習回数 \(K\) は有限なので、少ない回数で合格にできるテストから順番に救うのが最適です（貪欲法）。

なぜ貪欲法が最適か

赤点を1つ減らすためのコスト（必要な補習回数）はテストごとに独立です。限られた予算 \(K\) でできるだけ多くのテストを救いたいので、コストの安い順に救うのが最適解になります。これは典型的な「ナップサック問題の特殊ケース（各アイテムの価値が等しい場合）」であり、貪欲法で最適解が得られます。

アルゴリズム

1. 各テストについて、\(H_i > 0\) ならすでに合格なのでスキップ。
2. \(H_i \leq 0\) のテストについて、合格にするのに必要な補習回数 \(\lceil (1 - H_i) / P \rceil\) を計算し、リストに格納。
3. このリストを昇順にソートする。
4. コストの小さい方から順に、残りの補習回数 \(K\) から引いていく。\(K\) が足りなくなったら打ち切る。
5. 救えなかったテストの数が答え。

具体例

\(N=4, K=3, P=2, H = [-3, -1, 5, 0]\) の場合：

テスト	\(H_i\)	赤点？	必要回数
1	\(-3\)	Yes	\(\lceil 4/2 \rceil = 2\)
2	\(-1\)	Yes	\(\lceil 2/2 \rceil = 1\)
3	\(5\)	No	—
4	\(0\)	Yes	\(\lceil 1/2 \rceil = 1\)

コスト昇順: \([1, 1, 2]\)。\(K=3\) から順に引くと \(3 \to 2 \to 1 \to -1\)（足りない）。2つ救えるので、赤点数は \(3 - 2 = 1\)。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（コストのリストを保持）

実装のポイント

• \(0\) 点ちょうども赤点 であることに注意。合格条件は「\(> 0\)」であり「\(\geq 0\)」ではありません。

• 必要回数の計算で 切り上げ除算 を正しく行う必要があります。Python の math.ceil を使うか、整数演算で (1 - h + P - 1) // P とする方法があります。

• \(K\) や \(H_i\) の値が最大 \(10^9\) と大きいですが、Python では整数オーバーフローの心配はありません。

  ソースコード

import math

def solve():
    N, K, P = map(int, input().split())
    H = list(map(int, input().split()))
    
    # A test is "赤点" (failing) if its final score <= 0
    # We want to minimize the number of failing tests.
    # 
    # For each test i, if H_i > 0, it's already passing (no help needed).
    # If H_i <= 0, we need to add enough P's to make it > 0.
    # The number of补習 needed for test i (if H_i <= 0) is ceil((1 - H_i) / P)
    # = ceil((1 - H_i) / P)
    # Since H_i <= 0, 1 - H_i >= 1, so we need at least 1 session.
    
    # Strategy: greedily fix the cheapest failing tests first.
    
    # Already passing tests (H_i > 0): no cost
    already_passing = sum(1 for h in H if h > 0)
    
    # Failing tests (H_i <= 0): compute cost to fix each
    failing = []
    for h in H:
        if h <= 0:
            # Need final score > 0, i.e., h + k*P > 0 => k > -h/P => k = ceil((-h+1)/P) = ceil((1-h)/P)
            needed = math.ceil((1 - h) / P)
            failing.append(needed)
    
    # Sort by cost (ascending) to fix cheapest first
    failing.sort()
    
    remaining = K
    fixed = 0
    for cost in failing:
        if remaining >= cost:
            remaining -= cost
            fixed += 1
        else:
            break
    
    print(len(failing) - fixed)

solve()

---

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