星座探し(08予選4) - olpheの競プロ帖

最大で200個(M個)の星からなる星座の位置と、最大で1000個(N個)の夜空の星の位置が与えられる。

星座の情報からどれだけ平行移動すれば実際の夜空で星座を見つけられるかな、という問題。(必ず一通りの解があることが保証されている)

愚直にやろうとすると1000通りの平行移動を試し、任意の星と星座の星が一致するかどうかを調べる必要があるので、O(MN^2)かかるっぽいので短縮したい(今なら多分通りそうな気はするが)

星座の情報と、夜空の情報を入れるsetを用意する。

x,yのまま扱うのは面倒なので一変数に直します。

そして、星座の一番小さな座標の星から、夜空に対応する星があるかどうか調べる。

するとO(MNlogN)となるので間に合う

難易度は6程度であるように感じられた。