AtCoder ARC #136 : E - Non-coprime DAG

うーむこれは思い至らず。
https://atcoder.jp/contests/arc136/tasks/arc136_e

問題

1～NのラベルがついたN個の頂点からなる有向グラフがある。
GCD(i,j)が2以上である頂点i,j間には、i＜jの場合i→jと有向辺が張られる。
各頂点には価値A[i]が設定されている。

このグラフからいくつか頂点を選ぶ。
ただし、それらの頂点はどの2点においても、片方の頂点からもう片方の頂点に有向辺に沿って連結でないようにしたい。
得られる価値の総和の最大値を求めよ。

解法

1番の頂点はどことも辺が張られないので、必ずその点を選ぶことができる。
以下2番以降の頂点を考える。
偶数同士の頂点は必ず連結なので、頂点xから遷移できる最小の偶数番号の頂点と、xに遷移できる最大の偶数番号の頂点を考える。
f(n)をnの素因数の最小値とすると、

• xが偶数なら、上記2頂点はいずれもx。
• xが奇数なら、x-f(x)以下の偶数からxに遷移可能だし、xからx+f(x)以上の偶数に遷移可能

よって、互いに遷移できない領域が重複するような複数のxを選ぼう。
各xに対し、BITや累積和を使って数列の下記範囲にA[x]を加算する。

• xが偶数なら[x,x]
• xが奇数なら[x-f(n)+1,x+f(n)-1]

あとはこの数列の最大値が解。

int N;
ll A[1010101];
int mip[1010101];

ll S[2010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=2;i<=1000000;i++) if(mip[i]==0) {
		for(j=i;j<=1000000;j+=i) if(mip[j]==0) mip[j]=i;
	}
	
	cin>>N;
	for(i=1;i<=N;i++) {
		cin>>A[i];
		
		if(i%2==0) {
			S[i]+=A[i];
			S[i+1]-=A[i];
		}
		else if(i>1) {
			S[i-mip[i]+1]+=A[i];
			S[i+mip[i]]-=A[i];
		}
	}
	
	ll ret=0;
	for(i=1;i<=2000000;i++) {
		S[i]+=S[i-1];
		ret=max(ret,S[i]);
	}
	cout<<ret+A[1]<<endl;
}

まとめ

偶奇で分けるところに考えが至らず…。