UnKoder #02 : Pass on Tree

面白かったです。
https://www.hackerrank.com/contests/unkoder-02/challenges/pass-on-tree

問題

木を成すグラフが与えられる。
頂点Sに白い駒、Tに黒い駒が与えられる。

以下の条件を満たす範囲で駒を動かし、両者の位置を交換したい。

• 1手あたり、どちらかの駒を隣接点に移動する。
• 両方の駒が同一頂点にあってはならない。

両者の位置を交換するのに必要な最小手数を求めよ。

解法

2頂点x,y間の距離をD(x,y)とする。
両者の位置を交換できるのは、以下の2通り。

• S-Tの最短経路中に、(S,T以外の頂点で)次数3以上の点がある場合。
  • この場合、白い駒をS-Tの経路から1手分脇に移動してもう黒い駒をTからSに移動し、白い駒をTに移動すればよい。
  • この場合手数は2*D(S,T)+2。
• S,T,またはS-Tの最短経路外に、次数3以上の点Pがある場合。
  • 一度両方の駒をこの点まで移動する。この点はS-Tの最短経路上ではないので、白い駒も黒い駒も同じ側からこの頂点に移動する。
  • その歳、白い駒と黒い駒を別々の脇道に1手移動して互いの位置を入れ替えることができる。
  • この場合この場合手数は2*(D(S,P)+D(T,P))+4。

最初に2回DFSして各頂点xに対しD(S,x)とD(T,x)を求めておいて、後は次数3以上の頂点に対し上記手数の最小値を求めればよい。

int N,S,T;
int D[101000][2];
vector<int> E[101000];

void dfs(int cur,int pre,int type) {
	if(pre!=-1) D[cur][type]=D[pre][type]+1;
	FORR(r,E[cur]) if(r!=pre) dfs(r,cur,type);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>T;
	S--,T--;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(S,-1,0);
	dfs(T,-1,1);
	
	int mi=1<<20;
	FOR(i,N) if(E[i].size()>=3) {
		if(D[i][0]+D[i][1]==D[T][0] && D[i][0] && D[i][1]) mi=min(mi,2*D[T][0]+2);
		else mi=min(mi,2*(D[i][0]+D[i][1])+4);
	}
	if(mi>=1<<20) mi=-1;
	cout<<mi<<endl;
}

まとめ

脇道がS-T上にあるかそうでないかで、大きく結果が変わるのが興味深い性質だね。