CODE FESTIVAL 2018 Qual A : E - オレンジとみかん

こういう一見シンプルな問題は、既存テクが使いまわしにくくて苦手。
https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_e

問題

オレンジがX個、みかんがY個あり、それをN人で分ける。
(X+Y)がNの倍数なので、皆もらうオレンジとみかんの和は等しくできることが保障される。
i番の人は、オレンジ1個あたり満足度がA[i]、みかん1個あたり満足度がB[i]増加する。

最適にオレンジとみかんを分けた場合、N人の満足度の最大と最小値の差を最小化せよ。

解法

二分探索で解く。
解の候補をDとする。

各人がもらう果物の数をS=(X+Y)/Nとおく。
N人の最小値がNとすると、i番の人がもらうオレンジをx個とすると、満足度はL≦A[i]*x+B[i]*(S-x)≦L+Dとなり、それを満たすxの範囲が求まる。
また、条件を満たすxが1つもない人の人数をpとし、それ以外の各人のxの最小値の総和をmin(L,D)、xの最大値の総和をmax(L,D)とする。
p==0かつmin(L,D)≦X≦max(L,D)であれば、Dを満たす配分が存在する。

今回Dを二分探索するのだが、その際上記判定にはLを動かさないといけない。
Lを小さい順に動かしていくことを考える。
ただ、Lを動かした場合p,min(L,D),max(L,D)が変化するのは、

• A[i]*x+B[i]*(S-x)=Lを満たすiおよび0≦x≦Sが存在するとき、Lをそれより増やす
• A[i]*x+B[i]*(S-x)=L+Dを満たすiおよび0≦x≦Sが存在するとき、Lがそれより小さい時からこれを満たす値になる

のいずれかである。
これらは大よそO(SN)=O(X+Y)なので、何とか間に合う。

なお、Editorial通り解いた自分の解は1.9sで、Writer解は443msである。
これは自分は二分探索過程で毎回上記Lの候補をソートしたのに対し、Writer解はA[i]*x+B[i]*(S-x)=Lを満たすi,xを初回にソートしておき、～～～=L+Dを満たすi,xはソートせず前者の(i,x)の数列を尺取り法しているためである。
Editorialを素直に実装しても自分のようにTLEスレスレになる可能性があるので注意。

int X,Y,N,S;
ll A[202020],B[202020];

int LB[202020],RB[202020],NG[202020],TNG;
int TLB,TRB;

vector<pair<ll,ll>> ev;

int ok(ll d) {
	int i,j;
	
	ev.clear();
	TLB=TRB=TNG=0;
	
	FOR(i,N) {
		LB[i]=X+Y+1;
		RB[i]=-1;
		
		FOR(j,S+1) {
			ll tot=A[i]*j+B[i]*(S-j);
			
			if(0<=tot && tot<=d) {
				LB[i]=min(LB[i],j);
				RB[i]=max(RB[i],j);
				ev.push_back({tot+1,(1LL*i<<30)+(j*2)});
			}
			else if(tot>d) {
				ev.push_back({tot-d,(1LL*i<<30)+(j*2)+1});
				ev.push_back({tot+1,(1LL*i<<30)+(j*2)});
			}
		}
		if(LB[i]<X+Y+1) {
			TLB+=LB[i];
			TRB+=RB[i];
			NG[i]=0;
			
		}
		else {
			NG[i]=1;
			TNG++;
		}
	}
	
	sort(ALL(ev));
	ll pre=-1;
	FORR(e,ev) {
		if(pre!=e.first) {
			if(TNG==0 && TLB<=X && X<=TRB) return 1;
		}
		pre=e.first;
		int add=e.second&1;
		int x=(e.second>>30);
		int y=(e.second>>1)&((1<<29)-1);
		
		if(NG[x]==0) {
			TLB-=LB[x];
			TRB-=RB[x];
		}
		if(add==0) {
			// rem
			if(RB[x]==y) RB[x]--;
			if(LB[x]==y) LB[x]++;
			
			if(NG[x]==0 && LB[x]>RB[x]) {
				NG[x]=1;
				TNG++;
			}
		}
		else {
			// add
			if(NG[x]) {
				TNG--;
				NG[x]=0;
				LB[x]=RB[x]=y;
			}
			if(y==LB[x]-1) LB[x]--;
			if(y==RB[x]+1) RB[x]++;
		}
		if(NG[x]==0) {
			TLB+=LB[x];
			TRB+=RB[x];
		}
	}
	if(TNG==0 && TLB<=X && X<=TRB) return 1;
	
	return 0;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y>>N;
	FOR(i,N) cin>>A[i]>>B[i];
	S=(X+Y)/N;
	
	ll D=(1LL<<47)-1;
	for(i=46;i>=0;i--) if(ok(D-(1LL<<i))) D-=1LL<<i;
	cout<<D<<endl;
	
}

まとめ

本番Lの総当たりは何を勘違いしたかO(N(X+Y))と思ってしまった…。