Codeforces #290 Div1 B. Fox And Jumping

Codeforceで似たような問題を見ていたので割とあっさり。
http://codeforces.com/contest/512/problem/B

問題

1次元の数直線上に置いて、プレイヤーの初期値は原点である。
ここでN枚のカードがある。
各カードには数値L[i]が書かれており、価格はC[i]である。

プレイヤーは数値xが書かれたカードを1枚でも持っていると、現在位置から+xまたは-xの位置に何度でもジャンプできる。
プレイヤーが任意の格子点に移動するために必要なカードの総購入価格を求めよ。

解法

複数枚カードを持っている場合、その最大公約数が1なら題意を満たせる。

あとはmapを使ってある公約数を満たす最小価格をDPで更新していけばよい。
公約数をmapで管理するテクは、過去にも登場している。
Bayan 2015 Contest Warmup: D. CGCDSSQ - kmjp's blog
AtCoder ARC #023 : D - GCD区間 - kmjp's blog

int N;
ll L[1000],C[1000];
map<ll,ll> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i];
	FOR(i,N) {
		cin>>C[i];
		if(M.count(L[i])) M[L[i]]=min(M[L[i]],C[i]);
		else M[L[i]]=C[i];
		ITR(it,M) {
			ll X=__gcd(it->first,L[i]);
			if(M.count(X)) M[X]=min(M[X],it->second+C[i]);
			else M[X]=it->second+C[i];
		}
	}
	
	ll mi=-1;
	if(M.count(1)) mi=M[1];
	cout<<mi<<endl;
}

まとめ

約数の数が多すぎてmapがMLEするかと思ったけど、なんとか大丈夫だった。