Codeforces #162 Div2. D. Good Sequences

どんどん行きます。
http://codeforces.com/contest/265/problem/D

単調増加の整数列が与えられる。
その部分列のうち、隣接する要素が互いに素じゃないようなもので最長の部分列の長さを答える。

元の整数列のうち任意の２値について、互いに素かどうか判定することで部分列に取り入れるか選ぶことはできる。
でもこの処理はO(N^2)かかるので、N<=100000だと時間切れする。

ここだと、項目数だけでなく数値の上限も100000であることを利用する。
たとえば元の整数列に2 4 6 8の様に共通の素因数を持つ数値がある場合、2の次には6や8に行く必要はなく隣の4に行けばよい。

同様に、数列中の各要素について、素因数分解して各素因数を公約数に持つ数値を数列から探し、そこを部分列で隣接させる候補にする。
これで各数値から隣接する数値の候補がわかるので、あとはDPで最長の部分列を求めればよい。

int np;
int prime[10000];
const int prime_max = 100000;
void cprime() {
	int i,j;
	char p[prime_max];

	np=0;
	ZERO(p);
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		prime[np++]=i;
		for(j=i*2;j<prime_max;j+=i) p[j]=1;
	}
}

int N;
int M[100001];
vector<int> path[100001];
int NP[100001];

void solve() {
	int f,r,i,j,k,l,cur,tar,ret,loop;
	int res,x,y;

	N=GETi();
	MINUS(M); 

	FOR(i,N) M[GETi()]=i;

	cprime();
	for(x=2;x<=100000;x++) {
		if(M[x]==-1) continue;

		l=x;
		FOR(y,np) {
			if(prime[y]>l) break;
			if(l%prime[y]>0) continue;
			while(l%prime[y]==0) l /= prime[y];

			for(f=x+prime[y];f<=100000;f+=prime[y]) {
				if(M[f]>=0) {
				path[M[x]].push_back(M[f]);
				break;
				}
			}
		}
		if(l==x && l>1) {
			for(f=x+x;f<=100000;f+=x) {
				if(M[f]>=0) {
					path[M[x]].push_back(M[f]);
					break;
				}
			}
		}
	}
	int ma=0;
	FOR(i,N) NP[i] = 1;
	FOR(i,N) {
		FOR(j,path[i].size()) NP[path[i][j]] = max(NP[path[i][j]] , NP[i]+1);
		ma=max(ma,NP[i]);
	}

	_P("%d\n",ma);
	return;
}

まとめ

これで500ms程度。もっと時間かかるかと思ったら意外と少なかった。
O(N logN)位？