EasyというけどDiv1 Mediumとどっちが難しいだろうな。
https://community.topcoder.com/stat?c=problem_statement&pm=15270
問題
abで構築される100文字以下の文字列のうち、部分文字列列が回文となるものがn個であるようなものを構築せよ。
なお、部分文字列自体が同一でも抜き出した位置が異なるものは別々にカウントする。
解法
「aa...ab....ba....ab...b」のようにa,bの連続列を最大2セットまで繰り返すうちに1~1000となるケースは1度は登場する。
よってそれぞれのa,bの登場回数を総当たりしてしまおう。
class FindStringEasy { public: string withPalindromicSubstrings(int n) { for(int a1=0;a1<=100;a1++) { for(int b1=0;a1+b1<=100;b1++) { int v=a1*(a1+1)/2+b1*(b1+1)/2; string S=string(a1,'a')+string(b1,'b'); if(v==n) return S; if(a1==0 || b1==0) continue; for(int a2=1;a1+a2+b1<=100;a2++) { for(int b2=0;a1+a2+b1+b2<=100;b2++) { int v=(a1*(a1+1)+b1*(b1+1)+a2*(a2+1)+b2*(b2+1))/2+min(a1,a2)+min(b1,b2); if(v==n) { return S+string(a2,'a')+string(b2,'b'); } } } } } return ""; } }
まとめ
これ想定解なんなんだろう。