AtCoder ARC #117 : F - Gateau

シンプルな問題なんだけどな。
https://atcoder.jp/contests/arc117/tasks/arc117_f

問題

2N個のピースが円形に並んだケーキがある。
各ピースにいくつかイチゴを載せたい。

ここで、各半円に何個以上イチゴを載せる、という条件が与えられる。
条件を満たす載せ方のうち、総イチゴ数の最小値を求めよ。

解法

二分探索で求める。
まず、円形を扱うのは面倒なのでこれをやめよう。
各ピースのイチゴ搭載量を示す長さ2Nの配列Xとその累積和Sを考える。二分探索の仮の解をTとする。
ピース[i,i+N-1]の間の総和がA[i]以上である場合、それはS[i+N-1]-S[i-1]≧A[i]と簡単な式で書ける。
一方(i+N-1)が2N以上になる場合は、ピース[i,2N-1]と[0,(i+N-1)%2N]の総和がA[i]以上であるという条件は、T-A[i]≦S[i]-S[i-N]と、上記同様にSのN区間に関する条件としてかける。

S[N]-S[0]の値を定めたとき、そこから連鎖的にS[N+i]-S[i]の値を決めていくことができる。
問題はS[N]-S[0]を何にするかだが、S[N]を大きくしすぎると最終的にS[2N]がTを超えてしまうし、S[N]を小さくしすぎるとS[2N-1]とS[2N]の大小関係が矛盾を起こす。
そこで、S[N]も二分探索しよう。

二分探索の中で二分探索するので割とややこしい。

int N;
ll A[603030];
ll S[603030];
ll L[151515],R[151515];
ll TS[303030];

pair<int,int> check(ll SN,ll X) {
	TS[0]=0;
	TS[N]=SN;
	int i;
	for(i=1;i<N;i++) {
		ll PS=TS[i+N-1]-TS[i-1];
		if(L[i]<=PS&&PS<=R[i]) {
			TS[i]=TS[i-1];
			TS[i+N]=TS[i+N-1];
		}
		else if(PS<L[i]) {
			TS[i]=TS[i-1];
			TS[i+N]=TS[i-1]+L[i];
		}
		else {
			TS[i]=TS[i+N-1]-R[i];
			TS[i+N]=TS[i+N-1];
		}
	}
	return {TS[2*N-1]<=X,TS[N-1]<=TS[N]};
}

int ok(ll X) {
	int i;
	FOR(i,N) {
		L[i]=A[i];
		R[i]=X-A[i+N];
		if(L[i]>R[i]) return 0;
		
	}
	ll TL=L[0],TR=R[0];
	auto p=check(TL,X),q=check(TR,X);
	if(p.first&&p.second) return 1;
	if(q.first&&q.second) return 1;
	if(p.first==0) return 0;
	if(q.second==0) return 0;
	while(TL+1<TR) {
		ll M=(TL+TR)/2;
		auto v=check(M,X);
		if(v.first&&v.second) return 1;
		if(v.first) TL=M;
		else TR=M;
	}
	
	p=check(TL,X),q=check(TR,X);
	if(p.first&&p.second) return 1;
	if(q.first&&q.second) return 1;
	return 0;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
	}
	
	ll ret=(1LL<<40)-1;
	for(i=39;i>=0;i--) if(ok(ret-(1LL<<i))) ret-=1LL<<i;
	cout<<ret<<endl;
}

まとめ

二分探索は思いついても、そこから詰めていくのが大変。