Handstand [AtCoder Beginner Contest 124 D]

https://atcoder.jp/contests/abc124/tasks/abc124_d

前提知識

• 尺取法

解説

https://atcoder.jp/contests/abc124/submissions/4966633

まず、気づくべき性質として
「ある区間を全て1にするには、その区間に含まれる0のグループの個数分の支持回数が必要になる」
ということ。
　
つまり、この問題は、区間に含まれる0のグループがK以下である区間の最大長を求める問題となる。
これは尺取法で解いていこう。
区間の右を全探索し、右を伸ばしていくと、0のグループが増えていくので、Kを超えたら、
左側の右に動かしてKを減らすということを繰り返す。
この際にグループの扱いが少し面倒なので、先にランレングス表現しておこう。

int N, K; string S;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K >> S;
 
	auto blocks = runLengthEncoding(S);
	int M = blocks.size();
	int ans = 0;
	int sm = 0;
	int L = 0;
	int zero = 0;
	rep(R, 0, M) {
		sm += blocks[R].second;
		if (blocks[R].first == '0') zero++;
 
		while (K < zero) {
			sm -= blocks[L].second;
			if (blocks[L].first == '0') zero--;
			L++;
		}
 
		chmax(ans, sm);
	}
	cout << ans << endl;
}