概要

\(N\) 回のテストのうち、点数が \(0\) 以下の「赤点」の数を最小化する問題です。最大 \(K\) 回の補習授業を、赤点回避に必要な回数が少ないテストから優先的に割り当てることで解決できます。

考察

まず、すでに点数が \(1\) 点以上あるテストについては、赤点ではないため補習授業を行う必要はありません。 点数が \(0\) 以下のテストを赤点から救う（\(1\) 点以上にする）ために必要な補習回数を考えてみましょう。

点数が \(H_i\) (\(H_i \le 0\)) のテストに対して \(c\) 回の補習を行うと、点数は \(H_i + c \times P\) になります。これが \(1\) 以上になればよいので、 $\(H_i + c \times P \ge 1\)\( \)\(c \times P \ge 1 - H_i\)\( これを満たす最小の整数 \)c$ が、そのテストの赤点を回避するために必要な補習回数です。

高橋君が受けられる補習授業の合計回数 \(K\) には上限があります。赤点の数をできるだけ少なくするには、「少ない補習回数で赤点を回避できるテスト」から優先して補習を割り当てるのが最適です。これは貪欲法（Greedy Algorithm）と呼ばれる考え方です。

もし、どのテストに何回補習するかを全探索しようとすると、組み合わせが膨大になり実行時間制限（TLE）に引っかかってしまいますが、この貪欲法を用いれば高速に答えを求めることができます。

アルゴリズム

1. 各テストの点数 \(H_i\) を確認し、\(H_i \le 0\) である（現在赤点である）テストについてのみ、赤点回避に必要な補習回数を計算してリストに追加します。
2. 計算した「必要な補習回数」のリストを昇順（小さい順）にソートします。
3. 初期状態の赤点の数をリストの長さ（現在赤点であるテストの総数）とします。
4. ソートしたリストを前から順に見ていき、手持ちの補習回数 \(K\) から必要な回数を引いていきます。
   • \(K\) が必要な回数以上あれば、\(K\) を減らし、赤点の数を \(1\) 減らします。
   • \(K\) が足りなくなったら、それ以上赤点を減らすことはできないのでループを抜けます。
5. 最終的な赤点の数を出力します。

計算量

• 時間計算量: \(O(N \log N)\) 各テストの確認に \(O(N)\)、必要な補習回数リストのソートに \(O(N \log N)\)、リストの走査に \(O(N)\) かかるため、全体の時間計算量は \(O(N \log N)\) となります。制約の \(N \le 2 \times 10^5\) に対して十分に高速です。
• 空間計算量: \(O(N)\) 必要な補習回数を格納するリストが最大で要素数 \(N\) となるため、\(O(N)\) のメモリを使用します。

実装のポイント

• 必要な補習回数の計算: Pythonの切り捨て除算 // を使うと便利です。h <= 0 のとき、(P - h) // P とすることで、浮動小数点数の精度誤差（小数の計算ズレ）を気にすることなく、正確に「\(1\) 点以上にするための最小回数」を整数で求めることができます。

  • 例: \(P=5, H_i=-4\) の場合、\((5 - (-4)) // 5 = 9 // 5 = 1\) 回。
  • 例: \(P=5, H_i=-5\) の場合、\((5 - (-5)) // 5 = 10 // 5 = 2\) 回。

• 高速な入力: sys.stdin.read().split() を使用することで、大量の入力データに対しても高速に読み込み処理を行うことができます。競技プログラミングにおいて \(N\) が大きい場合に有効なテクニックです。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    P = int(input_data[2])
    
    req_k = []
    for i in range(3, 3 + N):
        h = int(input_data[i])
        if h <= 0:
            req_k.append((P - h) // P)
            
    req_k.sort()
    
    ans = len(req_k)
    for req in req_k:
        if K >= req:
            K -= req
            ans -= 1
        else:
            break
            
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。