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

はじめに

この記事では、全員に同じボーナス点を加算しても、どの学生も100点を超えないという条件下で、合格できる学生の最大人数を求めるC++プログラムについて解説します。

具体的には、N人の学生の点数が格納された配列が与えられます。各学生に同じ量のボーナス点を加えることで、より多くの学生(合格ラインは50点)を合格させることが目的です。ただし、加点によってどの学生も100点を超えてはいけません。

アルゴリズムの考え方

この問題は次の手順で解くことができます。

• まず、配列内の最高得点を見つけます。
• 最高得点の学生がちょうど100点になるようにボーナス点を計算します(ボーナス = 100 − 最高得点)。これにより、加点できるボーナスは最大限になります。
• そのボーナス点を全員に加算したとき、50点以上となる学生の数を数えます。

最高得点の学生を基準にすることで、ルール違反(100点超え)を避けつつ、ボーナスを最大化できます。結果として、合格できる人数も最大になります。

実装例

#include<iostream>
#include<algorithm>
using namespace std;
int check(int n, int marks[]) {
    int* x = std::max_element(marks,marks+5);
    int bonus = 100-(int)(*x);
    int c = 0;
    for(int i=0;
    i<n;i++) {
        if(marks[i] + bonus >= 50) c += 1;
    }
    return c;
}
int main() {
    int n = 5;
    int marks[] = {0, 21, 83, 45, 64};
    cout<<check(n, marks)<<endl;
    return 0;
}

出力

3

コードの解説

上記の例では、5人の学生の点数として {0, 21, 83, 45, 64} が与えられています。処理の流れは以下の通りです。

• std::max_element を使用して、配列内の最高得点である 83点 を取得します。
• ボーナス点は 100 − 83 = 17点 と計算されます。
• 各学生に17点を加算すると、点数は {17, 38, 100, 62, 81} となります。
• 50点以上となるのは 100点・62点・81点 の 3人 であるため、出力は「3」になります。

まとめ

このアルゴリズムの計算量は、最高得点の探索と合格者数のカウントでそれぞれ配列を一度走査するため、O(N) です。ボーナス点の上限を最高得点から逆算するシンプルな発想により、効率的に答えを求められるのがポイントです。