Google Code Jam 2014 Round 3 : A. Magical, Marvelous Tour

GCJ Round3に参加。
Easyをかき集めたけどB-largeが解けず微妙な順位…。
https://code.google.com/codejam/contest/3024486/dashboard#s=p0

問題

N要素の整数配列C[i]があったとする。
先手はこの配列を３つに分割する。たとえばC[0..(a-1)]、C[a..b]、C[(b+1)..(N-1)]に分割するとする。
後手は分割した３つの配列うち要素の和が最大となるものを選ぶ。

残った２つの配列の総和を全体の総和で割った値が先手のスコアとなる。
両者が得られる総和が最大となるよう最適手を取る場合、先手の最大スコアを答えよ。

解法

問題を言い換えるとこうなる。
配列を３つに分割としたとき、総和が最大となる配列の値を最小化せよ。

a,bを愚直に総当たりするとO(N^2)で先手のスコアが求められるので、そこから最大値を探せばよい。
SmallならN<=1000なのでこれで間に合う。

Largeだとこれでは間に合わない。
先にaを固定したとする。総和の最大値を抑えるには、C[a..b]とC[(b+1)..(N-1)]の総和ほぼ同じ値になるようなbを選べば良い。
これは先にC[a]～C[i]の累積和を取っておくとupper_boundを用いてlogNでbを検索できるので、全体でO(N*logN)で処理できる。

以下では念のためupper_boundで得たbの周辺も若干検索してみた。

ll N,P,Q,R,S;
ll T[1000005];
ll sum[1000005];

void solve(int _loop) {
	int f,i,j,k,l,x,y,a,b;
	
	cin>>N>>P>>Q>>R>>S;
	FOR(i,N) {
		T[i]=(i*P+Q)%R+S;
		sum[i+1]=sum[i]+T[i];
	}
	
	ll ma=0;
	FOR(a,N) {
		ll mid=(sum[N]-sum[a])/2+sum[a];
		ll* p=upper_bound(sum,sum+N+1,mid);
		x=p-sum;
		
		FOR(i,5) {
			b=x+i-2;
			if(b>=a && b<N) {
				ll took=max(max(sum[a],sum[N]-sum[b+1]),sum[b+1]-sum[a]);
				ma=max(ma,sum[N]-took);
			}
		}
	}
	_P("Case #%d: %.12lf\n",_loop,ma/(double)sum[N]);
}

まとめ

これはすんなり解けてよかった。