TopCoder SRM 654 Div2 Medium OneEntrance

この回は不参加でした。
一応Div1Easy/Mediumは自力で解けたけど、本番だと時間内に解けきれなさそう。
http://community.topcoder.com/stat?c=problem_statement&pm=13698

問題

N個の部屋からなる木を成す無向グラフの形状をした建物がある。
また、その入り口はs番の部屋である。

この建物の各部屋にN個の異なる荷物が順に送られてくるので、各部屋に１個ずつ配置したい。
ただし、荷物は大きいので先に荷物を置いた部屋があると、その奥に荷物を持っていくことができない。

N部屋全部に荷物を置けるような荷物と部屋の対応付けはN!通りのうちいくつあるか。

解法

Nが小さいのでnext_permutationで荷物配置を全探索すればよい。

部屋yに荷物を持っていくとき、それより先に荷物を置かれた部屋xに対してxがs→yの経路上にある場合、荷物の配置ができない。
xがs→y上にあるかどうかは、Warshall-Floyedなどで全頂点間の距離S(p,q)を求めておき、。S(s,x)+S(x,y)==S(s,y)かどうかで判定できる。

class OneEntrance {
	public:
	int count(vector <int> a, vector <int> b, int s) {
		int mat[10][10];
		int V[10];
		int x,y,i;
		int N=a.size()+1;
		FOR(x,N) FOR(y,N) mat[x][y]=(x==y)?0:100;
		FOR(i,N-1) mat[a[i]][b[i]]=mat[b[i]][a[i]]=1;
		FOR(i,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
		
		FOR(i,N) V[i]=i;
		ll ret = 0;
		do {
			int ok=1;
			FOR(y,N) FOR(x,y) if(mat[s][V[y]]+mat[V[y]][V[x]]==mat[s][V[x]]) ok=0;
			ret += ok;
		} while(next_permutation(V,V+N));
		
		
		return ret;
		
	}
}

まとめ

Div2 Mediumとしては若干考える問題。