kmjp's blog

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

yukicoder : No.869 ふたつの距離

これ実装は簡単なので、解説有だと★5にしてはだいぶ楽なんだけど、あまり解かれていないな。
https://yukicoder.me/problems/no/869

問題

整数N,A,Bが与えられる。
2次元座標上で、(格子点でなくてもよいので)以下の条件を満たすようN個の頂点を配置せよ。

  • 頂点対のうち点の距離が10以下となるのがA通り
  • 頂点対のうち点の距離が20以下となるのがB通り

解法

乱数を使って微調整することを考える。
まず、y座標=0のところにU個、y座標=YのところにV個点を配置するとする。
この際、U+V=Nで、かつYは10より大きいとする。
とすると、距離が10以下となる頂点対は前者のグループ同士か後者のグループ同士になる。

これらを適当に配置しよう。
まず両グループそれぞれのX座標について考える。
先に0~0.0001以下の乱数列Tを生成しておく。
i番目の点とi+1番目の点は、R+T[i]個X座標が離れる、という配置にすることとし、距離10以下の点がA組となるようなRを二分探索する。

この際、入力のAの条件より、両グループのX座標の範囲は20以下に収まる。
すなわち、同グループ内の頂点は必ず距離が20以下である。

次にY座標を適切に設定することで、距離20以下の点がB個となるよう調整しよう。
これは二分探索でもいいし、両グループの頂点間で、距離が20となるようなY座標の候補を列挙し、ソートしてもよい。
ここで乱数を使ったのが活きてきて、Y座標の候補はU*V通りあるがちゃんと乱数を散らせばこれらは異なる値になるので、必ず条件を満たすY座標の値がある。

int N,A,B;

long double getrandom() {
	int a=rand()%10000;
	int b=rand()%10000;
	return (a*10000+b)/10000000000.0;
}

vector<long double> hoge(int n,int p) {
	vector<long double> T;
	T.push_back(getrandom());
	while(T.size()<n) T.push_back(T.back()+getrandom());
	if(n<2) return T;
	long double L=0,R=17.3/(n-1);
	int i,x,y;
	FOR(i,100) {
		long double M=(L+R)/2.0;
		int num=0;
		FOR(y,n) FOR(x,y) if((T[y]+y*M)-(T[x]+x*M)<=10) num++;
		if(num>=p) L=M;
		else R=M;
	}
	
	FOR(i,n) T[i]+=L*i;
	return T;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	srand(time(NULL));
	cin>>N>>A>>B;
	int U,V;
	for(U=1;U<=N;U++) {
		V=N-U;
		if(U>=V && U*(U-1)/2+V*(V-1)/2>=A) break;
	}
	x=A*1.0*U*(U-1)/(U*(U-1)+V*(V-1))+0.5;
	y=A-x;
	B-=U*(U-1)/2+V*(V-1)/2;
	vector<long double> S=hoge(U,x);
	vector<long double> T=hoge(V,y);
	vector<pair<long double,long double>> R;
	vector<double> C;
	FORR(s,S) FORR(t,T) {
		C.push_back(sqrt((long double)400-(t-s)*(t-s))-0.000000001);
	}
	sort(ALL(C));
	reverse(ALL(C));
	FORR(s,S) R.push_back({s,C[B-1]});
	FORR(t,T) R.push_back({t,0});
	
	/*
	int num[2]={};
	FORR(x,R) FORR(y,R) if(x<y) {
		long double a=x.first-y.first;
		long double b=x.second-y.second;
		if(a*a+b*b<=100.0000000000) num[0]++;
		if(a*a+b*b<=400.0000000000) num[1]++;
	}
	_P("%d %d %d\n",N,num[0],num[1]);
	assert(num[0]==A);
	assert(num[1]==B+U*(U-1)/2+V*(V-1)/2);
	*/
	FORR(r,R) _P("%.12lf %.12lf\n",(double)r.first,(double)r.second);
	
}

まとめ

乱数を微調整に使うのが面白いな。