TechFUL: Improving Binary

問題概要

バイナリ文字列 が与えられる．

文字列の良さとは、1 が連続して並んでいる区間の長さの最大値である．

以下の操作を 回まで行える．

• の文字が 0 である箇所を 1 つ選び、1 に変える．

適切に操作したときの文字列の良さの最大値を求めよ．

問題のリンク

制約

• は 0 または 1 からなる文字列

• 

• 

解法1: 二分探索

について、位置 を始点に右に 1 ができるだけ長く連なるように操作を行う．

最初に文字 0 が現れる位置を とする．

このとき、 が答えである．

例として、S = 001001011, K = 2 の場合をみると

• 位置 0 を始点とした場合、S = 001001011 の位置 0, 1 の 0 を 1 に変えれば、
  S = 111001011 となり、 となる．

• 位置 1 を始点とした場合、S = 001001011 の位置 1, 3 の 0 を 1 に変えれば、
  S = 011101011 となり、 となる．

• 位置 2 を始点とした場合、S = 001001011 の位置 3, 4 の 0 を 1 に変えれば、
  S = 001111011 となり、 となる．

次に の計算であるが、 これは に文字 0 がいくつ存在するか数える配列 を事前に計算しておけば、 二分探索を使用して 時間でできる．

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

string S;
int K;
int cnt[100010];

int main() {
    cin >> S >> K;

    for (int i = 0; i < S.size(); ++i) {
        cnt[i + 1] = cnt[i] + (S[i] == '0');
    }

    int ans = 0;
    for (int i = 0; i < S.size(); ++i) {
        int ok = i, ng = S.size() + 1;
        while (ng - ok > 1) {
            int m = (ok + ng) / 2;
            if (cnt[m] - cnt[i] <= K) ok = m;
            else ng = m;
        }
        ans = max(ans, ok - i);
    }
    cout << ans << endl;
}

解法2: しゃくとり法

上の の値は において が成り立つ．

そのため、 はしゃくとり法を使って全体で 時間で計算できる．

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

string S;
int K;
int cnt[100010];

int main() {
    cin >> S >> K;

    for (int i = 0; i < S.size(); ++i) {
        cnt[i + 1] = cnt[i] + (S[i] == '0');
    }

    int ans = 0, j = 0;
    for (int i = 0; i < S.size(); ++i) {
        while (j <= S.size() && cnt[j] - cnt[i] <= K) {
            j++;
        }
        ans = max(ans, j - 1 - i);
    }
    cout << ans << endl;
}