79brue의 PS 블로그

이번 앳코더 ARC에서 6문제를 다 풀어 전체 5등, Rated 중 1등을 하였습니다. 간단한 후기와 문제 풀이를 해볼까 합니다. A. 2nd Greatest Distance 구현과 케이스처리가 매우 복잡한, 400점짜리 문제 치고는 어려운 문제입니다. 다만 아래와 같은 관찰을 통해 구현을 편리하게 줄일 수 있습니다. 각 정점을 x좌표순으로 정렬했을 때 상위 2개 / 하위 2개 점과, y좌표순으로 정렬했을 때 상위 2개 / 하위 2개 점만이 필요하다. 만약 2번째로 긴 체비셰프 거리가 위 정점들로 이루어지지 않는다면, 두 양끝점 중 하나를 위에서 뽑아낸 (최대 8개의) 점들로 대체했을 때 더 긴 해를 얻을 수 있음이 보장되기 때문입니다. 따라서 위와 같이 8개의 점의 후보를 얻어내고, 나이브하게 2번째로..