diverta 2019 2 B - Picking Up解説[python]

URL

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_b

問題概要

• 二次元平面上にN点あり、それらを全てめぐるルートを考える
• 適当にp,q を選び、現在地点から(a-p,b-q)の地点にいくパスはコスト0それ以外の点に行く時はコスト1かかる
• p,qを適切に選んだ時の最小コストを求めよ

制約

$$1 <= N <= 50$$

提出コード

#!/usr/bin/env python3
import sys


def solve(N: int, x: "List[int]", y: "List[int]"):
    ans_max = 0
    dist = []
    for i in range(N):
        for j in range(i + 1, N):
            # x は正にする
            if x[i] - x[j] > 0:
                dist.append((x[i] - x[j], y[i] - y[j]))
            elif x[i] - x[j] < 0:
                dist.append((-x[i] + x[j], -y[i] + y[j]))
            else:  # x == 0 の時は向きに注意
                dist.append((0, abs(y[i] - y[j])))
    for i in range(N * (N - 1) // 2):
        ans_i = 0
        for j in range(N * (N - 1) // 2):
            if dist[i] == dist[j]:
                ans_i += 1
        ans_max = max(ans_max, ans_i)
    print(N - ans_max)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)


if __name__ == "__main__":
    main()

考察

• Nが小さいのでNaiveに考えられそう
• 同じ位置に存在する点がないことからnC2で全ての二点間の相対位置を求め、それが同じになる最大の個数を求めてNからへけばよい
• 50C2 = 10^3 程度で二重ループは回るのでOK

実装方針

• 単純に書くだけ

次回への反省

• Nが小さいからNaive にまず考える
• 辞書でx*10**9 + y とかをkey にしてvalue を回数とかにしてもてばO(nC2)でいけそう。

参考

https://ami-atcoder.hatenablog.com/entry/20190617/1560747446
pythonってタプルをkey に持てるんだ。。