SRM 281 DIV1 Hard Equidistance

問題 Editorial

問題

数列initialが与えられる。
これの各々を移動させて、等差数列の並び替えにしたい。ただしそれぞれの数値は重複があってはいけない。
移動させるのに移動させた分だけコストがかかる。
コストを最小化せよ

• 2 <= |initial| <= 50
• -2*10^9 <= initial[i] <= 2*10^9

解答

Editorialを見た。
まず、数列をソートできる。
そうすると、等差数列の順序はそのままの順序でよくなる。
次に、どれかの数1つはそのままの位置で良い。
そうすると、コストは等差の関数(d => Σ |v[fixed] + d * (j - fixed) - v[j]|)になる。
そしてこの関数は凸である。何故ならば、Sumの各項は凸で、任意の凸関数の非負係数の線形結合は凸になるからである。
凸ならば、二分探索で答えが出る

コメント

まずソートするというのは普通に考えよう。それによって順序が決めることのできることもある。
「任意の凸関数の非負係数の線形結合は凸」は当たり前だけれども、その形に注意して見てみよう。

コード

#include <vector>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(o) (o).begin(), (o).end()
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef long long ll;

struct Equidistance {
	vi v; int n;
	ll effort(int i, ll d) {
		ll r = 0;
		rep(j, n) r += abs((ll)v[i] + d * (j - i) - v[j]);
		return r;
	}
	long long minimumEffort(vector <int> initial) {
		v = initial, n = v.size(), sort(all(v));
		ll r = INFL;
		rep(i, n) {
			ll l = 1, u = 4000000001LL;
			while(u-l>1) {
				ll mid = (l+u)/2;
				(effort(i, mid) - effort(i, mid-1) <= 0 ? l : u) = mid;
			}
			r = min(r, effort(i, l));
		}
		return r;
	}
};