Google Code Jam 2016 Round1A : C. BFFs

苦戦したけど解けて良かった。
https://code.google.com/codejam/contest/4304486/dashboard#s=p2

問題

N人の児童がいる。
それぞれの児童には永遠の友人F[i]が1名ずついる。

N人の児童のうち何人かを円周上に並べたい。
その際、各児童は左右どちらかに永遠の友人が並ぶようにしたい。

条件を満たす並べ方のうち、最大の児童数を求めよ。

解法

Smallはnext_permutationで並べ方を全部列挙しても間に合う。

児童の友好関係を有向グラフを見なすと、条件を満たす並べ方は以下の２通りがある。
児童数が大きい方を回答しよう。

全体で閉路を構築する

児童iの右隣にF[i]を置く、ということを繰り返すとき、児童iが閉路中に含まれていれば最終的にiを永遠の友人と見なす児童x(F[x]=i)が登場する。
よって最長閉路の頂点数が解の候補となる。

閉路とならないものを

互いに永遠の友人の関係にある2名x,y(F[x]=y,F[y]=x)がいるとする。
この２名を並べておけば、全体で閉路を構築しなくても、両端をa,bとしたとき a→F[a]→F[F[a]]→…→x⇔y←…←F[F[b]]←F[b]←bというような関係にある並びが構築できる。

G(x) := 友人関係を順に辿るとxに到達する、xまでの距離が最長の頂点
とすると、a=G(x), b=G(y)として選べば、a～x～y～bはx,yを含む最長列となる。

互いに永遠の友人の関係にある2名組は1つとは限らないので、同様に別の組(x',y')に対しG(x')～x'～y'～G(y')を並べた列もやはり条件を満たす。
また、a～x～y～bの列にG(x')～x'～y'～G(y')を並べても問題ない。
よって、互いに永遠の友人の関係にある2名組(x,y)ごとに最長列G(x)～x～y～G(y)を求め、その長さの総和を取るとよい。

int N;
int P[1010];
int ma;
int inloop[1010];
int tar[1010],D[1010];
int ma2[1010];

void dfs(int cur,int st,int step) {
	if(step>1000) return;
	if(P[cur]==st) {
		tar[cur]=inloop[cur]=cur;
		sz[cur]=step;
		ma=max(ma,step);
	}
	else {
		dfs(P[cur],st,step+1);
		if(inloop[st]>=0) {
			tar[cur]=inloop[cur]=cur;
			sz[cur]=sz[st];
		}
	}
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>P[i], P[i]--, V[i]=i;
	ma=0;
	MINUS(inloop);
	FOR(i,N) dfs(i,i,1);
	MINUS(tar);
	MINUS(D);
	ZERO(ma2);
	FOR(y,N) FOR(x,y) if(P[x]==y && P[y]==x) {
		inloop[x]=y,inloop[y]=x;
		tar[x]=x;
		tar[y]=y;
		D[x]=D[y]=1;
		ma2[x]=ma2[y]=1;
	}
	
	FOR(i,1010) {
		FOR(x,N) if(D[P[x]]>=0 && inloop[x]==-1) D[x]=D[P[x]]+1, tar[x]=tar[P[x]], ma2[tar[x]]=max(ma2[tar[x]],D[x]);
	}
	
	int tot=0;
	FOR(x,N) if(tar[x]==x) tot+=ma2[x];
	ma=max(ma,tot);
	
	_P("Case #%d: %d\n",_loop,ma);
}

まとめ

自分はBFFと思っていても、向こうからはBFFと思ってもらえないケースがあるの世知辛いよね。