TopCoder SRM 746 Div1 Medium FindStringHard

しょうもないコーナーケース漏れで落とすのもったいないね。
https://community.topcoder.com/stat?c=problem_statement&pm=15273

問題

文字列Sがanti回文であるとは、Sを反転したS'に対し、SとS'の文字が一致する箇所が一度もないものを示す。

整数nが与えられる。
'a''b'で構成される100文字以下の文字列のうち、anti回文となる部分文字列n個であるようなものを構築せよ。
なお、部分文字列自体が同一でも抜き出した位置が異なるものは別々にカウントする。

解法

基本アプローチはabab..abaとabを繰り返すことである。
(ab)*k+aという文字列を作ると、k*(k+1)個のanti回文となる文字列が生成できる。

そこで、合計がn個に達するまで(ab)*k+aの組み合わせを連結していこう。
連結の境目は"aa"となるが、この構築法で"bb"は登場しないので境目により想定外のanti回文が生成されることはない。

なお、1回あたりk*(k+1)個のanti回文ができるということは、常に偶数通りのanti回文が生成されるため、nに達するために1個足りない場合がある。
その時は最後に"ab"をつけよう。
n=0のコーナーケースに注意。

class FindStringHard {
	public:
	string withAntipalindromicSubstrings(int n) {
		int i;
		string S="";
		if(n==0) return "a";
		int x;
		for(i=50;i>=1;i--) {
			while(i*(i+1)<=n) {
				FOR(x,i) S+="ab";
				S+="a";
				n-=i*(i+1);
			}
		}
		if(n) S+="ab";
		return S;
		
	}
}

まとめ

本番n=1～1000までちゃんとチェックしたのに…。