C++でバイナリ配列の部分配列から10進数値を求めるクエリを効率的に処理する方法

この記事では、バイナリ配列 bin[] と、それぞれ2つの値 L と R からなる Q 個のクエリが与えられたときに、各部分配列（サブ配列）に対応する10進数値を求めるクエリをC++で解くプログラムの作成方法を解説します。

問題の概要

各クエリに対して、インデックス L から R までの部分配列 subarray[L...R] が表す2進数を求め、それを10進数に変換した結果を出力する必要があります。

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

入力例

bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0}
Q = 2
2 5
0 6

出力例

2 101

解説

クエリ1の場合： 部分配列は {0, 0, 1, 0} となり、これは2進数「0010」を表します。10進数に変換すると 2 になります。

クエリ2の場合： 部分配列は {1, 1, 0, 0, 1, 0, 1} となり、これは2進数「1100101」を表します。10進数に変換すると 101 になります。

解法1：シンプルな走査による方法

最も基本的なアプローチは、インデックス L から R まで2進文字列を走査し、形成される2進数を求めてから、それを10進数に変換する方法です。各ビットに対して bit × 2^j を累積していくことで変換できます。

実装コード

#include <iostream>
#include <math.h>
using namespace std;

int CalcDecimalValue(int bin[], int L, int R) {
    int decimal = 0;
    int j = 0;
    for(int i = R; i >= L; i--){
        decimal += bin[i] * pow(2, j);
        j++;
    }
    return decimal;
}

int main() {
    int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
    int n = sizeof(bin) / sizeof(bin[0]);
    int Q = 2;
    int query[Q][2] = {{2, 5},{0, 6}};
    for(int i = 0; i < Q; i++){
        cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(bin, query[i][0], query[i][1])<<"\n";
    }
    return 0;
}

出力結果

For query 1: The decimal value of subarray is 2
For query 2: The decimal value of subarray is 101

この方法は実装が簡単ですが、クエリごとに O(R−L) の計算が必要になるため、クエリ数や配列サイズが大きい場合には非効率になる可能性があります。

解法2：前計算配列を使った効率的な方法

より効率的なアプローチとして、前計算配列を使用する方法があります。あらかじめ、各インデックス i から配列末尾 n−1 までの部分配列が表す10進数値を格納した配列を作成しておきます。こうすることで、各クエリには L と R の位置の値の差分を計算するだけで答えられます。

配列の i 番目の値は、右側（n−1）から2進→10進変換の公式を適用して次のように求められます。

decimalArray[i] = bin[i]*2^(n-1-i) + bin[i+1]*2^(n-2-i) + … + bin[n-1]*2^(0)

そして、区間 [L, R] の10進数値は、decimalArray[L] と decimalArray[R+1] の差を、右側の余分な桁に対応する 2^(n-1-R) で割ることで得られます。R が配列末尾と一致する場合は除算を省略できます。

実装コード

#include <bits/stdc++.h>
using namespace std;
int decimalArray[1000];

void createDecimalArray(int bin[], int n){
    memset(decimalArray, 0, n*sizeof(int));
    decimalArray[n - 1] = bin[n - 1] * pow(2, 0);
    for (int i = n - 2; i >= 0; i--)
        decimalArray[i] = decimalArray[i + 1] + bin[i] * (pow(2,(n - 1 - i)));
}

int CalcDecimalValue(int L, int R, int n){
    if (R != n - 1)
        return (decimalArray[L] - decimalArray[R + 1]) / (pow(2, (n - 1 - R)));
    return decimalArray[L] / (1 << (n - 1 - R));
}

int main(){
    int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
    int n = sizeof(bin) / sizeof(bin[0]);
    createDecimalArray(bin, n);
    int Q = 2;
    int query[Q][2] = {{2, 5},{0, 6}};
    for(int i = 0; i < Q; i++){
        cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(query[i][0], query[i][1], n)<<"\n";
    }
    return 0;
}

出力結果

For query 1: The decimal value of subarray is 2
For query 2: The decimal value of subarray is 101

まとめ

このように、前計算を行うことで各クエリを高速に処理できるようになります。ただし、実際の運用では部分配列が長くなると10進数値が非常に大きくなり、整数型の範囲を超える可能性がある点に注意が必要です。そのような場合は、大きな数を扱えるデータ型やモジュロ演算の導入を検討しましょう。