PS 이야기

문제 설명은 매우 긴 반면에 문제는 매우 간단하게 풀 수 있다. 판도라(로봇)가 가리킬 수 있는 방향은 상,하,좌,우 뿐이다. 처음 시작 방향은 중요하지 않다. 문제 입력에서 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)$ 들을 배치..