HackerRank HourRank 21 : C. Tree Isomorphism

最近これ系多い。
https://www.hackerrank.com/contests/hourrank-21/challenges/tree-isomorphism

問題

N頂点の木が与えられる。部分木についてisomorphicなものを重複カウントしない場合、いくつあるか。

解法

部分木の頂点を(2^N)通り総当たりし、そのうち連結なものを処理しよう。
isomorphicをまともに判定するのは無謀なので、ハッシュ値を取ってユニークなものを求めよう。
同一性判定の方法によるけどO(N*2^N*logN)程度計算量があってちょっと重いので、ハッシュ計算は適宜メモ化しておく。

int N;
vector<int> E[20];
int A[20],B[20];
int AS[20],BS[20];
vector<ll> S[20];
ll memo[19][1<<19];
int tmask[20][20];
int tmask2[20][20];

ll tree_normalize(vector<ll> T) {
	static ll momo[2]={1000000007,1000000009};
	static vector<ll> prim = {79,73,47,7,41,13,17,19,23,29,31,37,43,5,53,59,61,67,71};
	
	sort(ALL(T));
	int id=0,id2=1;
	ll a=1,b=1;
	FORR(r,T) {
		ll h=r>>32, l=r-(h<<32);
		(a+=h*prim[(id++)%prim.size()])%=momo[0];
		(b+=l*prim[(id2++)%prim.size()])%=momo[1];
	}
	return (a<<32)+b;
}

ll hashhash(int cur,int mask) {
	if(memo[cur][mask]<0) {
		vector<ll> v;
		FORR(e,E[cur]) if(mask&(1<<e)) v.push_back(hashhash(e,mask&tmask[cur][e]));
		memo[cur][mask]=tree_normalize(v);
	}
	return memo[cur][mask];
}

int dfsmask(int cur,int pre) {
	if(tmask2[cur][pre]==0) {
		tmask2[cur][pre]=1<<cur;
		FORR(r,E[cur]) if(r!=pre) tmask2[cur][pre] |= dfsmask(r,cur);
	}
	return tmask2[cur][pre];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(memo);
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
		A[i]=x-1;
		B[i]=y-1;
		AS[i]=1<<A[i];
		BS[i]=1<<B[i];
	}
	
	FOR(i,N) tmask[19][i]=dfsmask(i,19);
	FOR(i,N-1) {
		tmask[A[i]][B[i]]=dfsmask(B[i],A[i]);
		tmask[B[i]][A[i]]=dfsmask(A[i],B[i]);
	}
	
	for(int mask=1;mask<1<<N;mask++) {
		
		x = __builtin_popcount(mask);
		
		int ok=0;
		FOR(i,N-1) if((mask&AS[i])&&(mask&BS[i])) ok++;
		if(ok!=x-1) continue;
		vector<ll> T;
		FOR(i,N) if(mask&(1<<i)) T.push_back(hashhash(i,mask));
		S[x].push_back(tree_normalize(T));
	}
	
	int ret=0;
	FOR(x,20) {
		sort(ALL(S[x]));
		S[x].erase(unique(ALL(S[x])),S[x].end());
		ret+=S[x].size();
	}
	cout<<ret<<endl;
}

まとめ

本番ハッシュ値判定があまりうまくいかなかった。