Codeforces #668 Div1 A. Balanced Bitstring

自分は本番解けきってないけど、D,Eが普段より簡単だったっぽい回。
https://codeforces.com/contest/1404/problem/A

問題

0/1で構成された文字列を考える。
この文字列がK-balancedであるとは、K文字の部分文字列を抜き出すと、0と1の登場頻度が常に等しいことを示す。

Kと0/1/?で構成された文字列Sが与えられる。
?に0か1を任意で埋めたとき、SをK-balancedにできるか。

解法

S[i,i+K-1]もS[i+1,i+K]もK-balancedであるためには、S[i]=S[i+K]でなければならない。
これにより、?の中身が確定できる箇所は埋めてしまおう。
またS[i]!=S[i+K]な箇所が生じる場合、K-balancedにできない。

上記で問題ない場合、累積和を使って、K文字の部分文字列を総当たりし、0または1の登場回数がK/2を超えないことを確認しよう。
そうすれば、?の中身を具体的に埋める必要はない。

int T;
int K,N;
string S;
int sum[303030][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K>>S;
		int ng=0;
		FOR(i,K) {
			int C[2]={};
			for(j=i;j<N;j+=K) {
				if(S[j]=='0') C[0]++;
				if(S[j]=='1') C[1]++;
			}
			if(C[0]&&C[1]) {
				ng=1;
			}
			else if(C[0]) {
				for(j=i;j<N;j+=K) S[j]='0';
			}
			else if(C[1]) {
				for(j=i;j<N;j+=K) S[j]='1';
			}
		}
		FOR(i,N) {
			sum[i+1][0]=sum[i][0];
			sum[i+1][1]=sum[i][1];
			if(S[i]=='0') sum[i+1][0]++;
			if(S[i]=='1') sum[i+1][1]++;
		}
		for(i=0;i+K<=N;i++) {
			int a=sum[i+K][0]-sum[i][0];
			int b=sum[i+K][1]-sum[i][1];
			if(a>K/2||b>K/2) ng=1;
		}
		if(ng) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
		
		
	}

}

まとめ

ここらへんはまだ簡単。