Codeforces #174 Div1 D. Cows and Cool Sequences

CF172に比べだいぶあっさり。
http://codeforces.com/contest/283/problem/D

問題

整数の対(x,y)がcoolであるとは、xが連続するy個の整数の和で表現できる場合を言う。
さらにN要素の数列(A[0], A[1], A[2], ... , A[N-1])がcoolであるとは、隣接する2要素(A[i],A[i+1])がいずれもcoolであることをいう。

ここで、数列Aが与えられる。
必要に応じていくつかの要素を任意の正の整数に置き換え、全体をcoolにしたい。
最少で何要素を置き換えればよいか。

解法

y個の整数の和で表現できる数を考えると、yが奇数ならky、yが偶数なら(k+1/2)yの形の数を表現できる。

部分列(A[l], A[l+1], A[l+2], .. , A[r])において、A[l]とA[r]はそのままでA[l+1]～A[r-1]のr-l-1要素を置き換えて、この部分列をcoolに出来る条件を考える。
上記推論より、A[r]からA[r-1]、A[r-2]…の最小値について考えると、それぞれA[i]が偶数である限りA[i-1]はその半分となり、A[i]が奇数となると以降A[i-1], A[i-2], ... はずっとA[i]と一致する。

よって、A[r]を(r-l)回まで(偶数である限り)半減した値をpとすると、

• pが偶数ならA[l]=(k+1/2)pの形である
• pが奇数ならA[l]=kpの形である

ならA[l]とA[r]はそのままでこの部分列をcoolに出来る。

後はO(N^2)のDPで置き換える数の最小値を求めればよい。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int N,dp[5010];
	ll A[5010];
	
	cin>>N;
	int ret=N;
	FOR(x,N) {
		cin>>A[x];
		dp[x]=x;
		ll X=A[x];
		for(y=x-1;y>=0;y--) {
			if(X%2==0 && (A[y]%X)==X/2) dp[x]=min(dp[x],dp[y]+x-y-1);
			if(X%2==1 && (A[y]%X)==0) dp[x]=min(dp[x],dp[y]+x-y-1);
			if(X%2==0) X>>=1;
		}
		ret=min(ret,dp[x]+(N-(x+1)));
	}
	cout << ret << endl;
}

まとめ

上記部分列の関係をさっと思いつけたのであっさり解けた。
…まぁ微修正で何とかWAしたけど。