あと一歩だったけど、本番では解けず。
http://codeforces.com/contest/526/problem/E
問題
N個の整数A[i]が円形に並んでいる(A[N-1]とA[0]が隣接している)。
ここでQ個のクエリに答えよ。
各クエリは1つの整数B[j]で表現される。
円形並んだA[i]を幾つかの(連続した要素による)グループに分け、個々のグループのA[i]の総和がB[j]以下になるようにしたい。
その際の最小グループ数を答えよ。
解法
各B[j]に対し、尺取法などでA[i]+A[(i+1)%N]+...+A[(i+next(i))%N]>B[j]となるnext(i)を全体でO(N)で求めることができる。
最小のnext(i)となるiを考える。
Aをどのように区切っても、A[i]~A[(i+next(i))%N]のどこか1か所は必ず切れ目が来る。
よってA[i]~A[(i+next(i))%N]をそれぞれ始点とし、A[i]を1周分カバーするには何個のグループになるか求めればよい。
B[j]が小さければnext(i)が小さいのでチェックすべき始点が減る。
逆にB[j]が大きければ、next(i)が大きいのでチェックすべき始点は増えるが、1周分の判定が短くて済む(概ねO(sumA/next(i)))。
結局1クエリO(N)で処理できるので、全体でO(NQ)。
int N,Q; ll A[2020000],B; int nex[2020000]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; FOR(i,N) cin>>A[i], A[i+N]=A[i]; while(Q--) { cin>>B; int mi=1<<30; ll sum=0; x=y=0; FOR(i,N) { while(sum+A[x]<=B) sum+=A[x++]; nex[i]=x; if(nex[i]-i>=N) { mi=1; goto out; } if(nex[i]-i<nex[y]-y) y=i; sum-=A[i]; nex[i+N]=min(2*N,nex[i]+N); } for(x=y;x<=nex[y];x++) { int cnt=0; for(i=j=(x>=N)?x-N:x;i<j+N;cnt++) i=nex[i]; mi=min(mi,cnt); } out: cout<<mi<<endl; } }
まとめ
本番はダブリングとかやってしまい間に合わなかった。