バイナリ文字列の購入に必要な最小コイン数を求めるC++プログラム

3つの整数 c0、c1、h と2進文字列 S が与えられるとします。S 内の任意のビットを反転することができ、反転1回につき h コインを支払います。反転を何回か行った後（0回でも構いません）、その文字列を購入することになります。文字列を購入するには、すべての文字を買い取る必要があります。ビット「0」の購入には c0 コイン、「1」の購入には c1 コインが必要です。ここで、文字列の購入に必要な最小のコイン数を求めるのが問題です。

入力例と動作

たとえば、入力が c0 = 10、c1 = 100、h = 1、S = "01010" の場合を考えてみましょう。まず S の2番目と4番目のビット（「1」の部分）を反転して、2コインを支払います。これで文字列は "00000" になります。その後、この文字列を購入するのに 5 × 10 = 50 コインを支払います。したがって、支払うコインの合計は 2 + 50 = 52 となり、出力は 52 になります。

解決のための手順

この問題は貪欲法で効率よく解くことができます。各ビットについて「そのまま買う」場合と「反転してから買う」場合のコストを比較し、安い方を選べばよいのです。

• 現在のビットが「0」の場合：そのまま買うと c0 コイン、反転して「1」として買うと c1 + h コインがかかります。
• 現在のビットが「1」の場合：そのまま買うと c1 コイン、反転して「0」として買うと c0 + h コインがかかります。

この判断を文字列の先頭から順に適用し、コストを加算していきます。擬似コードは次のとおりです。

k := 0
n := 文字列 S の長さ
i := 0 から開始し、i < n の間、i を 1 ずつ増やしながら繰り返す:
    もし S[i] が '0' と同じならば:
        k := k + min(c0, c1 + h)
    そうでなければ:
        k := k + min(c0 + h, c1)
return k

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;

int solve(int c0, int c1, int h, string S) {
    int k = 0;
    int n = S.size();
    for (int i = 0; i < n; i++) {
        if (S[i] == '0')
            k = k + min(c0, c1 + h);
        else
            k = k + min(c0 + h, c1);
    }
    return k;
}

int main() {
    int c0 = 10;
    int c1 = 100;
    int h = 1;
    string S = "01010";
    cout << solve(c0, c1, h, S) << endl;
}

実行結果

入力：

10, 100, 1, "01010"

出力：

52

計算量

時間計算量：O(n)（n は文字列 S の長さ）
空間計算量：O(1)