AGC027 B - Garbage Collector

問題

数直線上にn個のゴミがあり、左からi番目は位置a[i]にある
これらを全て位置0にあるゴミ箱に入れたい
ロボットが最初位置0にいて、ゴミをk個持っている状態で距離1だけ移動するには(k+1)^2だけエネルギーを使う
またゴミを1個拾うのと持っているゴミを全てゴミ箱に入れるのにはxだけエネルギーを使う
全てのゴミをゴミ箱に入れるのに必要なエネルギーの最小値を求めよ

解法

ロボットがゴミをゴミ箱に入れる回数k (1<=k<=n) を全部試す
この回数を固定すると、ゴミを拾うのと捨てるのに使うエネルギーは一瞬で求められる ((n+k)x) から考えなくて良くなる
また各往復でのゴミの拾い方は下の画像のように
①ゴミの個数は各往復に均等に割り当てる
②各往復では等間隔のゴミを拾う
③各往復では一番右のゴミを最初に拾い、その後位置0に戻る道中で出会うゴミを順に拾う
のが最善

更に一回の往復でi番目のゴミを拾うときに増えるコストは
i=1) 5
i>1) 2i+1
となることが計算でわかり、これを愚直に一個ずつ計算していけばO(n^2)で部分点、累積和でコストが同じ部分をまとめればO(nlogn)で満点
これ部分点要る？

③は明らか
①②は式変形で証明しようとしたけどよくわからなかった
解説pdfでも省略されてる・・
①は予想しやすいしちょっと実験してみればまあ正しいんだろうなってわかるけど②は直感的にわかるもんなのか？

(2018/9/20追記)
解説放送見たらスッキリした
各座標の係数は右の方ほど小さくするのが明らかに最善で、そうするには②のように割り当てるのが一番良いに決まってる

実装

オーバーフローに気をつける必要がある
ゴミを一個ずつ拾う場合でもコストは5Σa+2nXでせいぜい10^15くらいだから、計算途中でlonglongの範囲を超えるような値が出てきたら即スキップしていい
a*bがオーバーフローしてるかはa*b/b==a?で判別した (オーバーフローするならa*bの時点でおかしな値になるからその後bで割ってもaに戻らない)
↓ではコストが現在の答えの値を超えた時点でもスキップしてる

ll n, x, a[200200], s[200200], res = 1ll<<60;

signed main() {
	cin >> n >> x;
	rep(i,n) {
		cin >> a[i];
		s[i+1] = s[i] + a[i];
	}
	reps(k,1,n+1) {
		ll t = 0, of = 0;
		for (int i=n, j=1; i>=1 && !of; i-=k, j++) {
			ll p = (s[i] - (i-k<0 ? 0 : s[i-k])) * (j==1 ? 5 : j*2+1);
			if (p/(j==1 ? 5 : j*2+1) != s[i] - (i-k<0 ? 0 : s[i-k])) of = 1;
			t += p;
			if (res<=t) of = 1;
		}
		if (!of) chmin(res, t+(n+k)*x);
	}
	cout << res << endl;
}