PythonでビットごとANDとORの合計が最大になる部分列の組み合わせを求める方法

問題の概要

n個の要素からなる配列が与えられたとき、その配列から2つの部分列を選びます(2つの部分列は同じものでも異なるものでも構いません)。そして、1つ目の部分列の全要素のビットごとのAND(論理積)の値と、2つ目の部分列の全要素のビットごとのOR(論理和)の値を足し合わせた合計が最大になるようにします。

例えば、入力が A = {4, 6, 7, 2} の場合、出力は 14 になります。これは、要素「7」だけを選ぶことで最大のAND値である7が得られ、すべての要素(4 | 6 | 7 | 2)= 7 を選ぶことで最大のOR値である7が得られるためです。したがって、結果は 7 + 7 = 14 となります。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• and_max := 配列の最大値を設定する
• or_max := 0 で初期化する
• i を 0 から配列のサイズまで繰り返す:
  • or_max := or_max OR arr[i](各要素を順にORで結合する)
• and_max + or_max を返す

なぜこの方法が最適なのか

ビットごとのAND演算では、要素を追加するたびに結果のビットが0になる可能性があるため、単一の要素だけを選ぶのが最も有利です。つまり、配列内の最大値のみを選択すれば、それが最大のAND値になります。

一方、ビットごとのOR演算では、一度立ったビットは後続の演算で消えることがありません。そのため、すべての要素を選択することで、必ず最大のOR値が得られます。

Pythonでの実装例

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

def get_max_sum(arr):
    and_max = max(arr)
    or_max = 0
    for i in range(len(arr)):
        or_max |= arr[i]
    return and_max + or_max

a = [4, 6, 7, 2]
print(get_max_sum(a))

入力

[4,6,7,2]

出力

14

計算量について

このアルゴリズムは配列を一度走査するだけでよいため、時間計算量は O(n)、追加のメモリをほとんど必要としないため空間計算量は O(1) となります。非常にシンプルでありながら最適な解法と言えます。