【C++】出席率75%を維持するために必要な最小講義数を求めるプログラム

はじめに

この問題では、これまでに開講された講義の総数を表す M と、学生がすでに出席した講義の回数を表す N の2つの数値が与えられます。求めるのは、C++で出席率75%を維持するために、今後最低限出席すべき講義の回数です。

問題の概要

大学生活において、出席率75%の維持は多くの学生にとって切実な関心事の一つです。本プログラムは、出席率75%を達成するために、学生が今後ために、学生が今後継続的に出席しなければならない講義の最小回数を計算します。

具体例を使って問題を確認してみましょう。

例1

入力: M = 32、N = 20

出力: 16

解説: 出席率75%以上を達成するには、最低でもあと16回の講義に出席する必要があります。これにより総講義数は48回、出席済み講義数は36回となります。

出席率 = 36 × 100 ÷ 48 = 75%

例2

入力: M = 14、N = 4

出力: 26

解説: 出席率75%以上を達成するには、最低でもあと26回の講義に出席する必要があります。これにより総講義数は40回、出席済み講義数は30回となります。

出席率 = 30 × 100 ÷ 40 = 75%

解法アプローチ①：シミュレーション（計算量 O(n)）

求めたいのは、学生がこれから追加で出席すべき講義の回数です。最もシンプルな方法は、追加出席回数を1ずつ増やしながら出席率を計算し、その割合が75%以上になった時点でループを終了して、そのときの値を返すというものです。

この解法の動作を示すサンプルコード：

#include <iostream>
using namespace std;
int maintainAtt(int M, int N) {
    int att = 0;
    while(1){
        if(((N+att)*100)/(M+att) >= 75){
            return att;
        }
        att++;
    }
}
int main() {
    int M = 23, N = 12;
    cout<<"The total number of lectures to be attended is "<<maintainAtt(M, N);
    return 0;
}

実行結果

The total number of lectures to be attended is 21

※ 訳：「出席すべき講義の総数は21回です」

解法アプローチ②：数式を使った定数時間での求解（計算量 O(1)）

上記の方法はループ処理を行うため、計算量は O(n) となります。しかし、必要な回数を数学的に導出すれば、O(1) の計算量で即座に答えを求めることが可能です。

条件「(N + att) ÷ (M + att) ≥ 0.75」を式変形すると、次のようになります。

N + att ≥ 0.75 × (M + att)
0.25 × att ≥ 0.75 × M − N
att ≥ (0.75 × M − N) ÷ 0.25

したがって、出席率75%を維持するために必要な最小講義数の公式は次のとおりです。

att = ⌈(0.75 × M − N) ÷ 0.25⌉（小数点以下は切り上げ）

この解法の動作を示すサンプルコード：

#include <iostream>
#include <math.h>
using namespace std;
int maintainAtt(int M, int N) {
    int att = ceil(((0.75*M) - N)/(0.25));
    return att;
}
int main() {
    int M = 30, N = 11;
    cout<<"The total number of lectures to be attended is "<<maintainAtt(M, N);
    return 0;
}

実行結果

The total number of lectures to be attended is 46

※ 訳：「出席すべき講義の総数は46回です」

まとめ

出席率75%の維持という現実的な問題に対して、ループで1回ずつ試すシミュレーション方式でも十分に機能します。ただし、数式を用いた解法なら計算量 O(1) で一瞬にして答えを得られるため、入力値が大きい場合や高速な処理が求められる場面では、数式ベースのアプローチを採用するのが効果的です。