TopCoder SRM 518 Div1 Medium ConvexSequence

適当に解いちゃったら当たっちゃった回。
http://community.topcoder.com/stat?c=problem_statement&pm=11474

問題

N要素の数列X[i]が凸であるとは以下のことを示す。

• 1 ≤ i < N-2であるiに対しX[i-1]+X[i+1] ≤ 2*X[i]

数列X[i]に対しコスト1でX[i]の1要素を小さくすることができる。
X[i]を凸にする最小コストを求めよ。

解法

凸の条件を書き直すとX[i-1]-X[i] ≤ X[i]-X[i+1]である。
まずは階差数列Y[i]=X[i+1]-X[i]を取る。
あとはこのY[i]が単調増加になるようにすればよい。

X[i]を1小さくするというのは、Y[i-1]を1小さくしてY[i]を1大きくすることに相当する。
あとはY[i]を下から以下のように定めていけば全体が単調増加になる。

• i ≤ j ≤ N-2となるjに対し、Y[i]はY[i]～Y[j]の平均以下

class ConvexSequence {
	public:
	int N;
	long long getMinimum(vector <int> a) {
		int i,x,y,j;
		vector<ll> b,c;
		
		N=a.size();
		if(N<=2) return 0;
		
		ll ret=0;
		FOR(i,N-1) b.push_back((a[i+1]-a[i]));
		
		FOR(i,N-2) {
			ll mi=1LL<<35;
			ll tot=0;
			FOR(j,N-1-i) {
				tot+=b[i+j];
				ll hoge=tot/(j+1);
				if(tot<0 && tot%(j+1)) hoge--;
				mi=min(mi,hoge);
			}
			
			if(mi<b[i]) {
				ret+=b[i]-mi;
				b[i+1]+=b[i]-mi;
				b[i]=mi;
			}
		}
		
		return ret;
	}
}

まとめ

これで当たってしまってびっくり。