C++でバイナリ文字列Sを作るために必要な最小操作回数を求める方法

問題の概要

バイナリ文字列 str が与えられます。この文字列が表す数値を作り出すために必要な操作の最小回数を求めてください。実行できる操作は次の2種類のみです。

• 2^x を加算する
• 2^x を減算する

例えば、バイナリ文字列が「1000」の場合、必要な操作は「2³ を加算する」のたった1回だけです。

一方、バイナリ文字列が「101」の場合は、「2² を加算する」と「2⁰ を加算する」の計2回の操作が必要になります。

解法のポイント

一見すると、文字列に含まれる「1」の個数がそのまま答えのように思えるかもしれません。しかし、減算という操作を活用することで、より少ない操作回数で目的の数を作れるケースがあります。

例えば「111」(10進数で7)の場合、単純に足し算だけで表現すると 2² + 2¹ + 2⁰ の3回の操作が必要です。しかし、「2³(=8)を加算してから 2⁰(=1)を減算する」という2回の操作でも同じ数を作れます。このように、途中で繰り上げ(桁上がり)を考慮しながら最適な選択をしていくことが重要になります。

動的計画法(DP)によるアプローチ

この問題は、各桁ごとに次の2つの状態を持つ動的計画法で効率的に解けます。

• result[i][0]:下位 i+1 桁を処理したとき、現在の桁を「そのまま」扱う場合の最小操作回数
• result[i][1]:下位 i+1 桁を処理したとき、現在の桁を「1つ繰り上げて(値を1増やして)」扱う場合の最小操作回数

まず文字列を反転し、インデックス i が 2ⁱ の位に対応するようにします。そして各桁の値に応じて、以下のように遷移を行います。

• 現在の桁が「0」の場合:
  ・result[i][0] = result[i-1][0](そのまま引き継ぐ)
  ・result[i][1] = 1 + min(result[i-1][0], result[i-1][1])(繰り上げには1回の操作が追加)
• 現在の桁が「1」の場合:
  ・result[i][1] = result[i-1][1](そのまま引き継ぐ)
  ・result[i][0] = 1 + min(result[i-1][0], result[i-1][1])

最終的な答えは result[n-1][0]、つまり最上位桁まで処理して繰り上げを確定させない場合の値となります。

C++での実装例

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int getMinOperations(string s){
    reverse(s.begin(), s.end());
    int n = s.length();
    int result[n + 1][2];

    if (s[0] == '0') {
        result[0][0] = 0;
    } else {
        result[0][0] = 1;
    }
    result[0][1] = 1;

    for (int i = 1; i < n; ++i) {
        if (s[i] == '0') {
            result[i][0] = result[i - 1][0];
            result[i][1] = 1 + min(result[i - 1][1],
                                   result[i - 1][0]);
        } else {
            result[i][1] = result[i - 1][1];
            result[i][0] = 1 + min(result[i - 1][0],
                                   result[i - 1][1]);
        }
    }
    return result[n - 1][0];
}

int main(){
    string str = "101";
    cout << "Minimum required operations = " << getMinOperations(str) << endl;
    return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum required operations = 2

コードの解説

プログラムの流れを簡単に整理すると、次のようになります。

1. 文字列の反転:reverse 関数で文字列を逆順にし、インデックスと2のべき乗の位を対応させます。
2. 初期化:最下位桁(反転後の s[0])の状態を設定します。「0」なら操作不要で0、「1」なら加算1回で1。繰り上げ状態は常に初期コスト1です。
3. DP遷移:各桁について「そのまま扱う」「繰り上げて扱う」の2状態のコストを更新していきます。
4. 答えの出力:最上位桁まで処理した後の result[n-1][0] が最小操作回数となります。

このアルゴリズムの計算量は文字列の長さを n とすると O(n)、空間計算量も O(n) であり、非常に効率的です。減算操作を許容することで、連続する「1」の並びを1回の加算と1回の減算で置き換えられる点が、この問題の本質的な面白さといえます。