ABC124 D - Handstand

D - Handstand

方針

反転する区間は0が続いている区間のみを考えてよい。
すると問題は、0が続いている区間をK区間ずつ1に反転していって、1が連続する区間が最大になるものを求めればよい。

これは尺取り法でO(N+K)で求めることが出来る。

感想

下記ブログを参考にしました。
drken1215.hatenablog.com

解答

Submission #5002729 - AtCoder Beginner Contest 124

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, K;
	cin >> N >> K;
 
	string S;
	cin >> S;
 
	vector<int> v;
	if(S[0] == '0'){
		v.push_back(0);
	}
 
	int cnt = 0;
	bool zero = S[0] == '0';
 
	for(int i = 0; i < N; i++){
		if(zero){
			if(S[i] == '0'){
				cnt++;
			}else{
				v.push_back(cnt);
				zero = false;
				cnt = 1;
			}
		}else{
			if(S[i] == '1'){
				cnt++;
			}else{
				v.push_back(cnt);
				zero = true;
				cnt = 1;
			}
		}
	}
 
	v.push_back(cnt);
	if(S[N-1] == '0'){
		v.push_back(0);
	}
 
	// rep(i, v.size()) cout << v[i] << ",";
	// cout << endl;
 
	if(v.size() <= 2 * K + 1){
		cout << N << endl;
		return 0;
	}
 
	int tmp = 0;
	for(int i = 0; i < 2 * K + 1; i++){
		tmp += v[i];
	}
 
	int ans = 0;
	ans = max(ans, tmp);
 
	for(int i = 0; 2 * i + 2 * K + 2 < v.size(); i++){
		tmp += v[2 * i + 2 * K + 1] + v[2 * i + 2 * K + 2];
		tmp -= v[2 * i] + v[2* i + 1];
		ans = max(ans, tmp);
	}
 
	cout << ans << endl;
}