TopCoderOpen 2013 Round2C Easy DancingFoxes

さてTCO R2C。Easyでは微妙な問題文でChallengeの大量虐殺発生。
自分もご他聞にもれずChallengeで撃沈した。おかげで0pt。

最初Submitした際「Easyとはいえこんな簡単なはずはない、もしや…」と思ったところで「数えるのはSongsじゃなくDances」とアナウンスが出て安心してしまった…。

本番MediumはそこそこにHardに手を出したのもダメだった。Medium頑張れば行けたかもな…。
http://community.topcoder.com/stat?c=problem_statement&pm=12548

問題

N匹の狐と、互いの友人関係が与えられる。
ここで、１回ダンスを行うと、各狐は他の１匹の狐と踊るか、誰とも踊らないといった行動がとれる。
他の狐と踊るとその狐と友人になれるが、踊れるのは共通の友人を持つ狐だけである。
0番と1番の狐が友人になるのに必要な最少のダンス開催回数を求めよ。

解法

まず、友達関係をコスト1の辺とみなしたグラフを考え、0番から1番までの最小コストを求める。
以下はDijkstraで行っているが、N<=50なのでFloyd法でも良い。

ここで、以下の様に友人関係が連なっているとする。間の狐の番号は何でもよく、問題は辺の長さだけである。

0--A--B--C--D--E--F--G--H--I--1

ここで、１回ダンスを行うと、0とBが友人になる。
同様にCとE、FとHと辺の長さが3毎に辺を１個減らすことができ、以下の様に5手で直接の友人になる。

0--B--C--E--F--H--I--1
0--C--E--H--I--1
0--E--H--1
0--H--1
0--1

Editorialを見るとよりわかりやすい。

class DancingFoxes {
	public:
	int minimalDays(vector <string> friendship) {
		int F[100];
		int vis[100];
		int N=friendship.size();
		
		int i,x,y;
		FOR(i,100) F[i]=999;
		F[0]=0;
		ZERO(vis);
		
		queue<int> q;
		q.push(0);
		while(!q.empty()) {
			int k=q.front();
			q.pop();
			vis[k]=0;
			
			FOR(x,N) {
				if(x==k) continue;
				if(friendship[k][x]=='Y') {
					if(F[x]>F[k]+1) {
						F[x]=F[k]+1;
						if(vis[x]==0) {
							q.push(x);
							vis[x]=1;
						}
					}
				}
			}
		}
		
		if(F[1]>100) return -1;
		x=F[1];
		y=0;
		while(x>1) {
			x = x-(x+1)/3;
			y++;
		}
		
		return y;
	}

};

まとめ

上のコードは無駄にDijkstraして複雑になってしまった。
辺の圧縮の考えは面白いね。
問題文さえまともなら…。