HourRank17 : D. Number Game on a Tree

またハッシュが衝突する…。
https://www.hackerrank.com/contests/hourrank-17/challenges/number-game-on-a-tree

問題

木を成す無向グラフが与えられる。
各辺には非負整数が振られている。

以下のようなゲームを考える。
頂点を2つ選び、両者を結ぶ最短経路上にある辺の整数からなるmultisetを考えよう。
ここから2人で交互に数字を取り除いていくゲームを行う。
なお、数字を取り除く際は(最初の手番を除き)前の人より大きな数字を取ることはできない。
自分の手番で数字を取り除けなくなったら負けである。

先手必勝となる頂点ペアの選び方は何通りあるか。

解法

先手必勝のケースは、簡単に言えば集合に含まれる選択可能な数字群のうち、少なくとも1つ以上奇数個存在するケースである。
逆に言うと、すべての数字が偶数個ずつ含まれる場合、自分の手番で必ず奇数個含まれる数字が1個生じ、相手の手番をそれを取り除かれるので自分の手番は常に「すべての数字が偶数個ずつ含まれる場合」から抜けることができない。

これがわかると割と簡単。
グラフを根付き木とみなし、根から各頂点までの間の辺に、奇数回登場する数値を列挙しよう。
その列挙した数字群が等しくなるような頂点同士を選ぶと、先手必敗になる。

実際は「奇数回登場する数値を列挙」を愚直に行うとO(|V|^2)かかって破たんするので、何らかのハッシュ値に落とし込んで比較しよう。
これも結構ハッシュが衝突しがちなので丁寧にハッシュ関数を選択する必要がある。

int Q;
int N;
vector<pair<int,int>> E[505050];
set<int> S;
ll ret;
map<pair<int,int>,int> M;
int mo[2]={1000000021,1000000009};

ll modpow(ll a, ll n,ll mo) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void dfs(int cur,int pre,int a,int b) {
	ret -= M[{a,b}];
	M[{a,b}]++;
	FORR(e,E[cur]) if(e.first!=pre) {
		if(S.count(e.second)) {
			S.erase(e.second);
			int a2 = 1LL*a*modpow(7,1LL*e.second*(mo[0]-2),mo[0])%mo[0];
			int b2 = (b+modpow(5,1LL*e.second*(mo[1]-2),mo[1]))%mo[1];
			dfs(e.first,cur,a2,b2);
			S.insert(e.second);
		}
		else {
			S.insert(e.second);
			int a2 = a*modpow(7,e.second,mo[0])%mo[0];
			int b2 = (b+mo[1]-modpow(5,1LL*e.second*(mo[1]-2),mo[1]))%mo[1];
			dfs(e.first,cur,a2,b2);
			S.erase(e.second);
		}
		
		
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		
		cin>>N;
		ret=1LL*N*(N-1)/2;
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y>>r;
			x--,y--,r++;
			E[x].push_back({y,r});
			E[y].push_back({x,r});
		}
		M.clear();
		S.clear();
		dfs(0,-1,1,1);
		cout<<ret<<endl;
		
	}
	
}

まとめ

先日のCodeforcesといいハッシュ衝突に悩まされている。