yukicoder : No.180 美しいWhitespace (2)

想定解のはずの解法をバグで通せず、別解で力技で解いた。
http://yukicoder.me/problems/425

問題

N個の整数対(A[i],B[i])が与えられる。

を最小化できる正整数xのうち、最小のxを求めよ。

解法

xが増加するにつれ、maxの項のB[i]は大きくなり、minの項のB[i]は小さくなる。
よって、全体としてf(x)は下に凸な関数になる。
そのためWrite解説によると二分探索や三分探索で求められる。

自分は最初三分探索で書いたが、多くのxで最小値が一致するケースでWAを出してしまったので別解法でチャレンジ。
二次元座標上で、となる直線がN本あるので、一番下もしくは一番上に来る直線が入れ替わる(=交差する)ようなxを求め、そのx周辺についてf(x)を計算した。
一番下・上に来る直線が入れ替わるのは高々N回なので、f(x)を求めるのもO(N)回で済み、全体でO(N^2)で済む。

Nが小さいので、一番下・一番上の直線を求めるのは愚直にO(N^2)箇所の交点を求めても間に合う。
convex hull trickでも行けるけど、そこまでする必要はないでしょう。

int N;
ll X[1010],Y[1010];
ll ret;
ll m=1LL<<60;
double cr[1010][1010];

void val(ll x) {
	ll ma=0,mi=1LL<<60;
	int i;
	if(x<1) return;
	FOR(i,N) ma=max(ma,Y[i]*x+X[i]) , mi=min(mi,Y[i]*x+X[i]);
	if(ma-mi<m || (ma-mi==m && x<ret)) m=ma-mi,ret=x;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	
	FOR(x,N) FOR(y,N) cr[x][y] = (Y[x]==Y[y]) ? -1 : (X[y]-X[x])*1.0/(Y[x]-Y[y]);
	
	set<double> S;
	S.insert(1);
	
	FOR(i,2) {
		x=0;
		FOR(y,N) {
			if(i==0 && ((X[y]<X[x]) || (X[y]==X[x] && Y[y]<Y[x]))) x=y;
			if(i==1 && ((X[y]>X[x]) || (X[y]==X[x] && Y[y]>Y[x]))) x=y;
		}
		for(double xx=0;;) {
			int ne=x;
			double mi=1e10;
			FOR(y,N) if(cr[x][y]>xx && cr[x][y]<mi) ne=y, mi=cr[x][y];
			if(mi>=1e10) break;
			S.insert(mi);
			xx=mi;
			x=ne;
		}
	}
	
	ITR(it,S) for(i=-2;i<=2;i++) val(*it+i);
	
	cout<<ret<<endl;
}

まとめ

三分探索苦手意識が強い…。