yukicoder : No.254 文字列の構成

これジャッジコード書くの大変そうね。
Manacherのアルゴリズム勉強しようかな。
http://yukicoder.me/problems/676

問題

整数Nが与えられる。
10^5文字以下の文字列Sのうち、以下を満たすものを１つ答えよ。

• アルファベット小文字からなる
• 隣接する文字は異なる文字である
• 部分文字列のうち回文となるものがちょうどN個ある。

解法

abababab...baという文字列を考える。
aがp個ある場合、この文字列中の回文の数f(p)はaが両端に来るケースとbが両端に来るケースでである。

よって、f(x)≦Nとなる最大のxを求め、aがx個ある文字列"ababab...ba"を解とする。
まだN-f(x)個作るべき回文が残っているので、次はf(y)≦N-f(x)となる最大のyを求め、次はcがy個ある文字列"cdcdcd...dc"を連結していく。

同様にN個回文ができるまで２文字が交互に並ぶ文字列を連結していけば良い。

int N;
int step='a';

void go(int hoge) {
	
	int i;
	FOR(i,hoge-1) _P("%c%c",step,step+1);
	_P("%c",step);
	step += 2;
	if(step>'z') step='a';
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	while(N) {
		ll a;
		for(a=1;a*(a+1)/2+(a-1)*(a)/2<=N;a++);
		a--;
		go(a);
		N -= a*(a+1)/2+(a-1)*(a)/2;
	}
	
	_P("\n");
}

まとめ

あれ、タグが書き換えられている…。