C++で生成した文字列Tの最小アンバランス度を求める方法

問題の概要

文字列Sが与えられます。Sの各文字は「0」「1」または「?」のいずれかです。それぞれの「?」を0または1に置き換えることで、新しい文字列Tを作成することを考えます。Tのアンバランス度とは、0 ≤ l ≤ r < |S| を満たすすべての区間 [l, r] について、その範囲内に出現する0の個数と1の個数の差の絶対値を計算し、その中の最大値を取ったものです。ここで、Tのアンバランス度としてあり得る最小値を求めることが目標です。

例えば、入力が S = "0??0" の場合、出力は 2 になります。

解法のアプローチ

この問題は、二分探索と貪欲法を組み合わせることで効率的に解くことができます。まず、与えられた上限 x 以内で文字列を構築できるかどうかを判定する関数 check() を定義します。この関数では、読み込んだ位置までの「0と1の個数差」が取りうる範囲を、下限 L と上限 R のペアで管理します。「0」が出現すれば L と R をともに1減らし、「1」が出現すればともに1増やし、「?」が出現すれば取りうる範囲を広げます。その際、範囲が上限 x+1 や下限 -1 を超えないよう適宜調整を行い、もし L が R を追い越したらその x では構築不可能として false を返します。メイン処理では、x の候補に対して二分探索を行い、check() が true になる最小の x を求めます。

関数 check() を定義する。引数は S と x
L := 0, R := x
B := true
i := 0 から S のサイズ未満の間、i を1ずつ増やしながら繰り返す:
    もし S[i] が '0' ならば:
        L と R をそれぞれ1減らす
    もし S[i] が '1' ならば:
        L と R をそれぞれ1増やす
    もし S[i] が '?' ならば:
        もし L が R と等しいならば:
            B := false
            L を1減らす
            R を1増やす
    もし R が x + 1 と等しいならば:
        もし B が真ならば:
            R を1減らす
        そうでなければ:
            R := R - 2
    もし L が 0 未満ならば:
        もし B が真ならば:
            L を1増やす
        そうでなければ:
            L := L + 2
    もし L > R ならば:
        false を返す
true を返す

メイン処理では以下を実行する
L := 1, R := 1000000
L <= R である間、繰り返す:
    Mid := (L + R) / 2 の小数点以下切り捨て
    もし check(S, Mid) が真ならば:
        R := Mid - 1
    そうでなければ:
        L := Mid + 1
R + 1 を返す

実装例

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

#include <bits/stdc++.h>
using namespace std;
bool check(string S, int x) {
    int L = 0, R = x;
    bool B = true;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == '0')
            L--, R--;
        if (S[i] == '1')
            L++, R++;
        if (S[i] == '?') {
            if (L == R)
                B = false;
            L--;
            R++;
        }
        if (R == x + 1) {
            if (B)
                R--;
            else
                R -= 2;
        }
        if (L < 0) {
            if (B)
                L++;
            else
                L += 2;
        }
        if (L > R)
            return false;
    }
    return true;
}
int solve(string S) {
    int L = 1, R = 1000000;
    while (L <= R) {
        int Mid = L + R >> 1;
        if (check(S, Mid))
            R = Mid - 1;
        else
            L = Mid + 1;
    }
    return R + 1;
}
int main() {
    string S = "0??0";
    cout << solve(S) << endl;
}

入力

0??0

出力

2

動作のポイント

S = "0??0" の場合、Tとして作れる文字列は "0000"、"0010"、"0100"、"0110" の4通りです。"0000" では文字列全体に0が4個含まれるためアンバランス度は4になってしまいますが、"0010" や "0110" などでは、どの区間を取り出しても0と1の個数差は最大2に収まります。したがって、この入力に対する最小のアンバランス度は2となります。