C++で1人目の学生に割り当て可能な最大スコアを求める方法

n 個の要素を持つ配列 A と数値 m が与えられているとします。n 人の学生が試験を受けており、取りうる最高得点は m です。A[i] は i 番目の学生の得点を表します。各学生の得点は自由に変更できますが、次の条件を満たす必要があります。

• どの得点も m を超えないこと
• すべての得点が整数であること
• 全学生の平均点が変化しないこと

このとき、1 人目の学生の得点を最大化したい場合、割り当てられる最高得点はいくつになるでしょうか。

例

たとえば、入力が A = [1, 2, 3, 4]、m = 10 の場合を考えてみましょう。このときの出力は 10 になります。元の平均点は 2.5 ですが、得点を [10, 0, 0, 0] と設定しても合計点(したがって平均点)は変わらず、1 人目の得点を最大にできます。

解法のアプローチ

この問題の鍵となるのは「平均点が変わらない」という条件です。学生の人数は固定なので、平均点が変わらないということは、合計点も変わらないことを意味します。したがって、1 人目の学生に割り当てられる最大の得点は、次の 2 つの制約から決まります。

• 得点は m を超えられない
• 他の学生の得点は 0 以上であるため、1 人目の得点は全体の合計点(sum)を超えられない

よって、答えは m と sum のうち小さい方(min(m, sum))となります。

手順

1. 合計 sum を 0 で初期化する
2. n を配列 A のサイズとする
3. j = 0 から n-1 までループし、sum に A[j] を順に加算する
4. m と sum の最小値を返す

C++ 実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int m){
    int sum = 0;
    int n = A.size();
    for (int j = 0; j < n; j++){
        sum += A[j];
    }
    return min(m, sum);
}
int main(){
    vector<int> A = { 1, 2, 3, 4 };
    int m = 10;
    cout << solve(A, m) << endl;
}

入力

{ 1, 2, 3, 4 }, 10

出力

10