C++で解く！0と1の文字列における「1が優勢なセグメント」の最大長

問題文

0と1だけで構成された文字列が与えられます。この文字列を複数のセグメント（部分文字列）に分割し、各セグメントに含まれる「1」の数が「0」の数より多いようにするとき、選択できるセグメントの合計長の最大値を求めるのが課題です。

例

入力文字列が "10111000001011" の場合、答えは 12 になります。

• 第1セグメント：長さ 7（1011100）
• 第2セグメント：長さ 5（00010 を除いた残りから有効な部分を選択）
• 合計長 = 7 + 5 = 12

ポイントは、必ずしも文字列全体を使う必要はなく、「1の数が0の数を上回る」条件を満たす範囲だけを抜き出して合計することです。

アルゴリズム

この問題は再帰＋メモ化（動的計画法）で効率よく解けます。手順は以下のとおりです。

1. 開始位置 start が文字列長 n に達したら 0 を返します（ベースケース）。
2. すでに計算済みなら dp[start] の値をそのまま返します。
3. start から n までループを回し、各位置 k までの部分文字列について「1」と「0」の出現数を数えます。
4. 文字が '1' ならカウント one を、'0' なら zero をインクリメントします。
5. one > zero のときは、その区間を採用して残りを再帰的に処理します。つまり getSegmentWithMaxLength(k + 1) の結果に現在の区間長 k - start + 1 を加えた値で dp[start] を更新します。
6. 条件を満たさない場合は、区間を採用せず次のインデックス k + 1 から再帰呼び出しを行います。
7. 最後に dp[start] を返します。

C++実装例

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

int getSegmentWithMaxLength(int start, string str, int n, int dp[]) {
    if (start == n) {
        return 0;
    }
    if (dp[start] != -1) {
        return dp[start];
    }
    dp[start] = 0;
    int one = 0;
    int zero = 0;
    int k;
    for (k = start; k < n; ++k) {
        if (str[k] == '1') {
            ++one;
        } else {
            ++zero;
        }
        if (one > zero) {
            dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp) + k - start + 1);
        } else {
            dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp));
        }
    }
    return dp[start];
}

int main() {
    string str = "10111000001011";
    int n = str.size();
    int dp[n + 1];
    memset(dp, -1, sizeof(dp));
    cout << "Maximum length of segment = " << getSegmentWithMaxLength(0, str, n, dp) << endl;
    return 0;
}

コードのポイント

• dp[] 配列を -1 で初期化し、未計算の状態を管理することで、同じ開始位置の重複計算を防いでいます。
• 各区間の判定は one > zero の一つの比較だけで済むため、実装はシンプルです。
• 計算量は状態数 O(n) × 遷移 O(n) で、全体として O(n²) になります。

出力

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

Maximum length of segment = 12

まとめ

0と1の文字列から「1の数が0の数より多いセグメント」を切り出して合計長を最大化する問題は、メモ化再帰を使うことで整理して解けます。区間ごとの1と0のカウントを更新しながら「採用する／しない」を比較するシンプルなDP構造なので、部分和や区間分割系の問題全般にも応用できる考え方です。