ABC128 F - Frog Jump (600)

概要

0, ..., N-1と番号付けられたN個のハスが横一列にならんでいる。現在ハス0にいる。
正の整数A, Bを選び、0, A, A - B, 2 * A - B, 2 * A - 2 * B, ...の順番で対応する番号のハスを行き来し、最終的にハスN-1に到達したい。ただし、同じハスに2度行くことはできず、また0未満のハスやN-1より大きなハスは存在しない。
ハスiに行くとs[i]点取得できるものとする。このとき得られる点数の最大値を求めよ。ただし、s[0] = s[N-1] = 0 である。

制約

3 ≦ N ≦ 10^5
-10^9 ≦ s[i] ≦ 10^9

方針

A < Bなら2番目の移動で0未満のハスに移動するのでダメ。A = Bなら2番目の移動で0のハスに移動するが、スタートが0であり、同じハスに2回行くことになりダメ。よってA > Bである。

A- B をCとおく。すると移動するハスは0, A, C, A + C, 2 *C, ..., A + k * Cとなる。このとき、A + k * C = N - 1である。kは左に移動する回数 であり、右に移動する回数-1でもある。
A = N -1 - k * Cと変形できるので、移動するハスはk, Cが決まると決まることになる。また、Cを固定してk = k'のときとk=k'+1のときの移動するハスを比較すると、k=k'+1ではN - 1 - (k' + 1) * Cのハスと(k' + 1) * Cのハスが増えていることが分かる。
よって、C, kの2重ループで計算を進める。

kのループの範囲について。
同じハスに移動する場合がある。これはN - 1 + k1 * C = k2 * Cなるk1 > 0, k2 > 0が存在することであるが、式を変形すると(N -1) = (k2 - k1) * Cとなり、すなわちN-1がCで割り切れることが必要である。
どのハスで初めて同じハスに移動するかだが、N-1がCで割り切れる場合、移動するハスはすべてCの倍数になるため、右移動の最小ハスと左移動の最大ハスが重なった地点が初めて同じハスに移動する地点である。そのため、N-1がCで割り切れる場合はk * C >= N - 1 - k * Cとなるkで即座に計算を終了する。
N-1がCで割り切れない場合は、同じハスに移動することがない。ただし、2番目の移動が左移動になる必要があるため、C < N - 1 - k * Cである必要がある。

計算量について。
一見Cとkの2重ループなのでO(N^2)かかるように見えるが、k, Cには小さくともC < N - 1 - k * Cの制約がある。
このときおおまかにはk * C < N が成り立つことになり、各Cに対しkのループはN / Cまでとなる。
すると1 + 1 / 2 + 1 / 3 + ... 1 / N ≦ 1 + log N なので、この設問のC, kの2重ループはO(NlogN)となり、間に合う。

感想

Noiminさんのブログを参考にしました。
noimin.hatenablog.com

解答

Submission #6928059 - AtCoder Beginner Contest 128

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	vector<ll> s(N);
	rep(i, N) cin >> s[i];
 
	ll ans = 0;
 
	for(ll C = 1; C <= N - 1; C++){
		ll sm = 0;
		if((N - 1) % C == 0){
			for(ll k = 1; k * C < N - 1 - k * C; k++){
				sm += s[N - 1 - k * C] + s[k * C];
				ans = max(ans, sm);
			}
		}else{
			for(ll k = 1; N - 1 - k * C > C; k++){
				sm += s[N - 1 - k * C] + s[k * C];
				ans = max(ans, sm);
			}
		}
	}
 
	cout << ans << endl;
 
}