Google Code Jam 2011 Round 2 : D. A.I. War

こちらも本番Smallだけ解いて放置していたので再チャレンジ。
http://code.google.com/codejam/contest/1150486/dashboard#s=p3

Analysisにしたがって解いてみた。
この問題は、辺0->1を最短ルートで行くルートのうち、最短ルートに隣接する点を最大化するもの。
よって、最短ルートをBFSで求めつつ、隣接点の最大値を求めていく。

最大値の求め方だけど、点Cの最大値は、Cの手前の点をB、Bの手前の点をAとしたとき、Bの隣接点数に、AにもBにも接しないCの隣接点数を足すことで求めている。
(Analysisにはminとあるけどmaxの間違いだと思う)

この処理はAとBとCでDPだけど、点数は最大360だし、辺は最大2000なのでさほど計算量は多くない。

int P,W;
int X[2001],Y[2001];
int D[401];
int mat[401][401];
int nmat[401];
int mat2[401][401];
int DV[401][401];
int T[401];

/* tの隣であってtやsの隣でないもの */
int uniqn(int r,int s,int t) {
	int c = 0;
	int ri,si,ti;
	ri=si=ti=0;
	while(ti<nmat[t]) {
		while(ri<nmat[r] && mat[r][ri]<mat[t][ti]) ri++;
		while(si<nmat[s] && mat[s][si]<mat[t][ti]) si++;
		
		if((ri>=nmat[r] || mat[t][ti]!=mat[r][ri]) && (si>=nmat[s] || mat[t][ti]!=mat[s][si]) && mat[t][ti]!=r && mat[t][ti]!=s) {
			//_P("(AA %d)",mat[t][ti]);
			c++;
		}
		ti++;
	}
	//_P("(%d %d %d %d)",r,s,t,c);
	return c;
}

/* s->tで増える点 */
int newt(int s,int t) {
	/* r->s->t で DV[s][t]=DV[r][s]+G[r][s][t] */
	int i,r,c,tc;
	
	if(DV[s][t]==-1) {
		
		c=0;
		if(s==0) {
			c = T[0]+uniqn(0,0,t);
		}
		else {
			FOR(i,nmat[s]) {
				r = mat[s][i];
				if(D[r]!=D[s]-1) continue;
				if(DV[r][s]==-1) _P("assert!!\n");
				
				tc = DV[r][s]+uniqn(r,s,t);
				if(c<tc) c = tc;
			}
		}
		
		DV[s][t]=c;
	}
	//_P("(%d,%d=%d)\n",s,t,DV[s][t]);
	return DV[s][t];
}

void gett(){
	int i;
	deque<int> q;
	
	q.clear();
	FOR(i,P) D[i]=99999;
	D[0]=0;
	q.push_back(0);
	
	ZERO(T);
	T[0]=1+nmat[0];
	
	while(!q.empty()) {
		int key = q.front();
		q.pop_front();
		
		FOR(i,nmat[key]) {
			int tar = mat[key][i];
			if(D[tar]>D[key]+1) {
				D[tar] = D[key]+1;
				q.push_back(tar);
			}
			if(D[tar]==D[key]+1) {
				int t = newt(key,tar);
				if(T[tar]<t) T[tar]=t;
			}
		}
	}
	//FOR(i,P) _P("%d\n",T[i]);
}

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;
	
	ZERO(mat);
	ZERO(mat2);
	ZERO(nmat);
	GET2(&P,&W);
	
	FOR(i,W) {
		scanf("%d,%d", &X[i],&Y[i]);
		mat[X[i]][nmat[X[i]]++]=Y[i];
		mat[Y[i]][nmat[Y[i]]++]=X[i];
		mat2[X[i]][Y[i]]=1;
		mat2[Y[i]][X[i]]=1;
	}
	FOR(i,P) sort(&mat[i][0],&mat[i][nmat[i]]);
	
	//距離
	MINUS(DV);
	gett();
	
	int resd = D[1]-1;
	int mt = 0;
	FOR(i,P) if(D[i]==resd && mat2[i][1]==1 && T[i]>mt) mt=T[i];
	//FOR(i,P) _P("(%d:%d,%d) ",i,D[i],T[i]);
	//通った点を引く
	mt-=resd+1;
	_PE("Case #%d: %d %d\n",_loop,resd,mt);
}

まとめ

途中数えもれとか過剰な足し算でなかなか数値が合わず苦労した。