Codeforces #777 : Div2 F. Juju and Binary String

ボス問だがとてもコードが短い。
https://codeforces.com/contest/1658/problem/F

問題

01で構成される文字列に対し、cutenessとは1の占める割合と定義する。

N文字の01で構成される文字列Sと、正整数Mが指定される。

Sの互いに交差しない連続部分列をいくつか抽出することを考える。この時以下を満たしたい。

• 各連続部分列におけるcutenessは、Sのcutenessと等しい。
• 総長はMである。
• できるだけ少ない連続部分列で達成したい。

条件を満たす連続部分列があればそれを答えよ。

解法

Sを繰り返した文字列において、1つの連続部分列でこれを満たせることが証明できる。
よって始点を総当たりしてcutenessが一致するM文字の連続部分文字列を探せばよい。

int T,N,M;
string S;
int A[404040];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>S;
		ll C1=count(ALL(S),'1');
		if(C1*M%N) {
			cout<<-1<<endl;
			continue;
		}
		C1=C1*M/N;
		FOR(i,2*N) A[i+1]=A[i]+(S[i%N]-'0');
		
		FOR(i,N) if(A[i+M]-A[i]==C1) {
			if(i+M<=N) {
				cout<<1<<endl;
				cout<<(i+1)<<" "<<(i+M)<<endl;
			}
			else {
				cout<<2<<endl;
				cout<<1<<" "<<(i+M)%N<<endl;
				cout<<(i+1)<<" "<<N<<endl;
			}
			break;
		}
		
		
		
	}
}

まとめ

考察が難しくて実装が簡単なタイプの問題。