概要

各科目で目標点に足りない分を合計し、その合計が提出可能な追加課題の数 \(M\) 以下かどうかを判定する問題です。

考察

重要な気づき

この問題のポイントは、追加課題の効率的な使い方を考えることです。

追加課題1つで任意の1科目を1点上げられます。目標を達成するためには、目標点 \(T\) に達していない科目だけを \(T\) 点まで引き上げればよいです。

具体例で考える

例えば、\(N = 3\), \(M = 10\), \(T = 70\) で、点数が \([65, 80, 60]\) の場合を考えます。

• 科目1: \(65\) 点 → \(70\) 点にするには \(70 - 65 = 5\) 点必要
• 科目2: \(80\) 点 → すでに \(70\) 点以上なので追加不要（\(0\) 点）
• 科目3: \(60\) 点 → \(70\) 点にするには \(70 - 60 = 10\) 点必要

必要な追加課題の合計は \(5 + 0 + 10 = 15\) 個です。

\(M = 10\) なので、\(15 > 10\) となり、目標達成は不可能です。答えは -1 です。

なぜ単純な方法でよいのか

この問題では複雑なアルゴリズムは不要です。理由は以下の通りです：

1. 各科目で必要な追加点数は独立に計算できる
2. 追加課題の配分に優先順位を考える必要がない（すべての不足分を埋める必要があるため）
3. 単純に不足分の合計を求めれば、それが必要な最小個数となる

アルゴリズム

1. 各科目 \(i\) について、目標点 \(T\) との差を計算する
   • \(A_i < T\) の場合：\(T - A_i\) 点が不足
   • \(A_i \geq T\) の場合：不足なし（\(0\) 点）
2. 全科目の不足分を合計する（これを total_needed とする）
3. 判定する：
   • total_needed \(\leq M\) なら、total_needed を出力（必要な最小個数）
   • total_needed \(> M\) なら、-1 を出力（達成不可能）

計算量

• 時間計算量: \(O(N)\)
  • 全科目を1回ずつ見て不足分を計算するため
• 空間計算量: \(O(N)\)
  • 点数を格納する配列のサイズ
  • （配列を保持せずに処理すれば \(O(1)\) も可能）

実装のポイント

1. 不足分の計算に注意: \(A_i \geq T\) のとき、\(T - A_i\) は負になりますが、その場合は \(0\) として扱う必要があります。コードでは if a < T の条件分岐でこれを処理しています。

2. オーバーフローに注意: \(N\) が最大 \(10^5\)、不足分が最大 \(100\) 点なので、合計は最大 \(10^7\) 程度です。Pythonでは整数オーバーフローの心配はありませんが、他の言語では int 型で十分です。

3. 最小個数を求める: 「可能かどうか」だけでなく「最小個数」を求める問題ですが、不足分ぴったりの追加課題を使うのが最小なので、単純に合計値がそのまま答えになります。

   ソースコード

def solve():
    N, M, T = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 各科目で目標点Tに達するために必要な追加点数を計算
    total_needed = 0
    for a in A:
        if a < T:
            total_needed += T - a
    
    # M個の追加課題で足りるか判定
    if total_needed <= M:
        print(total_needed)
    else:
        print(-1)

solve()

---

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