実験系の問題。
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するの怖いな。