C++でグループサイズに基づいて人々をグループ化するアルゴリズム

0からn-1までのIDを持つn人の人がおり、各人は必ず1つのグループに所属しているとします。長さnの配列groupSizesが与えられ、この配列の各要素はその人が所属すべきグループのサイズを示しています。ここでの課題は、実際に形成されるグループと、各グループに含まれる人々のIDを見つけ出すことです。

例えば、入力が [3,3,3,3,3,1,3] の場合、出力は [[5], [0, 1, 2], [3, 4, 6]] となります。なお、答えは一意ではなく、[[2,1,6],[5],[0,4,3]] や [[5],[0,6,2],[4,3,1]] なども有効な解として認められます。

解法のアプローチ

この問題は、ハッシュマップ（連想配列）を活用することで効率的に解決できます。基本的な発想は、「同じグループサイズを要求する人々をまずまとめ、その後指定されたサイズごとに分割する」というものです。具体的には以下の手順に従います。

• キーをグループサイズ、値をそのサイズに該当する人のIDリストとするマップ m を作成する
• i を 0 から配列 g のサイズ - 1 まで繰り返し処理する：
  • m[g[i]] に i を挿入する
• 結果を格納する二次元配列 res を作成する
• マップ m の各要素 i に対して以下を処理する：
  • j を 0 から i が持つリストのサイズ - 1 まで繰り返す：
    • i のリストの j 番目の要素を一時配列 temp に追加する
    • temp のサイズが i のキー（グループサイズ）と一致した場合：
      • temp を res に新しい行として追加する
      • temp をクリアして次のグループに備える
• 最終的に res を返す

この手法により、各グループは必ず指定されたサイズちょうどになるように分割されます。それでは、実際の実装を見て理解を深めましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << "[";
       for(int j = 0; j <v[i].size(); j++){
          cout << v[i][j] << ", ";
       }
       cout << "],";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<vector<int>> groupThePeople(vector<int>& g) {
        map <int, vector <int> > m;
        for(int i = 0; i < g.size(); i++){
           m[g[i]].push_back(i);
        }
        vector < vector <int> > res;
        map <int, vector <int> > :: iterator i = m.begin();
        vector <int> temp;
        while(i != m.end()){
           for(int j = 0; j < i->second.size(); j++){
              temp.push_back(i->second[j]);
              if(temp.size() == i->first){
                 res.push_back(temp);
                 temp.clear();
              }
           }
           i++;
        }
        return res;
    }
};
main(){
    vector<int> v = {3,3,3,3,3,1,3};
    Solution ob;
    print_vector(ob.groupThePeople(v));
}

入力

[3,3,3,3,3,1,3]

出力

[[5],[0, 1, 2],[3, 4, 6]]

計算量について

このアルゴリズムの時間計算量は O(n log n) です。これは、std::map が内部的に平衡二分木を使用しており、挿入や検索に O(log n) のコストがかかるためです。もし順序が不要であれば、unordered_map を使用することで平均 O(n) まで高速化できます。空間計算量は O(n) であり、すべての人のIDを格納するために必要となります。