kmjp's blog

競技プログラミング参加記です

Zepto Code Rush 2015 : E. Transmitting Levels

あと一歩だったけど、本番では解けず。
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;
	}
}

まとめ

本番はダブリングとかやってしまい間に合わなかった。