Google Code Jam 2017 Round 1B : B. Stable Neigh-bors

これは割と面白かった。
https://code.google.com/codejam/contest/8294486/dashboard#s=p1

問題

N体のユニコーンがいる。
各ユニコーンは赤・黄・青のいずれか、もしくはそのうち2種の色を合わせた色を持つ。

計6通りの色それぞれのユニコーンの数が与えられる。
これらのユニコーンを円形に並べたい。
この時、隣同士のユニコーンが同じ色要素を持ち合わせないようにしたい。
並べ方の一例を求めよ。

解法

Small

Smallでは2種合わせた色は登場しない。
よって赤・黄・青を単に互いに同じ色が連続しないように並べるだけである。
この場合、1つの色の数が半分以下であればそのような並べ方が可能で、まず最大数の色を1つおきに並べ、以降も他の色を1つおきに並べるようにすればよい。
（1周目は1つ飛ばしでユニコーンを配置するので、2周目は飛ばしたところを埋めるように埋める）

Large

2種を合わせた色の両隣には、その補色を配置しなければならない。
すでに赤が1つ配置されている場合、その隣に黄+青、またその隣に赤、と配置すると、他の部分に影響を及ぼすことなく(黄+青)および赤を1つずつ追加することができる。

よって、まず2色混合のユニコーンと、対応する同数の補色のユニコーンを無視して考えよう。(補色のユニコーンが足りない場合、解なし)
こうするとSmallと同じ問題になるので、Smallを解き、改めて上に書いたように2色混合およびその補色を挿入すればよい。

int N,A,B,C,AB,BC,AC;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>A>>AB>>B>>BC>>C>>AC;
	
	_P("Case #%d: ",_loop);
	if(A==BC && A+BC==N) {
		FOR(i,N/2) _P("RG");
	}
	else if(B==AC && B+AC==N) {
		FOR(i,N/2) _P("YV");
	}
	else if(C==AB && C+AB==N) {
		FOR(i,N/2) _P("BO");
	}
	else {
		if(BC && A<BC+1) return _P("IMPOSSIBLE\n");
		A-=BC;
		if(AC && B<AC+1) return _P("IMPOSSIBLE\n");
		B-=AC;
		if(AB && C<AB+1) return _P("IMPOSSIBLE\n");
		C-=AB;
		
		pair<int,string> P[3];
		P[0]={A,string(A,'R')};
		P[1]={B,string(B,'Y')};
		P[2]={C,string(C,'B')};
		sort(P,P+3);
		string T=P[2].second+P[1].second+P[0].second;
		if(P[2].first>T.size()/2) return _P("IMPOSSIBLE\n");
		
		string S(A+B+C,' ');
		x=0;
		FOR(i,S.size()) {
			S[x]=T[i];
			x+=2 ;
			if(x>=S.size()) x=1;
		}
		FOR(i,S.size()) if(S[i]=='R') while(BC) BC--,S=S.substr(0,i)+"RG"+S.substr(i);
		FOR(i,S.size()) if(S[i]=='Y') while(AC) AC--,S=S.substr(0,i)+"YV"+S.substr(i);
		FOR(i,S.size()) if(S[i]=='B') while(AB) AB--,S=S.substr(0,i)+"BO"+S.substr(i);
		_P("%s",S.c_str());
	}
	
	_P("\n");
}

まとめ

シンプルな問題設定だけどなかなかトリッキーな解き方でよいね。