Saiko~ No Contesuto #02 すごろくチキンレース

問題

www.hackerrank.com

解法

簡単な考察により|x-A[0]|+...+|x-A[n-1]|を最小化する問題に帰着できる。|x-A[0]|は凸関数だから|x-A[0]|+...+|x-A[n-1]|も凸関数。だから差分の正負で二分探索すればいい。

これだけじゃ物足りないので解説に書いてあった「|x-A[0]|+...+|x-A[n-1]|の最小値をとるxはAの中央値である」っていうのを証明しておく。

とりあえず微分してみる。といっても愚直に微分するのは大変なので、線形性を使ってバラバラに考えてみる。

図を見ればわかるけど、地点xにおける傾きは（x以下の個数）-（x以上の個数）になることがわかる。つまりx以下の個数とx以上の個数の大小が入れ替わるところが最小値になるはずで、それは中央値に他ならない。

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;

const ll inf = 2e18;

vector<ll> divisor(ll n) {
	vector<ll> res;
	for (ll i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			res.push_back(i);
			if (i != n / i) res.push_back(n / i);
		}
	}
	sort(res.begin(), res.end());
	return res;
}

ll n, m, A[303030];

ll f(ll x) {
	ll res = 0;
	rep (i, m) {
		res += abs(A[i] - x);
	}
	return res;
}

int main() {
	cin >> n >> m;
	rep (i, m) scanf("%lld", &A[i]);

	auto ds = divisor(n);
	int l = -1, r = ds.size() - 1;
	while (r - l > 1) {
		int m = (l + r) / 2;
		ll f1 = f(ds[m]);
		ll f2 = f(ds[m + 1]);
		if (f2 - f1 >= 0) {
			r = m;
		} else {
			l = m;
		}
	}
	cout << f(ds[r]) << endl;
	return 0;
}

コメント

差分の正負を考える二分探索、初期値が何になるのかパッと分からなかったので早く慣れたい。

凸関数から凸関数を作り出す操作

• f,gが凸ならf+gは凸
• f,gが凸ならmax(f,g)は凸
• f,gが凸かつgが単調増加ときg(f(x))は凸
• f,gが対数凸ならfgは対数凸

ちなみに一次関数ax+bも実は凸関数なので、max(ax+b,cx+d)は凸関数。

1つ目は今回使った操作。
2つ目を使えばmax(a[0]x+b[0],a[1]x+b[1],...,a[n-1]x+b[n-1])が凸だとすぐわかる。
3つ目は2^|x-3|とか。
4つ目は2^|x-3|*3^|x-2|とか。