概要

\(N\) 個の科目の点数をすべて \(T\) 点以上にするために必要な「追加課題」の最小個数を求め、それが上限 \(M\) 個以内であるかを判定する問題です。

考察

この問題のポイントは、「各科目を独立に考えて、不足分を合計すればよい」という点にあります。

高橋君が補習を回避するためには、すべての科目 \(i\) において \(A_i \geq T\) を満たす必要があります。 - すでに \(A_i \geq T\) である科目の場合：追加課題を使う必要はありません。 - \(A_i < T\) である科目の場合：その科目を \(T\) 点にするためには、最低でも \(T - A_i\) 個の追加課題が必要です。

すべての科目を目標点にするために必要な追加課題の総数は、各科目の不足分の合計となります。この合計値が、提出可能な最大数 \(M\) を超えなければ目標達成が可能であり、その合計値が最小の課題数となります。逆に合計値が \(M\) を超えてしまう場合は、どのように課題を割り振っても全科目 \(T\) 点以上にはできないため、-1 を出力します。

アルゴリズム

以下の手順で解くことができます。

1. 必要な追加課題の総数を表す変数 total_needed を \(0\) で初期化する。
2. 各科目の点数 \(A_i\) (\(i=1, \ldots, N\)) について順番に以下を行う：
   • もし \(A_i < T\) ならば、不足分である \(T - A_i\) を total_needed に加算する。
   • \(A_i \geq T\) ならば、何もしない（加算する値は \(0\)）。
3. 最終的な total_needed と \(M\) を比較する：
   • total_needed <= M であれば、total_needed を出力する。
   • total_needed > M であれば、-1 を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 科目数 \(N\) に対して、各科目の点数を \(1\) 回ずつ確認するため、計算量は \(N\) に比例します。\(N \leq 10^5\) であるため、十分に高速に動作します。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の点数をリストに格納して保持するため、その分のメモリが必要です。

実装のポイント

• 大きな値の扱い: \(M\) は最大 \(10^9\)、また必要な課題の総数も \(N \times T = 10^5 \times 100 = 10^7\) 程度になる可能性がありますが、Python の整数型は自動的に多倍長整数として扱われるため、オーバーフローの心配はありません。

• 入力の読み込み: \(N\) が大きいため、sys.stdin.read().split() などを用いて一括で入力を取得すると効率的です。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N, M, T を取得
    n = int(input_data[0])
    m = int(input_data[1])
    t = int(input_data[2])
    
    # 各科目の点数 A_i を取得
    a = list(map(int, input_data[3:]))
    
    # 全科目を目標点 T 以上にするために必要な追加課題の総数を計算
    total_needed = 0
    for score in a:
        if score < t:
            total_needed += (t - score)
            
    # 必要個数が M 以下であればその個数を出力、そうでなければ -1 を出力
    if total_needed <= m:
        print(total_needed)
    else:
        print("-1")

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。