JOI2008予選D 星座探し

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_d

この問題は全探索を用いて解くことができます。

方針

全探索をします。ただし、平行移動の方法が無数にあるので、候補を限定します。
星座のうちある星に対して、写真中のN個の星のいずれかがマッチする必要があるので、試すべき平行移動はN通りに絞ることができます。よって計算量はO(MN^2)で、十分に間に合います。

さらに、写真中のN個の星をハッシュテーブルで保持しておくことで、O(MN)に削減することが可能です。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
SM = []
SN = []
M = int(input()) # 探したい星座
for m in range(M):
x, y = map(int,input().split())
SM.append((x,y))
N = int(input()) # 星空の写真
for n in range(N):
x, y = map(int,input().split())
SN.append((x,y))
st = set(SN) # inが高速
base = SM[0] # 探したい星座のうち基準となる星を設定
for sn in SN:
dx, dy = sn[0]-base[0], sn[1]-base[1] # 平行移動の方法
ok = True
for sm in SM:
if not (sm[0]+dx, sm[1]+dy) in st: # さらに高速化 O(MN)
ok = False
break
if (ok):
print (dx,dy)
exit()
print (ans)

記事情報

  • 投稿日:2020年5月10日
  • 最終更新日:2020年5月10日