C++で解く「適切な年齢の友達」問題 ― フレンド申請の総数を効率よく求める方法

問題概要

複数の人が互いにフレンド申請(友達リクエスト)を送る場面を考えてみましょう。各人の年齢は配列 ages に格納されており、ages[i] が i 番目の人の年齢を表します。このとき、人物 A は次のいずれかの条件に当てはまる場合、人物 B(B ≠ A)に対してフレンド申請を送りません。

• age[B] <= 0.5 * age[A] + 7
• age[B] > age[A]
• age[B] > 100 かつ age[A] < 100

これらの条件に該当しなければ、A は B にフレンド申請を送ります。なお、A が B に申請したからといって、B が必ずしも A に申請するとは限りません。また、自分自身へ申請することはできません。求めたいのは、最終的に発生するフレンド申請の総数です。

入力例

たとえば年齢の配列が [16, 17, 18] のとき、答えは 2 になります。「17 → 16」「18 → 17」の 2 件の申請だけが成立するためです。

解き方のポイント:バケットと累積和

すべてのペアを素朴に調べると計算量が O(n²) になってしまいますが、年齢ごとの人数を集計する「バケット」とその「累積和」を組み合わせれば、はるかに効率的に処理できます。手順は以下の通りです。

1. サイズ 1000 の配列 bucket を用意し、ages の各年齢の出現回数をカウントします。
2. bucket の累積和(先頭からの合計)を計算し、同じ配列に上書き保存します。これにより bucket[v] は「年齢 v 以下の人数」を表すようになります。
3. 答えを保持する変数 ret を 0 で初期化します。
4. i を 0 から ages.size() - 1 まで順に処理します。
   • x := ages[i]、y := ages[i] / 2 + 7 とします。
   • x >= y の場合、bucket[x] - bucket[y](年齢が y より大きく x 以下の人数)を ret に加算します。
   • 加算した値が非ゼロなら、自分自身まで数えてしまっているため、ret を 1 減らして除外します。
5. 最後に ret を返します。

補足すると、y = x / 2 + 7 は「申請が許される相手の年齢の下限」に相当します。x < y となるのは x が 14 歳未満のときだけであり、つまり 14 歳未満の人は誰にもフレンド申請できないということになります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        vector<int> bucket(1000);
        for(int i = 0; i < ages.size(); i++){
            bucket[ages[i]]++;
        }
        for(int i = 1; i < 1000; i++)bucket[i] += bucket[i - 1];
        int ret = 0;
        for(int i = 0; i < ages.size(); i++){
            int x = ages[i];
            int y = ((ages[i]) / 2) + 7;
            if(x >= y){
                ret += (bucket[x] - bucket[y]);
                if((bucket[x] - bucket[y]))
                ret--;
            }
        }
        return ret;
    }
};
main(){
    vector<int> v1 = {16, 17, 18};
    Solution ob;
    cout << (ob.numFriendRequests(v1));
}

実行結果

入力:

[16,17,18]

出力:

2

計算量の評価

年齢のカウントに O(n)、累積和の構築に O(A)(A は年齢の上限値、ここでは 1000)、メインのループに O(n) の計算時間が必要です。したがって全体の計算量は O(n + A) となります。O(n²) かかる全ペアの総当たりと比べると、人数が多いケースでも非常に高速に動作するのが大きな利点です。