yukicoder : No.202 1円玉投げ

★２か３か迷うところだけど。
http://yukicoder.me/problems/476

問題

2次元座標上にN個の1円玉を順に置いていく。
ただし1円玉を置いたとき他の1円玉と重なってしまうとき、その1円玉は置かない。
1円玉の半径は10であるとする。

各1円玉を置く位置を(X[i],Y[i])としたとき、置ける1円玉の数はいくつか。

解答

1円玉を置く際、周辺半径20未満の円内に他の1円玉がないか判定すればよい。

X,Yは0～20000の範囲まであるので、各座標に1円玉があるかないか20000*20000要素の配列を作るとMLEする。
最大でも1円玉は10^5しかないので、set等を使って管理すると良い。

int N;
int X[101000],Y[101000];

set<int> S[20200];
int ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		int ok=1;
		for(x=max(0,X[i]-19);x<=min(20000,X[i]+19) && ok;x++) {
			int dy=sqrt(399-(x-X[i])*(x-X[i])+0.0001);
			for(y=max(0,Y[i]-dy);y<=min(20000,Y[i]+dy);y++) if(S[x].count(y)) ok=0;
		}
		if(ok) ret++, S[X[i]].insert(Y[i]);
	}
	cout<<ret<<endl;
}

まとめ

★2.5位？