막대기 (KOI 2012)

https://www.acmicpc.net/problem/2519

새로운건 없는데 다까먹었네..

다음과 같은 논리식들을 만족하는 막대기가 필요하다.

1. 교차하는 막대기 두 쌍이 있다면, 두 쌍 중 한 쌍이 사라져야만 한다.

2. 3개의 막대기 중 한 막대기를 사용한다면, 나머지 두 막대기는 사용하면 안된다.

고로 2-SAT으로 풀리는 문제이다. 논리식을 만들어주자.

2번은 너무 당연히도 명제이다. 막대기 A를 지운다는 것을 E(A) 라고 표현했을 때, 2번은 E(A) -> ~E(B), E(A) -> ~E(C)... 를 6 (3 * 2)개 만들어주면 된다.

1번은 약간 변형해줘야 명제가 된다. E(A) || E(B) 라는 식의 명제인데. 논리식은 가정이 참이면 결론이 참이어야 하고, 가정이 거짓이면 항상 참이다. ~E(A)를 가정이라 하면 E(A) 일때 항상 참이고, ~E(A)일때는 E(B) 여야지만 참이다. 때문에 ~E(A) -> E(B) 라는 논리식을 N^2 쌍에 대해 만들어주면 된다.

논리식에 대한 논의가 끝났으니 구현에 대해서 고민해 보자.

두 선분의 교차 여부는, 한 선분을 잡은 후 반대 선분의 양 끝점이 한 선분을 마주보고 서있는지를 확인하면 된다. 조금 정확히 말하자면 선분 ax + by + c = 0 (x1 <= x <= x2) 가 있다면, 반대 선분의 양 끝점 중 하나는 ax + by + c > 0, 하나는 ax + by + c < 0이면 된다. 반대 선분도 똑같이 잡은 후 체크해줘야 한다. 설명을 이상하게 했지만 구현은 ccw 함수를 구현해주면 아주 쉽게 해결가능하다.

2-SAT 문제는 SCC를 통해서 풀 수 있다. 명제 a->b 에 대해서 a->b로 가는 간선과 ~b -> ~a로 가는 간선을 두개 만들어 준 후, Kosaraju's Algorithm이나 Tarjan's Algorithm을 통해서 SCC를 구분한다. 두 알고리즘 모두 각 컴포넌트와 그의 위상적 순서를 반환해 주는데 (타잔은 reverse order라고 한다. 난 안짜봐서 모름.) , 먼저 a와 ~a가 같은 컴포넌트에 들어 있으면 해가 없을 것이다.

만약 컴포넌트 안에 모순되는 명제가 없다면 위상적인 순서대로 차근차근 보면서 값이 정해지지 않은 컴포넌트에 "거짓" 값을 매긴다. 이런 식으로 모든 컴포넌트에 매겨진 값이 바로 답이다. 하지만 이보다 훨씬 더 간단하게 코딩할 수 있는 방법이 있는데 그냥 topo_order[i] > topo_order[~i] 일때 i가 참인 명제고 아니면 거짓인 명제라고 하면 된다. 이렇게 하면 답 역시 아주 단순하게 구할 수 있다.

이렇게 풀면 그래프 구성에 O(N^2), SCC 해결에 O(V+E)가 걸린다. E의 상한이 N^2이므로 시간 복잡도는 O(N^2)이다.