题目 https://atcoder.jp/contests/abc124/tasks/abc124_d?lang=en

大意：一队人站成一排，所有人不是正立就是倒立，用一个长度等于这队人数的01串表示它们的队。下标为i的字符若为0则表示正立的，为1表示倒立着的人。你可以发K次指令，每次指令是使[l,r]的人状态反过来（正立改倒立，倒立变正立），试求当这样做K次之后，队伍中最多有连续几人处在相同的状态（正立/倒立）

指示を一度行うたびに、人の状態が切り替わる部分を 2 箇所まで潰すことができます。これを踏まえて、連 続して 1 を並ばせる左端を i 番目としたときにいくつ 1 を並べることができるかを考えます。

• S_i = 0 のとき: i 番目以降で S_j != S_j+1 となる場所を順に最大 2K − 1 箇所潰すのが最適です。

• S_i = 1 のとき: i 番目以降で S_j  != S_j+1 となる場所を順に最大 2K 箇所潰すのが最適です。 1 を並べる左端を i としたときの最大値を X_i とすると、答えは max{X₁, X₂, …, X_N } となります。

しかし、 これをナイーブに実装しても O(N^2 ) となり間に合いません。 そこで、何かしら工夫する必要があります。まず、i (連続して 1 を並ばせる左端) として、元の文字列で 0 または 1 が連続する始点のみを探索すれば十分です。例えば、”11000…” の 4 文字目や 5 文字目の 0 を左端と するよりも 3 文字目の 0 を左端とした方が良いでしょう。このような場所を左から順に 1 = i₁ < i₂ < … < i_r とします。また、便宜上 k > r なる k について、i_k = N + 1 とします。このとき、k = 2, 3, …, r について、 S_i,k = S_i,k−1 です。よって、k = 1, 2, …, r について、X_i,k は

• S_i,k = 0 のとき: X_i,k = i_k+2K − i_k

• S_i,k = 1 のとき: X_i,k = i_k+2K+1 − i_k となり、答えは max{X_i,1 , X_i,2 , …, X_i,r } です。これは、O(N) で動作します。 別解として、二分探索を使った O(NlogN) の解法や、しゃくとり法を用いた O(N) の解法もあります。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin >> n >> k;
    string S;
    cin >> S;
    int res = 0;
    int l = 0;
    int cnt = 0;
    for(int r = 0;r < n; r++){
		if(S[r]=='0'){
			if(r==0 || S[r-1]=='1') cnt++;
		}
		if(cnt > k){
			while(l < S.size() && S[l]=='1') l++;
			while(l < S.size() && S[l]=='0') l++;
			cnt--;
		}
		res=max(res,r-l+1);
	}
    cout << res << endl;
    return 0;
}