コーディングコンテスト後の学生の順位を求めるC++プログラム

問題概要

n個の要素からなる配列Aがあるとします。あるコーディングコンテストには合計n人の学生が参加し、開始前の時点で全員が正の整数のレーティングを持っています。A[i]はi番目の学生のレーティングを表します。コンテスト終了後、すべての学生はそれぞれ正の整数の順位に着くことになります。学生はレーティングに応じて順位が決まり、学生Aのレーティングが学生Bより厳密に低い場合、Aの順位はBより厳密に大きい（下位の）番号になるとします。ここで、コンテスト終了時の各学生の順位を求めます。

例として、入力がA = [3, 5, 3, 4, 5]である場合を考えてみましょう。このとき出力は[4, 1, 4, 3, 1]になります。2番目と5番目の学生が最も高いレーティングで1位を分け合い、4番目の学生がその次の3位、そして1番目と3番目の学生が最も低い4位を分け合うためです。

解法の考え方

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

• 配列Aのサイズをnとします。
• 各学生iについて、「自分のレーティングA[i]よりも厳密に高いレーティングを持つ学生の人数」を数えます。
• その人数に1を加えた値が、i番目の学生の最終的な順位になります。同点の学生は自動的に同じ順位を共有することになります。

この方法の計算量はO(n²)ですが、実装が非常にシンプルで、同点による順位の共有も自然に処理できるのが特徴です。

アルゴリズム（擬似コード）

n := Aのサイズ
i := 0 から開始し、i < n の間繰り返す（iを1ずつ増やす）:
    d := 1
    j := 0 から開始し、j < n の間繰り返す（jを1ずつ増やす）:
        もし A[j] > A[i] ならば:
            d を 1 増やす
    cout << d << ", "

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A){
    int n = A.size();
    for (int i = 0; i < n; i++){
        int d = 1;
        for (int j = 0; j < n; j++){
            if (A[j] > A[i])
                d++;
        }
        cout << d << ", ";
    }
}
int main(){
    vector<int> A = { 3, 5, 3, 4, 5 };
    solve(A);
}

入力

{ 3, 5, 3, 4, 5 }

出力

4, 1, 4, 3, 1,

出力結果を見ると、2番目と5番目の学生が「1」、4番目の学生が「3」、1番目と3番目の学生が「4」となっており、期待どおりの順位が正しく求められていることが確認できます。