Codeforces #231 Div2. D. Physical Education and Buns

これは何とか本番中に解答。
http://codeforces.com/contest/394/problem/D

問題

N要素の整数配列が与えられる。
各要素をいくつか数字を動かし、等差数列にしたい。

各要素の数値を動かす最大値が最小となるような等差数列の初項と公差を求めよ。

解法

初期として各数字は-10000～10000のため、最大でも20000動かせば全部の数字は同じ値に出来る。

以下では、公差と初項を総当たりし、等差数列にするために動かす最大値を求めている。
公差が大きいと最後の項がすぐに30000以上に達してしまい明らかに20000以上動かす必要があり解となりえないので、試すべき初項はほとんどなくなる。
そのため一見計算量はO(公差候補×初項候補×N)だが時間は余裕で間に合う。

int N;
int H[10005];
int mi=10000;

int dodo(int xx,int hh) {
	int i;
	int ma=0;
	FOR(i,N) {
		int t=hh+xx*i;
		ma=max(ma,abs(t-H[i]));
		if(ma>=mi) return ma;
	}
	return ma;
}

void solve() {
	int f,i,j,k,l,x,y,h;
	int bh,bx;
	
	cin>>N;
	FOR(i,N) cin>>H[i];
	sort(H,H+N);
	
	
	FOR(x,20001) {
		if(x*(N-1)>40000) break;
		for(h=H[0]-mi+1;h<H[0]+mi;h++) {
			y=dodo(x,h);
			if(y<mi) mi=y,bh=h,bx=x;
		}
	}
	
	_P("%d\n%d %d\n",mi,bh,bx);
}

まとめ

実際は初項と公差は総当たりしなくても、片方決めればもう片方の最適値は大体決まるようだ。