C++で招待を辞退した参加者の最小人数を求めるアルゴリズム

問題概要

すべての要素が異なる n 個の整数からなる配列 A があるとします。あるコンテストのオンサイト決勝に進んだファイナリストがおり、その予選順位が配列 A に格納されています。決勝ラウンドへの現地参加の招待を辞退した出場者の最小人数を求めるのがこの問題の目的です。オンサイトで参加できるのは全部で 25 人であり、そのうち何人かは招待を受け入れ、何人かは辞退している状況を想定します。

たとえば、入力が A = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28] の場合、出力は 3 になります。これは、1位・13位・27位の人が招待を辞退したと考えられるためです。

解法のアプローチ

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

• 配列 A 内の最大値 mx を求めます。
• mx − 25 と 0 のうち大きい方の値を答えとして返します。

このアルゴリズムが成り立つ理由は次の通りです。最大順位 mx の人が招待を受け入れているということは、招待が順位の高い方から順に送られている以上、1位から mx 位までの人全員に招待が届いていたことを意味します。しかし、オンサイトで参加できるのは 25 人までなので、mx が 25 を超える場合は少なくとも mx − 25 人が辞退したことになります。逆に mx が 25 以下であれば、全員が枠内に収まるため、辞退者は 0 人です。

実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
    int mx = 0;
    for (int i = 0; i < A.size(); i++)
        mx = max(mx, A[i]);
    return max(mx - 25, 0);
}
int main(){
    vector<int> A = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
        24, 25, 26, 28 };
    cout << solve(A) << endl;
}

入力

{ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28 }

出力

3

計算量

時間計算量は O(n)（配列を一度だけ走査）、空間計算量は O(1)（追加メモリ不要）と非常に効率的です。