AtCoder AGC #001 : D - Arrays and Palindrome

あと数分で解けたのに時間切れで残念。
http://agc001.contest.atcoder.jp/tasks/agc001_d

問題

2つの数列A,Bがある。
それぞれの総和はNで等しい。

あるN文字の文字列があったとき、先頭A[0]文字、続くA[1]文字…は順に回文を成している。
同様に先頭B[0]文字、続くB[1]文字…は順に回文を成している。

ここで、入力としてAを並べ替えたものが与えられる。
適切なA,Bを選択したとき、N文字の文字列の全部の文字が等しいことが保証できるようにできるか。
出来るならA,Bの例を示せ。

解法

x文字の回文があると、floor(x/2)個の文字対がそれぞれ等しいことになる。
N文字全体が等しくなるためには、Union-findの要領で考えると最低(N-1)個の文字対が等しくなければならない。

数列Aより、等しい文字対の個数はfloor(A[0]/2)+floor(A[1]/2)+... = floor(N/2) - odd(A)/2 (odd(A)はA中の奇数の要素数)個となる。
仮にBを奇数が1個以下になるようにしたとき、等しい文字対の個数はfloor(N/2)個である。

Aのうち奇数個の要素が３個以上あるとき、Bと合わせてこれらで(N-1)個の文字対を作れないので解はない。
それ以外の時は、入力値のうち奇数の値を両端に持って行くとよい。
対応するBは、Aの先頭と末尾を1小さくし、B[0]の次にB[1]=2を挿入すると条件を満たせる。
(先頭と末尾以外はA[i]とB[i+1]の長さは同じで、始まりの位置は1ずれた状態になるが、そうするとこれらの値に相当する領域が全て等しくなることがわかる。)

例えばこんな感じ。小文字のアルファベットはA[i]やB[i]の大きさ分並べてある。

A={5,2,6,4,3}
B={4,2,2,6,4,2}
aaaaabbccccccddddeee
aaaaxxbbccccccddddee

int N,M,NE;
vector<int> O;
vector<int> E;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x;
		if(x%2==1) O.push_back(x);
		else E.push_back(x);
	}
	
	if(O.size()>2) return _P("Impossible\n");
	NE=E.size();
	sort(ALL(E));
	reverse(ALL(E));
	
	if(O.size()==2) {
		_P("%d",O[0]);
		FOR(i,NE) _P(" %d",E[i]);
		_P(" %d\n",O[1]);
		
		x = NE+1+2;
		if(O[0]==1) x--;
		if(O[1]==1) x--;
		
		_P("%d\n",x);
		if(O[0]>1) _P("%d ",O[0]-1);
		_P("2 ");
		FOR(i,NE) _P("%d ",E[i]);
		if(O[1]>1) _P(" %d",O[1]-1);
		_P("\n");
	}
	else if(O.size()==1) {
		_P("%d",O[0]);
		FOR(i,NE) _P(" %d",E[i]);
		_P("\n");
		
		
		x = NE+1+1;
		if(O[0]==1) x--;
		
		_P("%d\n",x);
		if(O[0]>1) _P("%d ",O[0]-1);
		
		if(NE) {
			_P("2");
			FOR(i,NE-1) _P(" %d",E[i]);
			
			_P(" %d\n",E[NE-1]-1);
		}
		else {
			_P("1\n");
		}
		
	}
	else {
		FOR(i,NE) _P("%d%c",E[i],(i==NE-1)?'\n':' ');
		_P("%d\n",NE+1);
		_P("1");
		FOR(i,NE-1) _P(" %d",E[i]);
		_P(" %d\n",E[NE-1]-1);
	}
}

まとめ

惜しかったなぁ…。