「JOI2007本戦C 最古の遺跡」を解いてみた

目的

• Atcoderで上を目指すべく、「競プロ初中級者100問」を解いている中で面白い問題に当たったので共有する
  • 言語はpython3系(pypy7.3 or python3.8.5)を利用している

qiita.com

問題

• 要約: 複数(最大3000個)の点(x,y)が与えられ、それら4つで正方形が作れるか、いくつか作れる場合はその面積の最大値を求める
  • JOI = 日本情報オリンピック

atcoder.jp

ポイント

計算量に関して

単純な全探索でなく、問題の条件/性質より探索範囲を絞り込む必要がある

• 点は最大3000個与えられるため、組み合わせ(nC4)で全部の点の組み合わせを求めることは不可能(計算量的にはO(n⁴))

  • n=3000の場合「3,368,254,124,250 通り」あるため、制限時間内に実行完了することは出来ない

• そのため、正方形である性質を利用し、4つの点ではなく、2点のみ求め、残りの2点が存在するかを求める

  • この場合は、計算量はO(n²)となり制限時間内に実行可能になる
    • n=3000の場合「4,498,500通り」
  • 点が存在する場合の探索は、さほどコストにならない

正方形の性質

• 計算量に関しては、下記等でも解説されてはいるが、正方形の性質に関して少し深く考える

kakedashi-engineer.appspot.com

• 図1. のように、点p1, p2を決定した場合、p3, p4の座標はそれぞれ下記のようにp1, p2のx, y座標の情報を用いて求めることができる
  • 入力座標にsortをかけた場合には、下記の2パターン(p2のy座標がp1のy座標よりも大きい or 小さい)があるが、全ての2点に関して探索するため、どちらか好きな方で考えれば良い

図1. 正方形

• ちなみに、pythonの2次元配列をsortすると下記のようになる

N = int(input())
P = []

for _ in range(N):
    x, y = map(int, input().split())
    P.append((x, y))

# ここでsortする
P.sort()

print(P)

# sortなし
[[9, 4], [4, 3], [1, 1], [4, 2], [2, 4], [5, 8], [4, 0], [5, 3], [0, 5], [5, 2]]


# sortあり
[[0, 5], [1, 1], [2, 4], [4, 0], [4, 2], [4, 3], [5, 2], [5, 3], [5, 8], [9, 4]]

listの計算量に関して

• 最初は何も考えずに、listを利用し list_a in list_A で判定していたが、配列検索O(N)になってしまうので TLE に・・・
  • ref: https://atcoder.jp/contests/joi2007ho/submissions/20217782

from itertools import combinations
 
N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]
P.sort()
 
C = combinations(P, 2)
ans = 0
 
for p1, p2 in C:
    x1, y1 = p1
    x2, y2 = p2
 
    p3 = x1 + y1 - y2, y1 + x2 - x1
    p4 = x2 + y1 - y2, y2 + x2 - x1
 
    if list(p3) in P and list(p4) in P:
        ans = max((x2 - x1) ** 2 + (y2 - y1) ** 2, ans)
 
print(ans)

• set型かdict型でO(1)で検索する必要がある
  • 結構この辺の仕様が、意識から抜けてた・・・非常に恥ずかしいミス

qiita.com

• set型を利用しAC(解けた)
  • ref: https://atcoder.jp/contests/joi2007ho/submissions/20217838

from itertools import combinations

N = int(input())
P = []

for _ in range(N):
    x, y = map(int, input().split())
    P.append((x, y))

P.sort()

C = combinations(P, 2)
ans = 0
st_P = set(P)

for p1, p2 in C:
    x1, y1 = p1
    x2, y2 = p2

    p3 = x1 + y1 - y2, y1 + x2 - x1
    p4 = x2 + y1 - y2, y2 + x2 - x1

    if p3 in st_P and p4 in st_P:
        ans = max((x2 - x1) ** 2 + (y2 - y1) ** 2, ans)

print(ans)

• ちなみに、 x in set は早いが、それ以上にlistをsetに変換することが、 x in list より低速であるため、注意が必要
  • set変換を毎回行うとかだと、非常に低速になる
  • 1,2回とかしか使わないなら、setへの変換コストが大きいのでlistのまま利用した方が良い

qiita.com

pypyの利用メモリに関して

• メモリ制限に引っ掛かりpypyでは通らない・・・64MBと通常のAtcoderの条件よりも厳しいため(Atcoderでは256MB)

  • ref: https://atcoder.jp/contests/joi2007ho/submissions/20217840

• 基本的にpypyの方が高速であるが、メモリを多く喰うことがAtcoderを解いていて見受けられる

  • python3の方が速い場合もある、順列の計算で標準ライブラリを使った場合もわずかにpython3の方が早かったりした

stackoverflow.com

qiita.com

学び

• dict/setの検索は爆速、listはクソ遅いという仕様の再認識
• pypyメモリ喰いがち(下記の情報もあり場合よりけり？ ただ、Atcoderで書く50行以下のscriptでは喰いがち)

dev.nextthought.com

• まだまだ、勉強が足らない・・・

github.com