Codeforces #559 Div1 B. The minimal unique substring

こういう考察系しんどいな。
https://codeforces.com/contest/1158/problem/B

問題

N文字の01からなる文字列のうち、部分列として登場する頻度が1となる文字列のうち最短の長さがKになるものを構築せよ。
なお、NとKの偶奇は一致する。

解法

これは実験ゲーかな…。

基本的に0を並べるが((N-K)/2+1)個ごとに1を置く。
例えばN=13, K=5のときは以下のようになる。

0000100001000
コメント部は実験したときのコード。
int N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	int step=0;
	FOR(i,N) {
		step++;
		if(step%((N-K+2)/2)==0) cout<<1;
		else cout<<0;
	}
	cout<<endl;
	
	/*
	if(N==K) {
		FOR(i,N) cout<<1;
		cout<<endl;
		return;
	}
	int mask=0;
	y=10;
	vector<string> C[33];
	FOR(mask,1<<y) {
		string S;
		map<string,int> V;
		FOR(i,y) S.push_back('0'+((mask>>i)&1));
		FOR(x,y) for(l=1;x+l<=y;l++) V[S.substr(x,l)]++;
		
		x=y;
		FORR(v,V) if(v.second==1) x=min(x,(int)v.first.size());
		C[x].push_back(S);
	}
	
	for(i=1;i<=y;i++) if(i%2==y%2) {
		cout<<i<<"--------------"<<endl;
		FORR(c,C[i]) cout<<" "<<c<<endl;
	}
	*/
	
	
}


    
まとめ
    実験ゲーってどう効率よく解けばいいんだろうな…。