競プロ初中級者100問

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日