yukicoder No.202 1円玉投げ 解説

空間を1辺5の正方形で区切り、各正方形にコインが存在するかどうかをboolean配列で管理する。

コインAを(X,Y)に置くためには、(X,Y)から20未満離れた位置にコインの中心が存在しなければよい。

従って周囲25個の正方形についてコインが存在するかどうか調べる。

もしコインがある正方形内に存在するならば、その正方形内について愚直に全探索してコインを探す。

そして見つけたコインがコインAが接触していないか調べる。25個の正方形のうち内部にコインが存在するものは高々9個である。（コインに内接する正方形の敷き詰めを考えればよい）

よって、全探索では高々9*5*5=225箇所を見ることになる。N=10^5だから全体では高々2.25*10^7箇所を見ることになる。

これは十分間に合う。