kmjp's blog

競技プログラミング参加記です

TopCoder SRM 668 Div1 Medium WalkingToSchool

最終的には自力回答できたけど、1発ACはならず。
http://community.topcoder.com/stat?c=problem_statement&pm=13983

問題

N頂点M有効辺のグラフが与えられる。

ある程度巨大な任意の正整数Kに対し、頂点0→1及び1→0をちょうどKステップ隣接辺を辿って移動するような移動の仕方が可能か判定せよ。

解法

まずグラフを探索して、0→1及び1→0の閉路があることを確認する。

ある程度巨大な正整数Kに対し、問題文を満たす移動の仕方があるためには、頂点0から0に戻る様々な閉路長の最大公約数が1ならばよい。
それなら閉路長の最小公倍数以上のKは任意の整数が取れる。
よって頂点0から初めて2*N回程度隣接辺を辿り、0に戻る閉路長の最大公約数を求めればよい。

以下は律儀に各頂点において頂点0,1からの最短距離を求めてしまったが、単に到達可否を求めるだけでよさそう。

class WalkingToSchool {
	public:
	vector<int> E[2020];
	int dist[2][2020];
	int pre[2020];
	
	
	string canWalkExactly(int N, vector <int> from, vector <int> to) {
		int i;
		FOR(i,N) E[i].clear(),dist[0][i]=dist[1][i]=5050;
		FOR(i,from.size()) E[from[i]].push_back(to[i]);
		
		dist[0][0]=dist[1][1]=0;
		queue<int> Q;
		Q.push(0);
		Q.push(10001);
		while(Q.size()) {
			int cur=Q.front()%10000;
			int ph=Q.front()/10000;
			Q.pop();
			FORR(tar,E[cur]) if(dist[ph][tar]>dist[ph][cur]+1) {
				dist[ph][tar]=dist[ph][cur]+1;
				Q.push(ph*10000 + tar);
			}
		}
		if(dist[0][1]>5000 || dist[1][0]>5000) return "Chores";
		
		int par=dist[0][1]+dist[1][0];
		
		vector<int> S;
		S.push_back(0);
		
		ZERO(pre);
		for(i=1;i<=5000;i++) {
			vector<int> S2;
			FORR(r,S) FORR(r2,E[r]) if(pre[r2]<i) {
				if(r2==0) par=__gcd(par,i);
				else S2.push_back(r2), pre[r2]=i;
			}
			swap(S,S2);
		}
		
		return par==1?"Freedom":"Chores";
		
	}
}

まとめ

最初全頂点で閉路長を列挙しようとしてTLEしてしまった。