Problem Solving Diary #17

친구들과 함께 연습셋을 돌았다. 그 중 다이아 이상 문제 몇 개에 대해 간단히 정리해 둔다.

BOJ 8473. Monopoly

좌표평면에 $N$개의 점이 주어질 때, 택시 거리가 $c$ 이하인 점들을 간선으로 연결하자. 연결 성분의 개수와 가장 큰 연결성분의 크기를 구하면 된다.

일단 좌표평면을 45도 회전해 생각하면 택시 거리는 체비셰프 거리 $\max(\Delta x, \Delta y)$ 가 된다. 이렇게 변형하면 한 점과 간선으로 직접 연결될 수 있는 점의 영역을 가로/세로 $2c$인 정사각형으로 생각할 수 있다. 이제 이러한 영역 안의 점을 빠르게 찾을 수 있는 방법을 생각해 보자.

위의 좌표 변환을 통해 다음처럼 문제를 변형할 수 있다. 각 점 $(a, b)$가 있고, $x$ 범위가 $[a-c, a+c]$ 안에 있고 $y$ 범위가 $[b-c, c]$ 안에 있는 모든 점을 찾아 이 점과 하나의 연결 성분으로 만들어 주어야 한다. 먼저 좌표 압축을 한 뒤, $x$좌표에 대한 세그먼트 트리를 관리하며 $y$가 늘어나는 방향으로 스위핑을 할 것이다. 세그먼트 트리의 각 노드에는 큐를 관리할 것인데, 해당 노드가 담당하는 $x$좌표 구간을 $x$좌표 범위가 완전히 포함하는 점들의 인덱스를 $y$좌표가 증가하는 순서대로 집어넣을 것이다. (만약 $y$좌표가 같은 점이 여러 개라면, 인덱스가 작은 것부터 집어넣자.) 이후 $y$좌표를 늘려 가면서, 어떤 점 $(a, b)$를 만날 경우 현재 $x$좌표 $a$를 포함하는 세그먼트 트리의 모든 노드 $\log n$ 개를 모두 둘러보며 큐에 있는 모든 정점과 Union Find를 통해 연결시켜주는 것이다. 이때 이것을 naive하게 한다면 당연히 시간 초과가 날 것이기 때문에 한 가지 트릭을 쓴다. 어떤 큐에 있는 점을 다른 하나의 점과 모두 연결시키고 나면, 큐에 있는 점을 하나 빼고 다 제거해 버리는 것이다. 나중에 $y=b+c$에 도달해 $(a, b)$를 제거해야 할 때에는 큐의 front에 해당하는 점이 이 점이면 제거하고, 이 점이 아니라면 앞과 같이 Union Find 연결 과정에서 이미 제거되었다는 뜻이므로 제거하지 않는다. (이것은 큐에 넣는 순서와 빼는 순서가 항상 같음이 보장되기 때문에 가능한 것이다.)

이걸 실제로 큐로 구현하면 메모리 초과가 나고 vector를 통해 구현해 주어야 한다. 이렇게 하면 시간 복잡도 $\mathcal{O}(N \log N)$에 문제를 해결할 수 있다.

BOJ 17517. Parklife

굉장히 유명한 문제로 알고 있었는데 풀게 된 것은 처음이다.

일단 문제에 등장하는 bridge들을 트리 구조로 나타내는 것이 가능하다. 방법은 어렵지 않은데, 일단 다리의 길이가 긴 것부터 짧은 것 순으로 정렬을 한 뒤, 현재 다리 노드에 해당하는 부모를 세그먼트 트리 등으로 찾으면 된다.

이제 이 문제를 트리에서 푼다고 생각해 보자. 이때 한 원호에서 $K$개 이하가 보여야 한다는 말은 트리의 모든 리프 노드 $x$에 대해 $x$와 그 조상 노드에 최대 $K$개의 정점을 색칠할 수 있다는 표현과 같다. 여기서 우리는 트리 DP가 필요하다는 생각을 할 수 있다.

$DP[x][y]$: $x$번 노드의 서브트리를 적당히 색칠했을 때, 리프 노드 중 그 노드와 조상 노드에서 색칠된 노드의 개수의 최댓값이 $y$ 이하인 경우, 가중치의 최대 합으로 정의하자. 우리는 두 자식 노드의 $DP[x]$를 빠르게 합치는 방법과 $DP[x]$에 그 부모 노드의 정보를 빠르게 추가하는 방법을 찾으면 된다.

그 전에 중요한 사실을 관찰하고 넘어가야 하는데, 바로 $DP[x]$가 볼록이라는 것이다. 즉, $DP[x][y+2] - DP[x][y+1] \le DP[x][y+1] - DP[x][y]$라는 것이다. 자세한 증명은 하지 않았지만, 이것을 말로 설명하면 $y$에서 $y+1$로 갈 때보다 $y+1$에서 $y+2$로 갈 때 증가 폭이 더 큰 일이 존재하지 않는다는 것이고, 이것은 양쪽 부분의 차이를 비교하면 쉽게 증명할 수 있을 것으로 보인다. (아니면 MCMF의 성질을 이용한다던지? 엄밀한 증명은 잘 모르겠다.)

이를 통해 단순한 DP 배열을 합치는 것이 아닌 볼록한 DP를 합치는 것으로 문제를 생각하면 일이 훨씬 더 쉬워진다. 일단 두 볼록 DP 배열을 합치는 것은, 기존의 두 배열이 $A$와 $B$라고 하고, 각각의 길이가 $a$와 $b$라고 할 때 (WLOG $a \ge b$), 이 과정을 $O(b \log b)$ 정도에 처리할 수 있으면, Tree optimzation의 원리에 따라 전체 문제를 $O(N \log N)$에 풀 수 있을 것이다. 실제로 두 배열 $A$와 $B$를 합치는 자세한 과정은 다음과 같다.

• 먼저 식을 세워 보자. 새로운 배열 $C$를 만들어서, $C[i] = A[i] + B[i]$가 되게 해야 한다. 단, $i \ge b$라면 $B[i] = B[b-1]$이다.
• 이것은 배열에 추가적인 인자 $offset$을 관리하는 것으로 해결할 수 있다. 대략적으로 설명하면, 실제로 저장하는 배열 $C_v$와 $offset$ 두 가지를 관리하고, 전체 배열에 어떤 수를 더하는 연산을 처리할 때 실제로는 $offset$에만 더하는 것이다. 이렇게 하면 $C[i] = C_v[i] + offset$이라고 생각할 수 있다. (이 트릭은 Tree에서 small to large DP를 할 때 정말 많이 사용한다)

이제 DP 배열에 새로운 노드 $x$의 정보를 추가하는 방법을 살펴보자. 예를 들어 DP 배열이 $[0, 7, 12, 15, 16]$이라고 하고, 노드 $x$의 가중치가 $4$라고 해 보자. 이때 새로운 DP 배열의 값은 $[0, 7, 12, 16, 19, 20]$이 된다. 이 연산을 정확하게 설명하는 방법은 DP 배열의 차이 배열을 논하는 것이다. 인접한 원소들의 차이가 초기에는 $[7, 5, 3, 1]$이었는데, 여기에 $4$가 끼어들어가면서 $[7, 5, 4, 3, 1]$이 된 것이다. 이것을 어떻게 구현할까? 크게 고민하지 말고 multiset을 쓰면 된다. 이렇게 하면 아까 두 배열을 구현했던 게 사실 셋 원소를 더해주는 걸로 바뀌어서 오히려 구현이 더 쉬워진다.

시간 복잡도는 $\mathcal{O}(N \log N)$ 또는 $\mathcal{O}(N \log X)$이다.

BOJ 27861. Linked Triangles

3차원 기하 문제다. 두 입체 삼각형이 고리 모양으로 서로 꿰어져 있는지를 판별할 수 있으면 풀 수 있다.

이것을 판별하기 위해서는 어떤 선분과 삼각형이 교점이 있는지를 판단할 수 있어야 한다. 벡터를 가지고 열심히 풀면 된다. 조금 자세히 설명하면, 어떤 삼각형 $ABC$와 선분 $PQ$가 겹치는지 확인할 것이다. 문제 조건상 네 점이 한 평면 위에 없으므로 케이스가 많지 않다. 일단 점 $P$와 점 $Q$가 삼각형 $ABC$를 기준으로 서로 다른 면에 있는지 확인해야 하는데, 이것은 $\overrightarrow{AB} \times \overrightarrow{AC}$를 통해 삼각형 $ABC$의 법선 벡터를 만든 뒤 이 법선 벡터와 $\overrightarrow{AP}$, $\overrightarrow{AQ}$를 내적한 값의 부호를 비교하면 된다. 그 뒤에는 삼각형 $ABC$의 면과 선분 $PQ$의 교점이 삼각형 $ABC$ 안에 있는지를 확인해야 하는데, 우선 내분점 공식을 통해 교점 $I$를 구한 다음, $(\overrightarrow{AB} \times \overrightarrow{AI}) \cdot (\overrightarrow{AB} \times \overrightarrow{AC})$를 통해 2차원에서 $A$, $B$, $I$의 ccw를 구하듯이 방향을 찾을 수 있다. 이것을 세 변에 대해 다 해보고, 방향이 모두 같은 경우 $I$가 $ABC$ 내에 있다는 것을 알 수 있다.

BOJ 24612. Sleeping in Class

길이 $N$의 배열 $A$가 있고, 인접한 두 수를 그 합으로 합치거나, 하나의 수를 합이 같은 두 수로 쪼개는 연산을 최소로 해 모든 수가 $q_i$가 되도록 하는 최소 연산 횟수를 구하는 문제이다. 이것은 $A$의 누적합 중 $q_i$의 배수의 개수를 구하는 문제로 쉽게 환원 가능하다. 이건 PMCC 2회 Div1 F의 트릭을 쓰면 해결 가능하다.