Codeforces #210 Div1. B. Levko and Array

Bは最初アプローチを間違えてpretestを3ミスした。
それでも本番に何とか解ききれてよかったな。
http://codeforces.com/contest/360/problem/B

問題

N要素の整数値からなる数列Aがある。
ここで、数列の隣接要素同士の差の絶対値のうち、最大値を小さくしたい。

N以下の数Kが与えられ、数列AのうちK要素を任意の値に書き換えられる場合、上記隣接要素の差の最大値を最小化せよ。

解法

整数値を最小化する問題なので、二分探索すればよい。
二分探索で最大値の候補Cが引数に与えられたとき、差をC以下に押さえられるか検証する。

Aの各要素iについて、A[0]～A[i]において隣接要素をC以下に押さえることであと何回値を変更できるか、をDPで処理する。
そのような数をdp[i]とし、dp[0]=Kとする。
各A[x]に対し、A[x+1]～A[x+y]までの値を変え、A[x+(y+1)]の値を変えないとすると、(y+1)*C<=|A[x+y+1]-A[x]|だったらそのようなx,yが取れ、dp[x+y+1]=dp[x]-yとなる。

値を変える数をK個以下に押さえられるなら、隣接要素をC以下に押さえられる。
上記DPはO(NK)なので、二分探索で30回ぐらいDPしても時間は間に合う。

int N,K;
ll A[10000];
int dpdp[2005];

int okok(ll piv) {
	int x,y;
	
	MINUS(dpdp);
	FOR(x,K+1) dpdp[K-x]=x;
	
	FOR(x,N) for(y=x+1;y<N;y++) {
		if(abs(A[y]-A[x])<=piv*(y-x)) dpdp[y]=max(dpdp[y],dpdp[x]-(y-x-1));
	}
	FOR(x,N) if(dpdp[x]>=(N-x-1)) return 1;
	return 0;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	
	if(K>=N-1) return _P("0\n");
	
	ll lo=0,hi=1LL<<35;
	FOR(i,40) {
		ll mi=(lo+hi)/2;
		if(okok(mi)) hi=mi;
		else lo=mi;
	}
	lo=max(lo-10,0LL);
	while(!okok(lo)) lo++;
	cout << lo << endl;
}

まとめ

最初のアプローチミスに本番中に気づけて良かった。