読者です 読者をやめる 読者になる 読者になる

yukicoder No.202 1円玉投げ

久々に問題を解いた。JOI本選(オンライン参加ですが)も近いので、ある程度はやっておこう。

問題概要

N個の半径10の円形コインを投げる。投げた時にコインが重なるようであればそれを取り除く。

N個のコインの中心座標が与えられるので、N回投げた後いくつコインがあるか求めよ。

No.202 1円玉投げ - yukicoder

解法

N≦100,000だから2重ループで過去のコインの位置を全て探っていたら終わらない。ということで調べるものの数を減らす。

コインの中心が(x,y)の時、ユークリッド距離で20未満の範囲に別の頂点が有ってはならないので、調べる範囲はx-20〜x+20、y-20〜y+20の正方形の範囲で十分である。

よって予めsetで置いてある頂点を管理して、lower_boundなり使えばよい。xの順にソートされているとき、y+20を超えたらそのxでは考えなくていいので再度lower_boundを用いないとTLEする気がする。

http://yukicoder.me/submissions/74446

感想

setのiteratorってインクリメント出来たんだ…(出来ないと思ってupper_bound用いてTLEした)

因みにGitHubを使い始めたので、ソースコードはこれ、もしくは回答ページを使ってリンクを貼るつもりです。文量が長くなって読みにくいことに気がついたので。