PS 이야기

문제에 중요한 명제가 있다. 주어진 $N$개의 점들을 모두 덮는 최소 크기의 정사각형으로, $N$개의 점을 모두 덮을 수 있는 최소 두께의 정사각형 액자를 만들 수 있다.문제 설명에 따르면 위 명제는 이미 증명된 사실이며, 이 조건 없이 문제를 해결하기는 매우 힘들다. $w \leq w'$ 일 때, 두께 $w$가 모든 점을 덮으면 두께 $w'$도 모든 점을 덮을 수 있다. 따라서 답을 binary search로 구할 수 있다. 우선, 편의상 $max_x-min_x \leq max_y-min_y$ 라 하자.그러면 액자의 바깥 정사각형의 한 변 길이 $S = max_y-min_y$ 임과 동시에 액자 위의 y좌표와 아래의 y좌표가 결정된다. 이제 두께 $w$가 답이 될 수 있는지 확인해야한다.이 때, 여러가지..

문제 설명에 의해 이벤트 $E_i$와 이벤트 $E_j$가 답이 요구하는 집합에 같이 있을 수 없는 조건은,$s_i + d_i + t_{i,j} \leq s_j$ 또는 $s_j + d_j + t_{j,i} \leq s_i$문제에 있는 조건 $t_{i,j} \leq t_{i,k} + t_{k,j}$ 에 의해서, 다음과 같은 정리가 성립한다.$E_i$와 $E_j$가 같은 집합 안에 있을 수 없고, $E_j$와 $E_k$가 같은 집합 안에 있을 수 없으면, 항상 $E_i$와 $E_k$도 같은 집합 안에 있을 수 없다.위 정리가 성립하므로, 이 문제를 이분 그래프의 Minimum Cut으로 해결할 수 있다. 우선, 이분 그래프의 왼쪽과 오른쪽에 각각 $n$개의 $E_i (1 \leq i \leq n)$ 들을 배치..

대한민국 ICPC 문제들은 데이터와 솔루션이 공개되지 않는다. 때문에 온라인 저지에서 한국 ICPC 문제들을 보기 힘들다. Baekjoon Online Judge 에서 간혹 한국 ICPC 문제들이 보인다. 어둠의 경로(?)로 데이터를 입수하는 방식이 아닌 관리자 혹은 회원이 데이터를 직접 만들어서 등록하는 방식으로 진행되는 것 같다. 그 곳에서 인터넷 예선 공부하기 너무 편했고, 그에 보답하기 위해 이번 인터넷 예선 데이터들을 만들어 보았다. 시간 날 때 마다 만든다고 시작한 것이 하다보니, 상당히 많은 문제들의 데이터를 만들게 되었다. 과거 KOI 준비하면서 내 솔루션이 맞는지 검증하기 위한 프로그램을 C++로 코딩했었는데, 최근 들어서 python으로 하면 굉장히 편하다는 것을 느꼈다. KOI는 이제..