CSAcademy Round #45 : E. Palindromic Tree

実験系の問題。
https://csacademy.com/contest/round-45/task/palindromic-tree/

問題

N文字の0/1二値からなる文字列Sを考える。
S中の異なる部分文字列のうち回文の数が最少となるものを求めよ。

解法

Nが小さい範囲で総当たりしてみよう。
すると"001011"を繰り返したものが最少となっていることがわかる。
なお、回文の種類は以下の通り。

• Nが7以下ならN
• Nが8なら7
• Nが9以上なら8

以下のコードは、回答後即座にreturnしているがその後に実験したときのコードを載せてある。

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	string S="";
	while(S.size()<N) S+="001011";
	cout<<min(N,8)-(N==8)<<endl;
	cout<<S.substr(0,N)<<endl;
	return;
	
	vector<pair<int,string>> V;
	for(int mask=0;mask<1<<N;mask++) {
		if(mask>(1<<N)-mask) continue;
		string s;
		FOR(i,N) s+='0'+((mask&(1<<i))>0);
		string t=s;
		reverse(ALL(t));
		if(s>t) continue;
		set<string> S;
		for(int l=1;l<=N;l++) {
			for(x=0;x+l<=N;x++) S.insert(s.substr(x,l));
		}
		
		int ret=0;
		FORR(s,S) {
			string t=s;
			reverse(ALL(t));
			if(s==t) ret++;
		}
		V.push_back({ret,s});
	}
	sort(ALL(V));
	
	FORR(v,V) cout<<v.first<<" "<<v.second<<endl;
	
	
}

まとめ

実験系の問題は「これが最適解」と自信を持ってSubmitするの怖いな。