TopCoder SRM 633 Div2 Hard GCDLCMEasy

そこまで難しくはないが、本番正答率はかなり低い。
http://community.topcoder.com/stat?c=problem_statement&pm=13470

問題

数nに対し、ある数列X[i]があるとする。

この数列に対し、m個の条件A[i],B[i],G[i],L[i]が与えられる。
各条件は以下を意味する。

• X[A[i]]とX[B[i]]の最大公約数はG[i]
• X[A[i]]とX[B[i]]の最小公倍数はL[i]

すべての条件を満たすX[i]は存在しうるか。

解法

X[A[i]]*X[B[i]]/G[i]=L[i]の関係があるので、X[A[i]]とX[B[i]]のどちらかが定まれば、もう片方も定まる。
L[i]の上限が10000なことからX[i]は10000以下なので、未決定なX[i]を1～10000で総当たりし、条件を満たすよう他の値をDFSで決めていけばよい。
1～10000のどれにしても矛盾が生じるなら、X[i]は存在しない。

X[A[i]]がすでに決まっている場合、以下を満たせば対応する有効なX[B[i]]があるといえる。

• まずX[A[i]]はG[i]の倍数でL[i]の約数である。
• X[B[i]]=L[i]*G[i]/X[A[i]]で求めると、X[B[i]]もG[i]の倍数でL[i]の約数である。
• 実際にX[A[i]]とX[B[i]]の最大公約数・最小公倍数はG[i],L[i]である。

class GCDLCMEasy {
	public:
	int dfs(int cur) {
		int i;
		FOR(i,P[cur].size()) {
			int tar=P[cur][i].second,op=P[cur][i].first;
			if(num[cur]%GG[tar] ||LL[tar]%num[cur]) return 0;
			
			ll nv=LL[tar]/num[cur]*GG[tar];
			if(num[op]>0 && num[op]!=nv) return 0;
			if(nv%GG[tar] || LL[tar]%nv) return 0;
			if(__gcd(num[cur],nv)!=GG[tar]) return 0;
			if(num[cur]*nv!=LL[tar]*1LL*GG[tar]) return 0;
			
			
			if(num[op]==0) {
				num[op]=nv;
				upd.push_back(op);
				if(dfs(op)==0) return 0;
			}
		}
		return 1;
	}
	
	string possible(int n, vector <int> A, vector <int> B, vector <int> G, vector <int> L) {
		int i,x;
		N=n;
		GG=G,LL=L;
		
		ZERO(num);
		FOR(i,n) P[i].clear();
		FOR(i,G.size()) {
			P[A[i]].push_back(make_pair(B[i],i));
			P[B[i]].push_back(make_pair(A[i],i));
		}
		FOR(i,N) if(num[i]==0) {
			for(x=1;x<=10000;x++) {
				num[i]=x;
				upd.clear();
				if(dfs(i))break;
				ITR(it,upd) num[*it]=0;
			}
			if(x>10000) return "Solution does not exist";
		}
		return "Solution exists";
	}
}

まとめ

Div1Hardに比べるとだいぶおだやかな問題。