C++で隣接要素を考慮せずに配列のセットビット数の合計を最大化する方法

この問題では、整数型の配列 arr[] が与えられ、隣接する要素を選ばないという条件下で、配列内のセットビット（1になっているビット）数の合計が最大になるように求めるプログラムをC++で作成します。

問題の概要

ここで扱うのは、配列 arr[] の各要素についてセットビットの数を数え、隣接しない要素同士（例えば a[i] + a[i+2] のように1つ飛ばしで選んだ要素）のセットビット数の合計が最大となる値を求めるというものです。

具体例で問題を理解しよう

入力

arr[] = {1, 4, 6, 7}

出力

4

解説

まず、各要素を2進数で表すと次のようになります。

arr[] = {01, 100, 101, 111}
セットビット数の配列 = {1, 1, 2, 3}

次に、隣接しない要素の組み合わせごとにセットビット数の合計を計算します。

arr[0] + arr[2] = 1 + 2 = 3
arr[1] + arr[3] = 1 + 3 = 4

したがって、最大の合計は 4 となります。

解決アプローチ

この問題を解くためには、まず各数値に含まれるセットビットの数を求めます。その後、隣接しない要素同士の組み合わせの中で、セットビット数の合計が最大になるものを見つけます。

最大の合計は、偶数インデックス（0から始まる場合）の要素のみを選んだ場合と、奇数インデックスの要素のみを選んだ場合のどちらか一方に必ず含まれます。なぜなら、隣接しない要素を選ぶ場合、選び方としては「偶数番目だけを選ぶ」か「奇数番目だけを選ぶ」かの2通りに帰着できるからです。そのため、この2つの場合を比較するだけで答えが求まります。

なお、セットビットの数を効率的に数えるには、ブライアン・カーニガンのアルゴリズムが便利です。「n & (n-1)」を繰り返し計算すると、1回の操作ごとに最下位のセットビットが1つ消えていくため、セットビットの数だけループが回る効率的な方法です。

解法の実装例

サンプルコード

#include<iostream>
using namespace std;

// セットビットの数を数える関数（ブライアン・カーニガンのアルゴリズム）
int countSetBit(int n){
    int setBits = 0;
    while(n) {
        setBits++;
        n = n & (n - 1);
    }
    return setBits;
}

// 隣接しない要素のセットビット数の合計の最大値を求める関数
int findMaxBitAltSubArray(int arr[], int n){
    int EvenSum = countSetBit(arr[0]);  // 偶数インデックスの合計
    int OddSum = 0;                      // 奇数インデックスの合計
    for (int i = 1; i < n; i++){
        if(i % 2 == 0){
            EvenSum += countSetBit(arr[i]);
        } else {
            OddSum += countSetBit(arr[i]);
        }
    }
    if(EvenSum >= OddSum){
        return EvenSum;
    }
    return OddSum;
}

int main() {
    int arr[] = {1, 4, 6, 7};
    int n = 4;
    cout<<"隣接要素を考慮しない場合のセットビット数の合計の最大値は "
        <<findMaxBitAltSubArray(arr, n);
    return 0;
}

出力

隣接要素を考慮しない場合のセットビット数の合計の最大値は 4

計算量について

この解法の時間計算量は、各要素のセットビット数を数える処理が O(log N)（Nは要素の値）、配列全体を1回走査するので全体として O(n log N) となります。空間計算量は O(1) で、追加の配列などを必要としない効率的な実装です。

まとめ

本記事では、配列内の各要素のセットビット数を求め、隣接する要素を選ばない条件下でセットビット数の合計を最大化する方法を解説しました。ポイントは以下の通りです。

• セットビットの数え方には「n & (n-1)」を利用したブライアン・カーニガンのアルゴリズムが有効
• 隣接しない要素の選び方は「偶数インデックスのみ」か「奇数インデックスのみ」の2通りに帰着できる
• 2つの合計を比較するだけで最大値が求まり、計算量は O(n log N) で効率的