AIM Tech Round : B. Array GCD

こちらは純粋な観点見落としなので、自分の手抜きがたたった形。
http://codeforces.com/contest/623/problem/B

問題

N要素の整数列Aが与えられる。
これらの整数に対し以下の処理が最大１回ずつ行える。

• 連続するいくつかの要素を削除する。(削除した個数)*aのコストがかかる。
• 任意の位置のいくつかの要素を、最大1だけずらす。(ずらした個数)*bのコストがかかる。

上記処理を行った後の整数列Aに対し、公約数が2以上となるようにしたい。
最小コストを求めよ。

解法

まず公約数の候補を求めよう。
最初か最後の要素は必ず残すので、処理後の公約数はA[0],A[0]+1,A[0]-1,A[N-1],A[N-1]+1,A[N-1]-1の素因数のいずれかである。
よって各素因数pについて、Aの公約数がpの倍数となるよう処理するコストの最小値を求めよう。

「連続する要素を削除する」という類の問題では、先頭からいくつかと末尾からいくつかを合わせて解を探索する方法がある。
本番自分はそのような解法でやったしそれでも解けるが、以下のDPの方が簡単である。

以下のような状態を考え、最小値を更新していこう。
dp[x][0] := 先頭x要素に対し、1回も削除を行わず要素がpの倍数となるようにする最小コスト
dp[x][1] := 先頭x要素に対し、直前要素までいくつか削除中で、残りの要素がpの倍数となるようにする最小コスト
dp[x][2] := 先頭x要素に対し、既に削除した範囲を抜け、再びAの要素を残して、それらがpの倍数となるようにする最小コスト

２つ目の添え字は0(まだ削除は使っていない)→1(削除中)→2(削除は使ってしまった)状態である。
A[x]をpで割った余りが0か1か(p-1)なら、要素を1ずらす手法を使えば要素の削除は不要だが、余りがそれ以外なら削除せざるを得ない。
あとはmin(dp[N][0],dp[N][1],dp[N][2])が解。

int N;
ll A,B;
int V[1010101];
ll ret;
ll dp[1010101][3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	FOR(i,N) cin>>V[i];
	ret=A*(N-1);
	
	vector<int> aa={V[0],V[0]-1,V[0]+1,V[N-1],V[N-1]+1,V[N-1]-1};
	set<int> S;
	FORR(r,aa) {
		y=r;
		for(x=2;x*x<=y;x++) while(y%x==0) S.insert(x),y/=x;
		if(y>1) S.insert(y);
	}
	
	FORR(r,S) {
		dp[0][1]=dp[0][2]=1LL<<60;
		FOR(x,N) {
			j=V[x]%r;
			if(j==0) {
				dp[x+1][0]=dp[x][0];
				dp[x+1][2]=min(dp[x][2],dp[x][1]);
			}
			else if(j==1 || j==r-1) {
				dp[x+1][0]=dp[x][0]+B;
				dp[x+1][2]=min(dp[x][2],dp[x][1])+B;
			}
			else {
				dp[x+1][0]=dp[x+1][2]=1LL<<60;
			}
			dp[x+1][1]=min(dp[x][0],dp[x][1])+A;
		}
		
		FOR(x,3) ret=min(ret,dp[N][x]);
	}
	cout<<ret<<endl;
	
}

まとめ

一部連続区間を除いて何かを求める問題、両端から挟み込むことばかり考えてたけど、削除前→削除中→削除後のDPの方がラクなケースもあるな。