Google Code Jam 2011 Round 1B : C. House of Kittens

これも昨年解き残していたので復習。
本番でsmallは全数列挙で通したけど、largeは解けていなかったので。
http://code.google.com/codejam/contest/1150485/dashboard#s=p2

凸のN角形中に、交差しない複数の対角線を引っ張ったとき、辺の両端の点が異なる色を持ち、かつ対角線で分割された各図形内の各頂点が、全部の色を網羅するよう色分けする。
このような色分けの最多色数と、色分けの例を示す問題。

解法

対角線で図形を分けたとき、もっとも少ない頂点数の図形がM角形とすると、色の数はMとなる。
なので、まずM角形を１つ選んで1～Mの色を割り当てる。

あとは、色を割り当てた図形と辺を共有する図形を選び、色を割り当てていく。
新しく色を割り当てる図形は、共有する編の両端の２色以外は自由に決められるので、この２色以外を優先的に割り当てる。

以上を再帰的に繰りかえればよい。
ある面の色を考える際、２点以上の色が確定されていることは無いので、色の割り当ては大雑把でよい。
O(N)かO(N logN)ぐらいかな？

int N,M;
vector< vector<int> > P;
int U[2001],V[2001];
int VM[2001][2001];
int COL[2001];
int done[2001];
int mc;

void split(int l,int u,int v) {
	vector<int> V[2];
	int i,s;
	
	s=0;
	FOR(i,P[l].size()) {
		if(P[l][i]==u || P[l][i]==v) {
			V[0].push_back(P[l][i]);
			V[1].push_back(P[l][i]);
			s=1-s;
		}
		else {
			V[s].push_back(P[l][i]);
		}
	}
	P[l]=V[0];
	P.push_back(V[1]);
}

void setcol(int F,int v1,int v2) {
	int sv,t;
	int c1,c2,c,pv1,pv2;
	
	
	//_P("%d :",F);
	FOR(sv,P[F].size()) {
		//_P("%d ",P[F][sv]);
		if(P[F][sv]==v1) pv1=sv;
		if(P[F][sv]==v2) pv2=sv;
	}
	//_P("\n");
	if((pv2+1)%P[F].size()==pv1) {
		t=pv2;
		pv2=pv1;
		pv1=t;
		v1=P[F][pv1];
		v2=P[F][pv2];
	}
	c1=COL[v1];
	c2=COL[v2];
	//_P("(P[%d]=%d(col:%d)-P[%d]=%d(col:%d)\n",pv1,v1,COL[v1],pv2,v2,COL[v2]);
	
	c=0;
	FOR(t,P[F].size()-2) {
		//1周目はc1,c2以外から使う
		while(c == COL[P[F][(pv2+2+t)%P[F].size()]] ||
		      c == COL[P[F][(pv2+0+t)%P[F].size()]] ||
		      c == c1 || c==c2) {
			c = (c+1)%mc;
			if(c==0) c1=c2=-1;
			
		}
		int v = P[F][(pv2+1+t)%P[F].size()];
		
		if(COL[v]!=-1) _P("NG %d\n",v);
		//_P("OK %d %d %d\n",t,v,c);
		COL[v]=c;
		c = (c+1)%mc;
		if(c==0) c1=c2=-1;
	}
	
}

void dfs(int F) {
	int i,v1,v2,nf;
	
	done[F]=1;
	//_P("%d\n",F);
	
	//隣接するやつを探す
	FOR(i,P[F].size()) {
		v1 = P[F][i];
		v2 = P[F][(i+1)%P[F].size()];
		if(VM[v1][v2]==-1) continue;
		nf = VM[v1][v2] % 10000;
		if(nf==F) nf=VM[v1][v2] / 10000;
		if(done[nf]) continue;
		setcol(nf,v1,v2);
		dfs(nf);
	}
	
}

void solve(int _loop) {
	int i,j,k,result,res,dir,ok,state,fstate,up,x,y,sp,dist1,dist2;
	int wid,hei,mv,mi;
	double br,tb1,tb2,start,end;
	
	
	GET2(&N,&M);
	FOR(i,M) {
		U[i] = GETi()-1;
	}
	FOR(i,M) {
		V[i] = GETi()-1;
	}
	
	P.clear();
	P.resize(1);
	
	FOR(i,N) {
		P[0].push_back(i);
		COL[i]=-1;
	}
	
	FOR(i,M) {
		FOR(j,P.size()) {
			int nv=0;
			FOR(k,P[j].size()) {
				if(P[j][k]==U[i]) nv++;
				if(P[j][k]==V[i]) nv++;
			}
			
			if(nv==2) {
				split(j,U[i],V[i]);
				break;
			}
		}
		
	}
	
	mc = 9999;
	MINUS(VM);
	MINUS(COL);
	FOR(i,P.size()) {
		if(P[i].size() < mc) mc =P[i].size();
		FOR(j,P[i].size()) {
			for(k=j+1;k<P[i].size();k++) {
				int u=P[i][j], v=P[i][k];
				if(((u-v+N)%N)!=1 && ((u-v+N)%N)!=N-1) {
					if(VM[u][v]==-1) VM[u][v]=i;
					else VM[u][v]+=i*10000;
					if(VM[v][u]==-1) VM[v][u]=i;
					else VM[v][u]+=i*10000;
				}
			}
		}
	}
	
	ZERO(done);
	FOR(i,P.size()) {
		if(P[i].size()==mc) {
			FOR(j,P[i].size()){
				COL[P[i][j]]=j;
				//_P("OK %d %d\n",P[i][j],j);
			}
			done[i]=1;
			dfs(i);
			break;
		}
	}
	
	_PE("Case #%d: %d\n",_loop,mc);
	FOR(i,N) {
		_PE("%d ",COL[i]+1);
	}
	_PE("\n");
	
	//check;
	FOR(i,P.size()) {
		/* smallのみの全色利用チェック
		int m;
		m=0;
		FOR(j,P[i].size()) m |= 1<<COL[P[i][j]];
		if(m!=(1<<mc)-1) {_PE("***%d %d\n",i,m);}
		*/
		FOR(j,P[i].size()) if(COL[P[i][j]]==COL[P[i][(j+1)%P[i].size()]]) {_PE("****%d %d %d %d\n",i,j,P[i][j],(j+1)%P[i].size());}
		
	}
}

まとめ

smallで通すまで苦戦したけど、smallが通ったらそのままlargeも通った。
Analysisのページにもあるけど、図形分割問題はデータ構造の持ち方に工夫がいるね。