SCPC 후기.

알고스팟/알고리즘 2015.10.31 00:34


일단 일차 예선은 무난히 통과했다.


대회 중에 4번 문제를 푸는데 잼있었는데 

1) 두 점간의 거리가 희한하게 정의되고 (일반 euclidean distance가 아님. 이름 까먹음.. 실제 정의는 공유하면 안될 것 같음.)

2) 한점과 선분의 거리또한 희한하게 정의될 때

3) maximal distance를 minimize하는 점을 찾아라. 라는 문제였는데


일단  선분이 아니라 점의 집합이 주어졌으면 쉽게 풀리는 문제였다. (힌트, 최대, 최소값의 관점에서 생각해보기) 

다만, 어떤 선분의 끝점이 optimal P와의 거리에 이용될 지 미리 모르기 때문에..처음에는 2^n개의 끝점 부분집합을 다 시도해보는 방식으로 했는데 TLE.. 좌절하고 다시 생각해보니 n개의 선분이 주어지면 n+1개의 in between point만 고려하면 된다. 그러면 어떤 끝점이 이용될지는 자동으로 정해지니깐!


이게 신선한 깨닳음 이었다. 2차도 잼있는 문제가 많길!

설정

트랙백

댓글