GCJ Round3に参加。
Easyをかき集めたけどB-largeが解けず微妙な順位…。
https://code.google.com/codejam/contest/3024486/dashboard#s=p0
問題
N要素の整数配列C[i]があったとする。
先手はこの配列を3つに分割する。たとえばC[0..(a-1)]、C[a..b]、C[(b+1)..(N-1)]に分割するとする。
後手は分割した3つの配列うち要素の和が最大となるものを選ぶ。
残った2つの配列の総和を全体の総和で割った値が先手のスコアとなる。
両者が得られる総和が最大となるよう最適手を取る場合、先手の最大スコアを答えよ。
解法
問題を言い換えるとこうなる。
配列を3つに分割としたとき、総和が最大となる配列の値を最小化せよ。
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]); }
まとめ
これはすんなり解けてよかった。