AtCoder ABC #128 : F - Frog Jump

今日の投稿数がすでに10だ。
https://atcoder.jp/contests/abc128/tasks/abc128_f

問題

0～(N-1)番のマスがある。
各マスiにはスコアS[i]が設定されている。

今駒が0番のマスにあるとする。
正整数A,Bを指定すると、以下の2手を交互に繰り返す。

• 駒を現在位置+Aの位置に動かす。(N-1)番のマスに到達したら終了。
• 駒を現在位置-Bの位置に動かす。(N-1)番のマスに到達したら終了。

なお、途中で0番未満のマスやN番以降のマスに行こうとしたり、同じマスに2回駒を置くことはできない。

最適なA,Bを選択したとき、止まったマスのスコアの総和の最大値を求めよ。

解法

A=N-1でない場合、0＜B＜A＜N-1でないといけないことは明らかである。
そこで、A-B=Dとし、このDを総当たりしよう。

止まるマス数が2x個であるとすると、泊まるマスは
0,D,2D,...,(x-1)DおよびN-1,N-1-D,N-1-2D,...,N-1-(x-1)Dである。
よってこれらの総和が最大となるxを求めよう。
これは単純に徐々にxを大きくしていけばよい。

なお、両者に共通するマスがあったり、xD≧N-1であるケースは範囲外のマスを経由したり同じマスを2回経由することに相当するので除外すること。

int N;
ll S[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	ll ret=0;
	for(int D=1;D<=N-1;D++) {
		
		ll sum=0;
		int L=0,R=N-1;
		if((N-1)%D==0) {
			while(L<R) {
				sum+=S[L]+S[R];
				ret=max(ret,sum);
				L+=D;
				R-=D;
			}
		}
		else {
			while(L+D<N-1) {
				sum+=S[L]+S[R];
				ret=max(ret,sum);
				L+=D;
				R-=D;
			}
			
		}
		
	}
	
	cout<<ret<<endl;
}

まとめ

EのグダグダSegTreeバグのせいで、こっちの方がはるかにすんなりだった。