Codeforces #236 Div1 B. Upgrading Array

せっかくそこそこの時間で解いたのにしょうもないミス…。
http://codeforces.com/contest/403/problem/B

問題

数列A[1]～A[N]がある。また悪い素数の一覧B[i]がある。
悪い素数の一覧B[i]に含まれない素数はよい素数である。

F(x)=(xを素因数分解したときのよい素数の数)-(xを素因数分解したときの悪い素数の数) と定義する。

ここで、1≦R≦NとなるRに対し、g=gcd(A[1]～A[R])を求め、A[1]～A[R]をgで割る、という処理を任意回数行えるとする。
その時最終的なF(A[i])の総和を最大化せよ。

解法

1度あるRについてA[1]～A[R]で割ると、以後A[1]～A[R]のGCDは1となるため、R<=PとなるようなPに対しGCDが1となるため、A[1]～A[P]をGCDで割ることはできない。

よって、Rが大きな順にGCDで割って得するか損するか判定すればよい。
g=GCD(A[1]～A[R])に対しA[1]～A[R]をgで割ると、R*F(g)の分だけF(A[i])の総和から失われる。
よって、F(g)が0以上ならGCDで割らず、F(g)が負ならGCDで割ればよい。

以下のコードではF(x)に相当する関数calcをメモ化しているが、メモ化しなくても0.9sでギリギリ間に合う。
残念ながら自分は本番メモ化処理を間違えてこの問題を落とした…。

int N,M;
int A[5005],C[5005];
set<int> S;

map<int,int> memo;

int calc(int hoge) {
	int num=0;
	int org=hoge;
	if(memo.find(hoge)!=memo.end()) return memo[hoge];
	if(hoge==1) return 0;
	int i;
	for(i=2;i*i<=hoge;i++) {
		while(hoge%i==0) {
			if(S.find(i)==S.end()) num++;
			else num--;
			hoge/=i;
		}
	}
	if(hoge>1) {
		if(S.find(hoge)==S.end()) num++;
		else num--;
	}
	return memo[org]=num;
}


void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,M) {
		cin>>x;
		S.insert(x);
	}
	
	C[0]=A[0];
	FOR(i,N-1) C[i+1]=__gcd(C[i],A[i+1]);
	int gc=1;
	ll res=0;
	
	for(i=N-1;i>=0;i--) {
		if(calc(C[i]/gc)<0) gc=C[i];
		res += calc(A[i]/gc);
	}
	cout << res << endl;
}

まとめ

今更メモ化処理のミスでせっかくの問題を落とすなんて…。