C++でビット単位ORがK以上となる部分配列の個数を求める方法

この記事では、C++を使って「ビット単位OR(論理和)がK以上となる部分配列の個数」を求める問題の解き方を解説します。整数の配列 arr[] と整数 K が与えられたとき、ORの値が K 以上になる部分配列が全部でいくつ存在するかを数えます。

入力: arr[] = {1, 2, 3}, K = 3
出力: 4

各部分配列のビット単位OR:
{1} = 1
{1, 2} = 3
{1, 2, 3} = 3
{2} = 2
{2, 3} = 3
{3} = 3
→ ORが3以上となる部分配列は4個

入力: arr[] = {3, 4, 5}, K = 6
出力: 2

解法へのアプローチ

ここでは、C++でこの問題を解くための2つの異なる手法を紹介します。

手法1: 全探索(ブルートフォース)

最もシンプルな方法は、考えられるすべての部分配列を列挙し、それぞれのビット単位ORがK以上であるかを順番にチェックすることです。条件を満たしていれば、答えのカウントを1つ増やします。

実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 2, 3}; // 与えられた配列
    int k = 3;
    int size = sizeof(arr) / sizeof(int); // 配列のサイズ
    int answer = 0; // 答えを数えるカウンタ変数
    for(int i = 0; i < size; i++){
        int bitwise = 0; // kと比較するための変数
        for(int j = i; j < size; j++){ // iから始まるすべての部分配列
            bitwise = bitwise | arr[j];
            if(bitwise >= k) // bitwiseがk以上なら答えをインクリメント
                answer++;
        }
    }
    cout << answer << "\n";
    return 0;
}

出力

4

この手法は非常にシンプルですが、弱点もあります。計算量が O(N×N)(Nは配列のサイズ)であるため、Nが大きくなると実行に非常に長い時間がかかってしまいます。そこで次に、より効率的なアプローチを見ていきましょう。

手法2: 効率的なアプローチ(セグメント木+二分探索)

この手法では、OR演算子の重要な性質を利用します。それは「要素を追加してもORの値は決して減少しない」というものです。つまり、区間 [i, j] のORがK以上であれば、その区間を完全に含む任意の部分配列のORも必ずK以上になります。この性質を活かすことで、コードを大幅に高速化できます。

具体的には、セグメント木で任意の区間のORを高速に求めながら、各左端 i に対して二分探索を用いて「ORが初めてK以上になる右端 j」を特定します。こうすることで、条件を満たす部分配列の個数をまとめて加算できます。

実装例

#include <bits/stdc++.h>
#define N 1000
using namespace std;
int t[4*N];
void build(int* a, int v, int start, int end){ // セグメント木の構築
    if(start == end){
        t[v] = a[start];
        return;
    }
    int mid = (start + end)/2;
    build(a, 2 * v, start, mid);
    build(a, 2 * v + 1, mid + 1, end);
    t[v] = t[2 * v] | t[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r){ // 区間クエリ(部分配列)の処理
    if (l > r)
        return 0;
    if(tl == l && tr == r)
        return t[v];
    int tm = (tl + tr)/2;
    int q1 = query(2*v, tl, tm, l, min(tm, r));
    int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r);
    return q1 | q2;
}
int main(){
    int arr[] = {1, 2, 3}; // 与えられた配列
    int k = 3;
    int size = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ
    int answer = 0; // 答えを数えるカウンタ変数
    build(arr, 1, 0, size - 1); // セグメント木を構築
    for(int i = 0; i < size; i++){
        int start = i, end = size-1;
        int ind = INT_MAX;
        while(start <= end){ // 二分探索
            int mid = (start + end) / 2;
            if(query(1, 0, size-1, i, mid) >= k){ // 部分配列のORを判定
                ind = min(mid, ind);
                end = mid - 1;
            }
            else
                start = mid + 1;
        }
        if(ind != INT_MAX) // 条件を満たす右端が見つかった場合のみ加算
            answer += size - ind;
    }
    cout << answer << "\n";
    return 0;
}

出力

4

この手法では、セグメント木と二分探索を組み合わせることで、計算量を O(N×N) から O(N log N) まで削減できます。これにより、全探索では現実的な時間内に処理できなかった大きな入力にも対応できるようになります。

まとめ

この記事では、「ビット単位ORがK以上となる部分配列の個数を求める」問題を、二分探索とセグメント木を用いて O(N log N) の計算量で解く方法を解説しました。全探索によるシンプルな解法と、効率化した解法の両方について、C++での実装例と考え方を紹介しています。同じロジックはC、Java、Pythonなど他の言語でも同様に実装可能です。この記事が皆さんの学習のお役に立てば幸いです。