diverta 2019 B-Picking Up 해설

URL


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

문제 개요

  • 2D 평면에 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에서 N으로 최대 수량을 구하여 동일하게 할 수 있다
  • 50C2 = 10^3 좌우 순환, OK
  • 실시 방침

  • 간단한 쓰기
  • 다음의 반성

  • N이 작기 때문에 Naive
  • 를 먼저 고려
  • 사전에서 x*10*9+y를 키로 하고value를 횟수로 하면 O(nC2)입니다.
  • 참고 자료


    https://ami-atcoder.hatenablog.com/entry/20190617/1560747446
    키에서 tapple을 가져올 수 있습니다.

    좋은 웹페이지 즐겨찾기