Codeforces #1012 : Div1 B2. Canteen (Hard Version)

不参加だった回。
https://codeforces.com/contest/2089/problem/B2

問題

整数列A,Bが与えられる。なお、sum(A)≦sum(B)である。
また、整数Kが与えられる。Aの各要素を、負にならないよう合計で最大K回までデクリメントできるとき、以下の最小処理回数を求めよ。

• Aを全要素0になるまで、以下の処理を繰り返す。
  • A[i]とB[i]から、両者の小さい方の値だけ減算する。
  • Aを左シフトする。

解法

C[i]を、A[i]-B[i]のprefix sumとする。
あらかじめA,Bをrotateし、C[i]の最小値が末尾に来るようにしよう。
そうすると、rotateによってA[N-1]が再び正になることはなく、最大N回の処理で終わる。

あとは解を二分探索しよう。

int T;
ll N,K,A[202020],B[202020],C[404040];

int ok(int v) {
	if(v<=0) return 0;
	int i;
	deque<int> D;
	ll sum=0;
	for(i=N-1;i>=0;i--) {
		if(D.size()&&D[0]-i>v) D.pop_front();
		if(D.size()&&N-1-i>=v) sum+=max(0LL,C[D[0]]-C[i]);
		if(sum>K) return 0;
		while(D.size()&&C[D.back()]>C[i]) D.pop_back();
		D.push_back(i);
	}
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N) cin>>A[i];
		FOR(i,N) cin>>B[i];
		ll sum=0;
		ll mi=1LL<<60;
		int tar=0;
		FOR(i,N) {
			sum+=A[i]-B[i];
			if(sum<mi) {
				mi=sum;
				tar=i;
			}
		}
		rotate(A,A+tar+1,A+N);
		rotate(B,B+tar+1,B+N);
		sum=0;
		FOR(i,N) {
			sum+=A[i];
			C[i+1]=C[i]+A[i]-B[i];
		}
		if(sum==K) {
			cout<<0<<endl;
			continue;
		}
		
		int ret=N;
		for(i=20;i>=0;i--) if(ok(ret-(1<<i))) ret-=1<<i;
		cout<<ret<<endl;
	}
}

まとめ

1000ptにしてはちょっとややこしいし、部分点付き1500ptはちょうどいいのかも。