概要

各テストの点数を補習授業で上げることで、赤点（0点以下）のテスト数を最小化する問題です。補習授業は最大K回まで行え、1回あたりP点を任意のテストに加算できます。

考察

素朴に考えると、補習授業を赤点になりそうなテストに割り当てることになります。しかし、各テストを赤点から救うために必要な補習回数は異なります。例えば、現在の点数が\(-5\)で\(P=2\)の場合、最低3回の補習が必要です（\(-5 + 2*3 = 1\)点）。重要な観察は、必要な補習回数が少ないテストから優先的に救うのが最適であることです。これにより、限られた補習回数Kで最大数のテストを救うことができます。

アルゴリズム

1. 各テスト\(i\)について、赤点（0点以下）から救う（1点以上にする）ために必要な補習回数\(r_i\)を計算します：
   • 現在の点数\(H_i \geq 1\)なら\(r_i = 0\)（既に救われている）
   • そうでなければ、\(r_i = \lceil (1 - H_i) / P \rceil\)（切り上げ計算）
2. 必要な補習回数のリストを昇順にソートします
3. ソートされたリストの累積和を計算します
4. 累積和がK以下となる最大のインデックス\(m\)を二分探索で求めます
   • これは、\(m\)個のテストを救えることを意味します
5. 答えは\(n - m\)（救えなかったテスト数＝赤点数）となります

計算量

• 時間計算量: \(O(N \log N)\)（ソートと二分探索による）
• 空間計算量: \(O(N)\)（必要な補習回数のリストと累積和の配列）

実装のポイント

• 必要な補習回数の計算では、切り上げ処理を正しく行う必要があります。コードでは(1 - h + P - 1) // Pという式で、整数除算を利用した切り上げ計算を実現しています

• 累積和の配列は先頭に0を追加することで、インデックス処理を簡単にしています

• 二分探索では、累積和がK以下となる最大の要素数を探すため、upper boundではなくlower bound的な探索を行っています

  ソースコード

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]))
    
    # 各テストを赤点にしないために必要な補習回数を計算
    required = []
    for h in H:
        # 最終スコアを1以上にするためには、h + x * P >= 1 となる最小のxを見つける
        # x >= ceil((1 - h) / P)
        if h >= 1:
            required.append(0)
        else:
            need = (1 - h + P - 1) // P
            required.append(need)
    
    # 必要な補習回数でソート
    required.sort()
    
    # 累積和を計算
    prefix = [0]
    for i in range(n):
        prefix.append(prefix[-1] + required[i])
    
    # 累積和がK以下となる最大のインデックスを二分探索
    left, right = 0, n
    while left < right:
        mid = (left + right + 1) // 2
        if prefix[mid] <= K:
            left = mid
        else:
            right = mid - 1
    
    # 救えるテストの最大数はleft
    # 赤点の最小数はn - left
    print(n - left)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。