【C++】全員にボーナス点を加算しても100点を超えない条件下で、合格できる学生の最大人数を求めるプログラム

この問題では、クラス内の各学生の試験点数を格納したサイズ n の配列 stu[] が与えられます。各学生の満点は100点であり、合格には50点以上が必要です。全員に一律でボーナス点を加算し、かつ誰の点数も100点を超えないという条件のもとで、合格できる学生の最大人数を求めるプログラムを作成することが課題です。

問題の概要

合格者を増やすために学生へボーナス点を与えますが、このボーナスはクラス全体に対して同じ値を加算しなければなりません。誰かの合計点が100点を超えてしまわない範囲でボーナス点を設定し、それによって合格できる学生の数を最大化します。最後に、合格できる学生の最大人数を返します。

入出力例で問題を理解する

入力

stu[] = {45, 32, 78, 10, 53, 67}

出力

5

説明

合格できる学生は以下の通りです。
45 + 22 = 67
32 + 22 = 54
78 + 22 = 100
53 + 22 = 75
67 + 22 = 89

最高得点は78点なので、加算できるボーナスは 100 − 78 = 22点です。このボーナスを全員に加算すると、上記の5人が50点以上となり合格できます（10点の学生は 10 + 22 = 32 点のため不合格）。

解決アプローチ

この問題を解くには全員にボーナス点を加算しますが、どの学生の点数も100点を超えてはならない点に注意が必要です。したがって、与えられることのできる最大のボーナス点は次のように計算できます。

最高得点者の点数(M) + ボーナス = 100
ボーナス = 100 − M

このボーナス点を全員の現在の点数に加算し、合計が50点以上であればその学生は合格です。答えは、条件を満たした学生の総数となります。

アルゴリズム

初期化

passCount = 0;

ステップ1

最高得点(maxMarks)を持つ学生を見つける。

ステップ2

全員に与えられるボーナス点を計算する。bonus = 100 − maxMarks。

ステップ3

i を 0 から n−1 までループさせる。

ステップ3.1

if(stu[i] + bonus >= 50) の場合、passCount++ とする。

ステップ4

passCount を返す。

C++実装例

ソリューションの動作を示すプログラムは以下の通りです。

#include<iostream>
using namespace std;
int calcPassCount(int stu[], int n) {
    int maxMarks = stu[0];
    for(int i = 1; i < n; i++){
        if(stu[i] > maxMarks)
            maxMarks = stu[i];
    }
    int bonusMarks = 100 − maxMarks;
    int passCount = 0;
    for(int i = 0; i < n; i++) {
        if(stu[i] + bonusMarks >= 50)
            passCount ++;
    }
    return passCount;
}
int main() {
    int stu[] = {45, 32, 78, 10, 53, 67};
    int n = sizeof(stu)/sizeof(stu[0]);
    cout<<"全員にボーナスを与えた後に合格できる学生の最大人数は "<<calcPassCount(stu, n);
    return 0;
}

出力

全員にボーナスを与えた後に合格できる学生の最大人数は 5

計算量について

このアルゴリズムでは配列を2回走査するため、時間計算量は O(n) です。また、使用する変数は定数個のみであるため、空間計算量は O(1) となります。非常にシンプルかつ効率的な解法と言えるでしょう。