PS 이야기

링크: https://code.google.com/codejam/korea/ 구글 코드 잼은 다들 잘 알 것이다. 구글 코드잼 한국 대회가 2012년에 딱 한 번 열렸다.2013년도에도 열리길 기대했었지만, 내가 알 수 없는 이유로 열리질 않았다. 우연히 기회가 되어 Google Codejam Korea 2012에 참가했다.1년도 지난 일이라 당시 상황이 잘은 기억이 나질 않는다.예선 라운드는 그럭저럭 코딩이 빨리 되어 2등을 했었고,1차 본선 때는... 말렸었던 것으로 기억한다.여러 문제로 1차 본선은 무효처리 되고, 2차 본선이 열리게 되었다. 2차 본선 때는 그리 컨디션이 좋진 못했지만, C번 문제가 평소 즐겨 풀던 매칭 문제가 나와 무난하게 해결하여 패널티가 낮은 덕분에 결선에 진출할 수 있었다...

문제 설명은 매우 긴 반면에 문제는 매우 간단하게 풀 수 있다. 판도라(로봇)가 가리킬 수 있는 방향은 상,하,좌,우 뿐이다. 처음 시작 방향은 중요하지 않다. 문제 입력에서 R이 세 번 이상 반복하면, X,Y 축 모두에 대해 monotone하지 않게 된다.만약 R이 두 번 반복한 경우가 있다면, 판도라의 방향에 따라 X축이나 Y축 둘 중 하나가 monotone 하지 않게 된다. 이 두 조건을 알면 문제를 해결할 수 있다.한 가지 주의해야 할 점은 입력 Sequence가 R로 시작할 경우 Sequence 끝의 R과 연결이 될 수 있다는 점이다.

문제에 중요한 명제가 있다. 주어진 $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)$ 들을 배치..