TopCoder SRM 699 Div1 Medium FromToDivisible、Div2 Hard FromToDivisibleDiv2

これ450ptでもよさそう。
https://community.topcoder.com/stat?c=problem_statement&pm=14387
https://community.topcoder.com/stat?c=problem_statement&pm=14395

問題

1～N番のN頂点からなる有向グラフがある。
２つのM要素の数列A,Bにより辺の集合が定義される。
要素対(A[i],B[i])があるとき、A[i]の倍数の番号の頂点からB[i]の倍数の頂点の頂点に長さ１の辺があることを示す。

S番の頂点からT番の頂点に移動する場合の最小コストを求めよ。

解法

D(x) := x番の倍数の頂点に至る最短コスト
を考える。Tの約数tに対し、D(t)の最小値を求められらば解となる。

(A[i],B[i])があるとき、A[i]の倍数からB[i]の倍数の頂点に移動できる。
よって、今の頂点がxの場合、直前の移動でLCM(x,A[i])に移動していたと仮定すると、LCM(x,A[i])≦NであればxからB[i](またはその倍数)に移動できる。
あとはその容量でBFSしてD(t)を求めるだけ。

なお、初回の移動だけではSのLCMは取れないので、S%A[i]==0である場合のみB[i]に移動できる点に注意。

class FromToDivisible {
	public:
	
	int shortest(int N, int S, int T, vector <int> a, vector <int> b) {
		unordered_map<int,int> M;
		queue<int> Q;
		int i;
		
		FOR(i,a.size()) if(S%a[i]==0) {
			if(M.count(b[i])) continue;
			M[b[i]]=1;
			Q.push(b[i]);
		}
		
		while(Q.size()) {
			int C=Q.front();
			int co=M[C];
			if(T%C==0) return co;
			Q.pop();
			
			FOR(i,a.size()) {
				ll t=1LL*C*a[i]/__gcd(C,a[i]);
				if(t>N) continue;
				if(M.count(b[i])) continue;
				M[b[i]]=co+1;
				Q.push(b[i]);
			}
		}
		return -1;
	}
}

まとめ

LCMが思いつくまでにちょっと時間かかった。