ABC128F: Frog Jump

https://atcoder.jp/contests/abc128/tasks/abc128_f

超良問。

A-B=Cとして場合分けします。

(i)(N-1)%C != 0のとき
0, C, 2C, 3C, ..., kC
N - 1, N - 1 - C, N - 1 - 2C, N - 1 - 3C, ..., N - 1 - kCと取ることができます。

(ii)(N-1)%C==0のとき
(i)とだいたい同様ですが、取る場所がかぶってはいけないので、kC < N - 1 - kCが成り立つkについて取ることができます。

Cとkすべて試すとO(N(1 + 1/2 + 1/3 + ...)) = O(NlogN)です。

ちなみに(i)(ii)よりN-1に減点なしで到達できるA,Bの必要十分条件は
A <= floor(N/2)のとき、N-1=A(mod A-B), N-1≠0(mod A-B)
A > floor(N/2)のとき、N-1=A(mod A-B)
です。最初はこっちの条件から解こうとしました。

int N;
ll D[MAX_N];

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> D[i];
	ll res = 0;
	rep(k, 1, N - 1) {
		if((N - 1) % k == 0) {
			ll tmp = 0;
			for(int i = 0; i < N - 1 - i; i += k) {
				tmp += D[i]; tmp += D[N - 1 - i];
				MAX(res, tmp);
			}
		}
		else {
			ll tmp = 0;
			for(int i = k; i < N - 1 - k; i += k) {
				tmp += D[i]; tmp += D[N - 1 - i];
				MAX(res, tmp);
			}
		}
	}
	cout << res << "\n";
}