成績表から学生の順位を求めるC++プログラムの解説

n × 4 のサイズを持つ 2 次元配列（成績表）を考えてみましょう。n 人の学生がおり、各学生には 0 から n-1 までの ID が割り当てられています。すべての学生は、英語・地理・数学・歴史という 4 科目の得点を持っています。

この成績表では、学生は合計点の降順に並べられます。また、合計点が同じ学生が複数存在する場合は、ID の昇順に並べ替えられます。今回の目的は、この並び順の中で「ID が 0 の学生」が何位になるかを求めることです。

入力例

この場合の出力は 2 となります。

実際に合計点を計算してみると、ID 0 の学生は 398 点、ID 1 の学生は 400 点、ID 2 の学生は 379 点、ID 3 の学生は 357 点です。ID 1 の学生だけが ID 0 の学生より合計点が高いため、ID 0 の学生の順位は 2 位になります。

解法のアプローチ

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

• まず、ID 0 の学生の 4 科目の合計点を変数 p として記録します。
• 順位を表すカウンタ r を 1 で初期化します。
• 残りの学生（ID 1 ～ n-1）について順番に合計点を計算し、p より大きければ r を 1 増やします。
• 最終的な r の値が、ID 0 の学生の順位となります。

同点の場合は ID の昇順で並べられるため、ID 0 の学生は同点のグループ内で必ず先頭に来ます。そのため、比較条件は「以上（>=）」ではなく「より大きい（>)」だけで十分です。

n := テーブルのサイズ
r := 1
p := table[0, 0] + table[0, 1] + table[0, 2] + table[0, 3]
i := 1 から n-1 まで繰り返す:
    もし table[i, 0] + table[i, 1] + table[i, 2] + table[i, 3] > p ならば:
        r を 1 増やす
r を返す

C++ での実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> table){
    int n = table.size();
    int r = 1;
    int p = table[0][0] + table[0][1] + table[0][2] + table[0][3];
    for (int i = 1; i < n; i++){
        if (table[i][0] + table[i][1] + table[i][2] + table[i][3] > p)
            r++;
    }
    return r;
}
int main(){
    vector<vector<int>> table = { { 100, 98, 100, 100 }, { 100, 100, 100, 100 }, { 90, 99, 90, 100 }, { 100, 98, 60, 99 } };
    cout << solve(table) << endl;
}

入力

{ { 100, 98, 100, 100 }, { 100, 100, 100, 100 }, { 90, 99, 90, 100 }, { 100, 98, 60, 99 } }

出力

2

計算量

このアルゴリズムは各学生の合計点を一度ずつ計算するだけなので、時間計算量は O(n)、追加のメモリ使用量は O(1) です。非常にシンプルかつ効率的な解法と言えます。