C++でバイナリ行列内の最大ビット差を持つ行のペアを見つける方法

バイナリ行列（0と1のみで構成される行列）が与えられたとき、その中からビット差が最大となる2つの行のペアを見つける問題を考えてみましょう。

例えば、次のような行列が入力された場合を想定します。

{1, 1, 1, 1},
{1, 0, 1, 1},
{0, 1, 0, 0},
{1, 0, 0, 0}

この場合、出力は (2, 3) となります。なぜなら、2行目と3行目のビット差は4であり、これがすべての行の組み合わせの中で最大だからです。

解決策：Trie（トライ木）を使った効率的なアプローチ

この問題は、各行をビット列として扱い、Trie（トライ木）というデータ構造を利用することで効率的に解くことができます。全ての行のペアを総当たりで比較するO(n²×m)の方法に比べ、Trieを使うと探索を高速化できます。

アルゴリズムの手順

• TrieNode構造体を定義します。各ノードは「leaf（行番号を格納）」と「child[2]（0と1に対応する2つの子ノード）」を持ちます。

• get_max_bit_diff() 関数を定義します。引数としてTrieのルート、行列、列数n、対象となる行インデックスを受け取ります。

この関数の内部処理は以下の通りです。

1. 一時ポインタ temp をルートに設定し、カウンタ count を0で初期化します。

2. i = 0 から n-1 までループし、現在の行の各ビットについて処理を行います。

   • もし temp の子ノード child[matrix[row_index][i]] が存在すれば、その子へ移動します（同じビット＝差分なし）。

   • 存在しない場合は、逆のビットに対応する子ノード child[1 - matrix[row_index][i]] へ移動し、count を1増やします（異なるビット＝差分あり）。

3. 到達した葉ノードの leaf の値を leaf_index として記録します。

4. 次に、temp_count を0に初期化して temp をルートに戻し、今度は可能な限り逆のビットを選ぶようにもう一度走査します。

   • child[1 - matrix[row_index][i]] が存在すればそちらへ移動し、temp_count を増やします。

   • 存在しなければ child[matrix[row_index][i]] へ移動します。

5. temp_count が count より大きければ (temp_count, temp->leaf) のペアを、そうでなければ (count, leaf_index) のペアを結果 P として返します。

メイン関数での処理の流れ

1. 新しい TrieNode をルートとして作成します。

2. 0行目をTrieに挿入します。

3. max_bit_diff を INT_MIN（最小値）で初期化します。

4. i = 1 から n-1 までループします。

   • get_max_bit_diff() を呼び出し、既存の行との最大ビット差を取得します。

   • 取得した値が max_bit_diff より大きければ、max_bit_diff を更新し、答えのペア pr を (temp.second, i + 1) として保存します。

   • その後、i 行目をTrieに挿入します。

5. 最後にペア pr を表示します。

C++による実装例

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

#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
class TrieNode {
    public:
    int leaf;
    TrieNode *child[2];
    TrieNode(){
        leaf = 0;
        child[0] = child[1] = NULL;
    }
};
void insert(TrieNode *root, int matrix[][MAX], int n, int row_index){
    TrieNode * temp = root;
    for (int i=0; i<n; i++) {
        if(temp->child[ matrix[row_index][i] ] == NULL)
            temp->child[ matrix[row_index][i] ] = new TrieNode();
        temp = temp->child[ matrix[row_index][i] ];
    }
    temp->leaf = row_index +1 ;
}
pair<int, int>get_max_bit_diff(TrieNode * root, int matrix[][MAX], int n, int row_index) {
    TrieNode * temp = root;
    int count = 0;
    for (int i= 0 ; i < n ; i++) {
        if (temp->child[ matrix[row_index][i] ] != NULL)
            temp = temp->child[ matrix[row_index][i] ];
        else if (temp->child[1 - matrix[row_index][i]] != NULL) {
            temp = temp->child[1- matrix[row_index][i]];
            count++;
        }
    }
    int leaf_index = temp->leaf;
    int temp_count = 0 ;
    temp = root;
    for (int i= 0 ; i < n ; i++) {
        if (temp->child[ 1 - matrix[row_index][i] ] !=NULL) {
            temp = temp->child[ 1- matrix[row_index][i] ];
            temp_count++;
        }
        else if (temp->child[ matrix[row_index][i] ] != NULL)
            temp = temp->child[ matrix[row_index][i] ];
    }
    pair <int ,int> P = temp_count > count ? make_pair(temp_count, temp->leaf): make_pair(count, leaf_index);
    return P;
}
void get_max_diff( int mat[][MAX], int n, int m) {
    TrieNode * root = new TrieNode();
    insert(root, mat, m, 0);
    int max_bit_diff = INT_MIN;
    pair<int ,int> pr, temp ;
    for (int i = 1 ; i < n; i++) {
        temp = get_max_bit_diff(root, mat, m ,i);
        if (max_bit_diff < temp.first ) {
            max_bit_diff = temp.first;
            pr = make_pair( temp.second, i+1);
        }
        insert(root, mat, m, i );
    }
    cout << "(" << pr.first <<", "<< pr.second << ")";
}
int main() {
    int mat[][MAX] = {
        {1 ,1 ,1 ,1 },
        {1, 0, 1 ,1},
        {0 ,1 ,0 ,0},
        {1 ,0 ,0 ,0}
    };
    get_max_diff(mat, 4, 4) ;
}

入力

{{1, 1, 1, 1},
{1, 0, 1, 1},
{0, 1, 0, 0},
{1, 0, 0, 0}}, 4, 4

出力

(2,3)

まとめ

このアルゴリズムでは、Trieに挿入済みの行と現在の行を比較することで、各ステップで「同じビットを優先的に辿る経路」と「逆のビットを優先的に辿る経路」の2通りを評価し、より大きなビット差を採用しています。これにより、総当たり方式よりも効率的に最大ビット差を持つ行のペアを特定できます。