kmjp's blog

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

AtCoder ARC #011 : D - きつねさんからの挑戦状

さて、なんかインチキっぽい解法で通ってしまった問題。
http://arc011.contest.atcoder.jp/tasks/arc011_4


2次元座標上で、点の位置と最寄の道路と最寄の住居で決まる評価関数が最大となる値を求める。

本番、道路数Nと住居数Mが少ないので、なんかビットDPでもやるのかな…と迷ったり。
最初道路と住居それぞれでボロノイ図を作って、その中の最大値を求めようか…と思ったけどボロノイ図をすんなり作れなさそうなので早々にあきらめ。

ダメ元で、大雑把にアタリを付けて、後はその周辺を絞る方法を取った。
4回WAしてるけど、初回で大体正解して、後はTLE,WAした問題に向けて絞り方のパラメータをいじっただけだね。

一応考えはあって、距離が離れると住居、距離が近いと道路の評価が効いてくるので、R>100なら座標を2毎に区切って最初の候補を探し、それ以下なら0.1単位で探す、とした。

Rが大きいとき1ずつ区切るとTLEした例があるし、Rが小さいときは探索範囲を絞らないとWAした。

int N,M,R;
int A[30],B[30],C[30];
int P[30],Q[30];


double ps(double x,double y) {
	double rsc=100000;
	int i;
	FOR(i,N) rsc=min(rsc, abs(A[i]*x+B[i]*y+C[i])/sqrt(A[i]*A[i]+B[i]*B[i]));
	double sc=1e10;
	FOR(i,M) sc=min(sc, (x-P[i])*(x-P[i])+(y-Q[i])*(y-Q[i]));
	
	return rsc+sc;
}

void solve() {
	int f,r,i,j,k,l;
	int x,y,mx,my;
	double sx,sy,tx,ty,tmx,tmy,ma,sc;
	double msc;
	GET3(&N,&M,&R);
	
	FOR(i,N) GET3(&A[i],&B[i],&C[i]);
	FOR(i,M) GET2(&P[i],&Q[i]);
	
	msc=0;
	if(R>100) {
		for(y=-R;y<=R;y+=2) for(x=-R;x<=R;x+=2) {
			sc=ps(x,y);
			if(sc > msc) msc=sc,sx=x,sy=y;
		}
	}
	else {
		for(ty=-R;ty<=R;ty+=0.1) for(tx=-R;tx<=R;tx+=0.1) {
			sc=ps(tx,ty);
			if(sc > msc) msc=sc,sx=tx,sy=ty;
		}
	}
	
	double step=0.05;
	FOR(l,50) {
		ma=0;
		for(y=-100;y<=100;y++) {
			ty=sy+y*step;
			if(ty<-R || ty>R) continue;
			for(x=-100;x<=100;x++) {
				tx=sx+x*step;
				if(tx<-R || tx>R) continue;
				sc=ps(tx,ty);
				if(sc>ma) {
					ma=sc; tmx=tx; tmy=ty;
				}
			}
		}
		
		sx=tmx;
		sy=tmy;
		step = step / 2.0;
	}
	
	_P("%.10lf\n",ps(sx,sy));
	
	return;
}

まとめ

他の正解者2名はちゃんと幾何的に解いているようだ。
こんな方法で解いていいのかなぁと思いつつ、力技もたまにはいいよねとも思う。