C++で解く!2つの配列から選ぶ部分配列の最大OR和の求め方

問題文

正の整数からなる2つの配列が与えられます。それぞれの配列から同じサイズの部分配列を1つずつ選び、その2つの部分配列に対してビットごとの論理和(OR)を計算したとき、その合計として考えられる最大値を求めてください。

例

たとえば、次の2つの配列が与えられたとします。

arr1[] = {1, 2, 4, 3, 2}
arr2[] = {1, 3, 3, 12, 2}

この場合、以下のように部分配列を選ぶと最大の結果が得られます。

Subarr1[] = {2, 4, 3}
Subarr2[] = {3, 3, 12}

このとき Subarr1 のOR値は 7、Subarr2 のOR値は 15 となり、合計は 22 になります。

アプローチ:ORの単調性を利用する

この問題を効率的に解く鍵は、OR演算の重要な性質にあります。ORでは、すでに立っているビットが要素を追加しても消えることはなく、新しいビットが立ちうるだけです。つまり、部分配列に含める要素を増やすほど、ORの値は増加するか、せいぜい変わらないという単調性が成り立ちます。

したがって、ある配列から得られるOR値の最大は、その配列全体のORを取ったときに実現されます。本問題では2つの配列の長さがともにnであるため、それぞれの配列全体を選べば「同じサイズの部分配列」という条件も同時に満たします。

結論として、答えは次の式で求められます。

f(a, 1, n) + f(b, 1, n)

ここで f(x, l, r) は、配列 x の区間 [l, r] に含まれる要素すべてのOR値を表します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int getMaximumSum(int *arr1, int *arr2, int n) {
    int sum1 = 0;
    int sum2 = 0;
    for (int i = 0; i < n; ++i) {
        sum1 = sum1 | arr1[i];
        sum2 = sum2 | arr2[i];
    }
    return sum1 + sum2;
}
int main() {
    int arr1[] = {1, 2, 4, 3, 2};
    int arr2[] = {1, 3, 3, 12, 2};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    cout << "Maximum result = " << getMaximumSum(arr1, arr2, n) << endl;
    return 0;
}

実行結果

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

Maximum result = 22

計算量

各配列を一度だけ走査すればよいため、時間計算量は O(n)、使用する追加メモリは定数のみで空間計算量は O(1) です。部分配列の組み合わせを全探索する非効率な手法と比べて、非常にシンプルかつ高速な解法といえます。