概要

高橋君は最大 \(K\) 回の補習授業を受けて、テストの赤点（点数が \(0\) 以下）を最小化したいです。各補習では任意のテストの点数を \(P\) だけ上げることができます。

考察

問題の本質

各テストの初期点数 \(H_i\) が与えられ、補習授業を受けることで点数を増やすことができます。最終的に点数が正（\(> 0\)）になるテストの数を最大化することが目的です。

赤点を避けるために必要な補習回数

あるテストの点数が \(h\) のとき、それが赤点（\(h \leq 0\)）なら、点数を \(1\) 以上にするために必要な最小補習回数は次のように求められます： $\( k = \left\lceil \frac{1 - h}{P} \right\rceil \)\( これは、\)h + k \cdot P \geq 1\( となる最小の非負整数 \)k$ です。

例えば、\(h = -3\), \(P = 2\) の場合： - 必要な点数は \(1 - (-3) = 4\) - 必要な補習回数は \(\lceil 4 / 2 \rceil = 2\)

一方、すでに正の点数（\(h > 0\)）のテストは補習不要です。

貪欲法による最適解

補習回数が限られているので、赤点のテストのうち、補習が最も少ない回数で救えるテストから優先的に救うのが最適です。これにより、できるだけ多くのテストを赤点から救えます。

具体的には、赤点テストの必要補習回数をリストアップし、昇順にソートして、合計が \(K\) を超えない範囲で貪欲に選んでいきます。

アルゴリズム

1. 各テストの点数 \(H_i\) を確認し、\(H_i \leq 0\) であれば赤点となり得る。
2. 各赤点テストに対して、点数を正にするために必要な補習回数 \(k = \left\lceil \frac{1 - H_i}{P} \right\rceil\) を計算。
3. これらの補習回数をリストにして昇順にソート。
4. 小さい方から貪欲に選び、使用した補習回数の合計が \(K\) を超えないようにカウントする。
5. 救えた赤点テスト数をカウントし、残りの赤点テスト数が答え。

計算量

• 時間計算量: \(O(N \log N)\) （ソートが必要なため）
• 空間計算量: \(O(N)\) （必要な補習回数を保存する配列）

実装のポイント

• 点数が正のテストは無条件で赤点にならないので、補習不要。

• 必要補習回数の計算には、天井関数相当の処理を行う：ceil((1 - h) / P) は (1 - h + P - 1) // P で実現可能。

• 合計補習回数が \(K\) を超えた時点で打ち切ることで効率よく計算できる。

  ソースコード

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    P = int(data[2])
    H = list(map(int, data[3:3+N]))
    
    # 赤点回避に必要な補習回数（0以下のものをヒープに）
    required = []
    for h in H:
        if h <= 0:
            # 赤点回避には ceil((1 - h) / P) 回必要
            # つまり (P - h - 1 + P - 1) // P = (P - h - 1)//P + 1 = (P - h + P - 1)//P = (2*P - h - 1)//P
            # 単純に (P - h) // P + (1 if (P - h) % P != 0 else 0) も可能
            # もっと簡単には (-h + P - 1) // P だが、hが負の場合に注意
            # 実際には、h + k*P > 0 なる最小の非負整数kを求めたい
            # h + k*P >= 1 → k*P >= 1 - h → k >= (1 - h)/P
            # 最小の整数kは ceil((1 - h)/P)
            # Pythonのceil(x/y)は (x + y - 1) // y (x,y>0)
            # ただし h が負の場合も考慮して、1 - h > 0 なので問題なし
            k = max(0, (1 - h + P - 1) // P)
            required.append(k)
    
    # 赤点でないものは補習不要
    # 赤点のものについて、必要な補習回数が少ない順にソートして貪欲に処理
    required.sort()
    
    total_used = 0
    count = 0
    for r in required:
        if total_used + r <= K:
            total_used += r
            count += 1
        else:
            break
    
    # 赤点でないものは N - len(required) 個
    not_red = N - len(required)
    # 赤点のうち救えたのは count 個
    red_solved = count
    # 残りの赤点は len(required) - count 個
    red_unsolved = len(required) - count
    
    print(red_unsolved)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。