C++で部分配列のビットごとのOR（Bitwise OR）の異なる結果数を求める方法

問題概要

負でない整数からなる配列 A があるとします。すべての連続する部分配列 B = [A[i], A[i+1], ..., A[j]]（i ≤ j）に対して、B に含まれる全要素のビットごとのORを計算し、A[i] | A[i+1] | ... | A[j] という結果を得ます。このとき、得られる可能性のある結果の個数を求めるのが目的です。ただし、同じ結果が複数回現れた場合は、最終的な答えには1回だけカウントします。

例えば、入力が [1,1,2] の場合を考えてみましょう。部分配列は [1]、[1]、[2]、[1,1]、[1,2]、[1,1,2] の6通りあり、それぞれのORの結果は 1、1、2、1、3、3 となります。したがって、異なる結果は「1」「2」「3」の3つとなり、答えは 3 です。

アルゴリズム

この問題を解くために、以下の手順に従います。

• 2つの集合 ret と curr2 を作成します。

• i を 0 から配列のサイズまで繰り返します。

  • 新しい集合 curr1 を作成し、A[i] を挿入します。

  • curr2 内の各要素 e について、(e OR A[i]) を curr1 に挿入します。

  • curr1 内の各要素 e について、e を ret に挿入します。

  • curr2 := curr1 と更新します。

• ret のサイズを返します。

ここで重要なポイントは、「あるインデックス i で終わる部分配列のORの値」の候補は、int型のビット数（32）以下にしかならないということです。OR演算はビットを立てる方向にのみ働くため、部分配列の左端を伸ばしてもORの値は増えるか同じままとなり、異なる値の個数はビット数で頭打ちになります。そのため、curr2 には「直前のインデックスで終わる部分配列のOR値の集合」だけを保持すればよく、全体の計算量は O(n × ビット数) 程度に抑えられます。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int subarrayBitwiseORs(vector<int>& A) {
        unordered_set <int> ret;
        unordered_set <int> curr2;
        for(int i = 0; i < A.size(); i++){
            unordered_set <int> curr1;
            curr1.insert(A[i]);
            unordered_set<int>::iterator it = curr2.begin();
            while(it != curr2.end()){
                curr1.insert(*it | A[i]);
                it++;
            }
            it = curr1.begin();
            while(it != curr1.end()){
                ret.insert(*it);
                it++;
            }
            curr2 = curr1;
        }
        return ret.size();
    }
};
main(){
    vector<int> v = {1,1,2};
    Solution ob;
    cout << (ob.subarrayBitwiseORs(v));
}

入力

[1,1,2]

出力

3