2022-06-05 Problem Solving

최근에 여러 문제를 해결하였다. 최근에 해결해 본 문제들의 풀이를 간략하게 정리해보았다.

4230. 사랑과 전쟁

편의상 0번 남편을 위쪽에 앉히자. 남편과 아내가 같은 편에 앉을 수 없다는 조건과 각 불륜 쌍 중 최소 한 쪽은 아래 쪽에 앉아야 한다는 조건은 typical한 2-SAT 조건 식으로 만들어줄 수 있다. 2-SAT을 구하는 알고리즘을 돌려서 문제를 해결할 수 있다.

21065. Friendship Circles

문제에서 물어보는 것은 $p_0$ 에 대해 점들을 반전시켜 생각해보면 간단하다. $p_0$ 와 $p_i$ 만을 포함하는 원이 있는 것은 $p_i$를 반전 시킨 점을 지나는 직선이 존재해 나머지 점들을 한쪽 반평면에만 놓이게 할 수 있음과 동치이다. 따라서, $p_i$를 반전시킨 점을 $q_i$ 라 할 때, $q_1, q_2, \cdots, q_{n-1}, p_0$ 의 볼록 껍질을 구하여 문제를 해결할 수 있다. 실수 오차에 유의해야 하며, 이는 반전원의 반지름을 정교하게 결정하여 해결할 수 있다.

23194. Domes

두 점 $A, B$를 왼쪽에서 오른쪽 순서로 보게 됨은 반직선 $BA$의 왼쪽 반평면에 있음과 동치이다. 문제에서 주어지는 순열을 편의상 $1, 2, \cdots, n$ 이라 할 때, (1) $P_1$이 가장 왼쪽에 있고, (2) $P_{i}$가 $P_{i+1}$보다 왼쪽에 있다는 조건을 반평면들로 나타내줄 수 있고, 이 반평면들의 교집합을 구해 문제를 해결할 수 있다.

4966. Cards

파란 카드와 빨간 카드의 쌍을 모두 보면서 gcd가 1 이상이면 간선을 잇자. 그러면, 이분 그래프가 생기게 되고, 카드 쌍을 제거하는 것은 이 그래프의 간선과 대응된다. 고로, 이 이분 그래프에서 최대 매칭을 구해주면 문제를 해결할 수 있다.

1725. 히스토그램

히스토그램 아래 최대 넓이 직사각형은 윗변이 히스토그램의 어느 한 칸 (혹은 그 이상)과 닿아있을 것이다. 이 관찰로 부터 문제의 정답은 가장 낮은 히스토그램의 칸과 닿는 (가장 양 옆으로 긴) 직사각형이 답이거나, 해당 칸을 기준으로 왼쪽 칸들 사이에 답이 되는 직사각형이 존재하거나, 해당 칸을 기준으로 오른쪽 칸들 사이에 답이 되는 직사각형이 존재함을 알 수 있다. 이러한 사실을 이용하면 분할-정복 등의 적절한 기법을 통해 문제를 충분히 빠르게 해결할 수 있다.

3102. 겹치지 않는 원

구간 DP를 통해 접근할 수 있다. $D(l, r)$을 $[l, r]$ 에 놓이는 원 중에 겹치지 않게 선택할 수 있는 최대 개수로 정의하자. $D(l, r) = \max (D(l, x) + D(x+1, r)) + C(l, r)$이 된다. 여기에서, $C(l, r)$은 $\overline{lr}$ 을 지름으로 하는 원이 존재하면 1, 아니면 0이 되는 값이다.