Codeforces #339 Div1. C. Necklace

今回のCFではこれが一番おもしろかったかな。
http://codeforces.com/contest/613/problem/C

問題

N種類のアルファベットそれぞれA[i]個ずつを円周上に並べることを考える。
円周のどこかを１つ切断して出来る文字列が回文となるようにしたい。

回文を生成できる切断箇所が最も多くなるアルファベットの並び順を１つ生成せよ。

解法

回文を生成するには、奇数個登場する文字は１個以下でなければならない。
そこで奇数個登場する文字が２個以上ある場合、回文は生成できない(そのため、条件を満たす切断箇所は0個として適当な文字列を返す)。

奇数個登場する文字が1個の場合

A[i]の最大公約数をgとする。
各文字をA[i]/g個ずつ使う回文をg個連結すれば、g箇所で切断後回文を生成可能な並びができる。
例：a,b,cの登場回数が3,6,12の場合、[ccbabcc][ccbabcc][ccbabcc]では、各括弧の境界3箇所のどこで切っても回文を生成できる。

奇数個登場する文字が0個の場合

A[i]/2の最大公約数をgとする。
まず各文字をA[i]/2/g個適当に並べ、次にそれらを逆順にしたものを連結する。
その全体をg回繰り返すと、2*g箇所の切断で回文を生成できる。
例：a,b,cの登場回数が6,6,12の場合、[abcc][ccba][abcc][ccba][abcc][ccba]とすると、各括弧の境界6箇所のどこで切っても回文を生成できる。

int N;
int A[30];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int odd=0, oid=0, g=0;
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		g=__gcd(g,A[i]);
		if(A[i]%2==1) odd++, oid=i;
	}
	
	if(odd>1) {
		_P("0\n");
		FOR(i,N) FOR(j,A[i]) _P("%c",'a'+i);
	}
	else {
		_P("%d\n",g);
		FOR(i,N) A[i]/=g;
		if(odd) {
			FOR(x,g) {
				FOR(i,N) if(i!=oid) FOR(j,A[i]/2) _P("%c",'a'+i);
				FOR(j,A[oid]) _P("%c",'a'+oid);
				for(i=N-1;i>=0;i--) if(i!=oid) FOR(j,A[i]/2) _P("%c",'a'+i);
			}
		}
		else {
			FOR(x,g) {
				if(x%2==0) {
					FOR(i,N) FOR(j,A[i]) _P("%c",'a'+i);
				}
				else {
					for(i=N-1;i>=0;i--) FOR(j,A[i]) _P("%c",'a'+i);
				}
			}
		}
	}
	_P("\n");
}

まとめ

ネックレスが２か所以上で切れる必要ありますかね…。