【C++】配列のビットごとのORを最大化するアルゴリズム

問題の概要

N個の整数からなる配列が与えられます。ここで、配列内の任意の1つの要素に対して、指定された整数 x を最大 k 回まで乗算するという操作を一度だけ行い、配列全体のビットごとのOR(論理和)を最大化することを考えます。

たとえば、入力配列が {4, 3, 6, 1}、k = 2、x = 3 の場合、得られる最大値は 55 となります。これは、要素「6」に 3^2 = 9 を掛けて 54 とし、残りの要素 {4, 3, 1} とのORを取ると 54 | 4 | 3 | 1 = 55 になるためです。

アルゴリズム

どの要素を何倍すればよいかを毎回総当たりで調べるのは非効率です。そこで、前方向と後ろ方向のORを事前に計算しておくことで、効率的に解くことができます。

1. 各要素に x^k(xのk乗)を乗算し、それより前にあるすべての要素のビットごとのORと組み合わせます(prefixOR)
2. 同様に、それより後にあるすべての要素のビットごとのORとも組み合わせます(suffixOR)
3. すべての要素について上記の計算を行い、得られた値の最大値を返します

この手法により、時間計算量は O(N + K)、空間計算量は O(N) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int getMaxOr(int *arr, int n, int k, int x){
    int prefixSum[n + 1];
    int suffixSum[n + 1];
    int power = 1;
    for (int i = 0; i < k; ++i) {
        power = power * x;
    }
    prefixSum[0] = 0;
    for (int i = 0; i < n; ++i) {
        prefixSum[i + 1] = prefixSum[i] | arr[i];
    }
    suffixSum[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        suffixSum[i] = suffixSum[i + 1] | arr[i];
    }
    int result = INT_MIN;
    for (int i = 0; i < n; ++i) {
        result = max(result, prefixSum[i] | (arr[i] * power) | suffixSum[i + 1]);
    }
    return result;
}
int main(){
    int arr[] = {4, 3, 6, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    int x = 3;
    cout << "Result = " << getMaxOr(arr, n, k, x) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Result = 55

コードのポイント解説

• 変数 power には x^k の値が格納されます。k回の乗算をあらかじめ1回の計算にまとめておくことで無駄を省いています。
• prefixSum[i] は「位置 i の直前までの要素のOR」、suffixSum[i + 1] は「位置 i より後ろの要素のOR」をそれぞれ保持しています。
• ループ内では、各要素 arr[i] を power 倍した場合の配列全体のORを計算し、これまでの最大値と比較しながら更新していきます。
• どの要素を強化しても他の要素は元のままなので、prefixOR と suffixOR を分けて管理するだけで全パターンを高速に評価できます。