C++で解く：お気に入り企業リストが他の誰のリストの部分集合でもない人を求めるアルゴリズム

問題概要

favoriteCompanies という配列があるとします。ここで favoriteCompanies[i] は、i 番目の人のお気に入り企業のリストを表します。この問題では、自分のお気に入り企業リストが他のどのリストの部分集合にもなっていない人を見つけ、そのインデックスをすべて返します。

たとえば、入力が favoriteCompanies = [["TCS", "google", "facebook"], ["google", "microsoft"], ["google", "facebook"], ["google"], ["amazon"]] の場合、出力は [0, 1, 4] になります。その理由は次のとおりです。

• インデックス 2 の人のリスト ["google", "facebook"] は、インデックス 0 の人の favoriteCompanies[0] = ["TCS", "google", "facebook"] に完全に含まれている(部分集合である)ため、結果から除外されます。
• インデックス 3 の人のリスト ["google"] は、favoriteCompanies[0] = ["TCS", "google", "facebook"] と favoriteCompanies[1] = ["google", "microsoft"] のどちらの部分集合でもあるため、これも除外されます。
• 残りのインデックス 0、1、4 のリストは、他のどのリストの部分集合でもないため、答えは [0, 1, 4] となります。

解法のアプローチ

各リストをあらかじめ辞書順にソートしておけば、「リスト a がリスト b の部分集合かどうか」はツーポインタ(2つのポインタ)を使ったマージの要領で効率よく判定できます。a のすべての要素が b にも現れる場合は部分集合、1つでも現れない要素があれば部分集合ではありません。

アルゴリズムの手順

• 配列 a と配列 b を受け取る関数 ok() を定義します。
• cnt := 0、i := 0、j := 0 で初期化します。
• i が a のサイズ未満 かつ j が b のサイズ未満の間、次を繰り返します。
  • a[i] が b[j] と等しい場合:i、j、cnt をそれぞれ 1 増やします。
  • a[i] が b[j] より小さい場合:i を 1 増やします。
  • それ以外の場合:j を 1 増やします。
• cnt が a のサイズより小さい場合に true を返します(a の要素の一部が b に存在しない、つまり部分集合ではないことを意味します)。
• メイン処理では次を行います。
  • 結果を格納するセット s を用意します。
  • n := f のサイズ とします。
  • i := 0 から n - 1 までの各 i について、f[i] をソートします。
  • 再び各 i について c := true とし、j = 0 から n - 1 までの各 j(i ≠ j)に対して c := c AND ok(f[i], f[j]) を計算します。
  • c が true のまま残った場合、つまり f[i] がどの他のリストの部分集合でもなかった場合、i をセット s に挿入します。
• 最後に、s の要素を配列として返します。

C++ 実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    bool ok(vector<string>& a, vector<string>& b){
       int cnt = 0;
       int i = 0;
       int j = 0;
       while (i < a.size() && j < b.size()) {
          if (a[i] == b[j]) {
             i++;
             j++;
             cnt++;
          }
          else if (a[i] < b[j]) {
             i++;
          }
          else {
             j++;
          }
       }
       return cnt < a.size();
    }
    vector<int> peopleIndexes(vector<vector<string> >& f){
       set<int> s;
       int n = f.size();
       for (int i = 0; i < n; i++) {
          sort(f[i].begin(), f[i].end());
       }
       for (int i = 0; i < n; i++) {
          bool c = true;
          for (int j = 0; j < n; j++) {
             if (i == j)
                continue;
             c &= ok(f[i], f[j]);
          }
          if (c)
             s.insert(i);
       }
       return vector<int>(s.begin(), s.end());
    }
};
main(){
    Solution ob;
    vector<vector<string>> v = {{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}};
    print_vector(ob.peopleIndexes(v));
}

入力

{{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}}

出力

[0, 1, 4]

計算量の目安

n を人数、L をリスト長の最大値とすると、すべてのリストのソートには全体で O(n・L log L)、部分集合判定は 1 ペアあたり O(L) で、全ペアを調べるため合計 O(n²・L) となります。制約が小さい場合は十分実用的ですが、入力規模が大きい場合はビットセットやハッシュ集合を活用した高速化も検討するとよいでしょう。