C++で実装する「Kに最も近い部分配列のビットごとのAND」問題の解法

問題の概要

この問題では、サイズ n の配列 arr[] と整数 k が与えられます。私たちのタスクは、インデックス i から j までの部分配列を選び、そのすべての要素のビットごとのAND(論理積)を計算することです。その後、|K − (部分配列のビットごとのAND)| の最小値を出力します。

具体例で問題を確認してみましょう。

入力: arr[] = {5, 1}, k = 2

この場合、考えられる部分配列は {5}、{1}、{5, 1} であり、それぞれのAND値は 5、1、1 となります。k = 2 との差の絶対値はそれぞれ 3、1、1 なので、答えは 1 になります。

解法1: 全探索によるシンプルなアプローチ

最も直接的な解法は、すべての部分配列についてビットごとのANDを求め、その値と K の差の絶対値を計算する方法です。

アルゴリズムの手順

ステップ1: すべての部分配列についてビットごとのANDを求めます。

ステップ2: ステップ1で得られた各値(仮に X とする)に対して、|k − X| を計算します。

ステップ3: 求まった最小値を変数 minimum に保存し続けます。

ステップ4: 最後に minimum の値を出力します。

実装例

#include <iostream>
using namespace std;
int CalcBitwiseANDClosestK(int arr[], int n, int k){
    int minimum = 1000;
    for (int i = 0; i < n; i++) {
        int X = arr[i];
        for (int j = i; j < n; j++) {
            X &= arr[j];
            minimum = min(minimum, abs(k - X));
        }
    }
    return minimum;
}
int main() {
    int arr[] = { 1, 6 , 4, 9, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout<<"Minimum value difference between Bitwise AND of sub-array and K is "<<CalcBitwiseANDClosestK(arr, n, k);
    return 0;
}

出力

Minimum value difference between Bitwise AND of sub-array and K is 1

この方法の計算量は O(n²) であり、配列サイズが大きくなると処理時間が増加します。

解法2: AND演算の性質を利用した最適化

もうひとつの効率的な解法は、ビットごとのAND演算の重要な性質に着目するものです。ビットごとのANDは、要素を追加しても値が増えることはありません(単調非増加)。つまり、部分配列が長くなるほどANDの結果は同じか小さくなっていきます。

この性質を利用すると、ANDの結果 X が k 以下になった時点で、それ以降の要素を追加しても |k − X| は増える一方であるため、内側のループを途中で打ち切ることができます。これにより、多くの場合で大幅な高速化が期待できます。

実装例

#include <iostream>
using namespace std;
int CalcBitwiseANDClosestK(int arr[], int n, int k){
    int minimum = 1000000;
    for (int i = 0; i < n; i++) {
        int BitwiseAND = arr[i];
        for (int j = i; j < n; j++) {
            BitwiseAND &= arr[j];
            minimum = min(minimum, abs(k - BitwiseAND));
            if (BitwiseAND <= k)
                break;
        }
    }
    return minimum;
}
int main() {
    int arr[] = {1, 6 , 4, 9, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout<<"Minimum value difference between Bitwise AND of sub-array and K is "<<CalcBitwiseANDClosestK(arr, n, k);
    return 0;
}

出力

Minimum value difference between Bitwise AND of sub-array and K is 1

まとめ

本記事では、配列の部分配列のビットごとのANDと整数 K の差の最小値を求める2つのアプローチを紹介しました。全探索によるシンプルな O(n²) の解法に加え、AND演算が単調非増加であるという性質を活かすことで、不要な計算を省き実用上の速度を改善できることを確認しました。ビット演算の性質を理解してアルゴリズムに応用することは、競技プログラミングや実務においても非常に有効なテクニックです。