Problem Solving Diary #9

BOJ 21792. Meetings 2

먼저 답 후보가 여러 개인 경우가 언제 일어나는지 살펴 봅시다. $2i$명의 비버가 만난다고 할 때, 답 후보가 $j$개인 참석자 선정이 존재한다면 트리에 아래 조건을 만족하는 경로가 존재합니다.

• 경로의 길이는 $j-1$이고,
• 경로의 양쪽 서브트리(경로의 양 끝점 포함)에 정점이 각각 $i$개 이상 존재한다.

같은 맥락으로 만약 참석자 수가 홀수라면 답은 항상 1개입니다.

Subtask 2 (20점)

$O(N^2)$ 풀이가 가능하므로, 가능한 모든 경로에 대해 양쪽 서브트리에 있는 정점 개수를 적당한 전처리를 통해 $O(1)$에 찾아주면 됩니다. 자세한 설명은 생략합니다.

Subtask 3 (100점)

가능한 모든 경로를 시도해 봐야 하는데, $N$이 큰 경우 사용할 수 있는 방법으로 Centroid Decomposition이 있습니다. 센트로이드 디컴포지션을 하면 센트로이드의 탐색 순서로 이루어진 또 다른 트리(편의상 Centroid Tree라고 부릅니다)가 존재함이 널리 알려져 있습니다. 따라서, 트리 상의 어떤 경로를 잡아도 그 경로상에 있는 점 중 Centroid Tree에서 가장 깊이가 낮은 정점 하나를 뽑을 수 있습니다. 다시 말해, 어떤 경로 $l \rightarrow r$에 대해 $l \rightarrow r$ 경로 위에 있는 점 중 가장 Centroid Tree상의 깊이가 낮은 정점 $v$가 있는데, 이를 $f(l \rightarrow r)=v$라고 합시다. 반대로, 우리는 센트로이드 트리를 순회하며 정점 $v$에서 가능한 모든 $f(l \rightarrow r)=v$인 $l \rightarrow r$에 대해 고려해 줄 것입니다.

 

이러한 접근의 장점을 알아보기 전에, 먼저 단순하게 떠올릴 수 있는 풀이를 생각해 봅시다. 아래와 같은 간단한 트리 DP를 생각해볼 수 있습니다.

• $DP[i][j]$: $i$번 노드의 서브트리에서, 경로 상의 모든 정점이 서로 부모-자식 관계인 경로만을 생각하자. 이 경로 위에 있는 정점들의 깊이를 모두 나열하면 연속한 자연수가 되고, 깊이가 가장 깊은 노드가 유일하게 존재한다. 이 노드의 서브트리 상에 있는 정점의 개수가 $j$개인 경로들에 대해, 그 최대 길이를 $DP[i][j]$로 정의한다.

이렇게 하면 max-depth가 $A$인 노드와 $B$인 노드를 합치고 답을 업데이트 하는 데 $min(A, B)$의 시간밖에 소요되지 않습니다. 다만 일반적인 벡터를 사용하면 힘들고 앞에 원소를 삽입할 수 있는 컨테이너 자료형을 구현해야 할 것입니다. 어쨌든 이 성질 때문에 잘 알려진 트리 DP 시간 복잡도 기법을 활용하면 $O(N)$에 전체 문제를 풀 수 있게 됩니다... 과연 그럴까요?

 

이 기법을 활용하면, $u$가 $v$의 조상인 형태의 $u \rightarrow v$ 경로는 고려할 수 없습니다. 그래서 여기서 Centroid Decomposition을 도입합니다. 이 기법을 각 센트로이드에 대해서 적용해 주면 모든 경로를 고려할 수 있기 때문입니다. 이제 남은 건... 구현입니다.

 

BOJ 17700. Natural Park

Subtask 1 (10점)

모든 점 쌍에 대해서 간선이 존재하는지를 한 번의 쿼리로 알 수 있기 때문에, 제곱 번 정도의 쿼리로 풀 수 있습니다.

 

Subtask 2 (20점)

입력으로 주어지는 그래프가 체인입니다. 제한을 보니 대략 $O(N \log N)$번 정도의 쿼리로 풀어야 할 것 같은데, 쉽지 않습니다. 쉽지 않은 이유 중 하나는 쿼리에서 경로의 양끝점을 지정해 줘야 하기 때문입니다.

 

여기서 조금 흥미로운 관찰이 하나 필요합니다. 정점 $0$에서 $x$번 정점까지 갈 수 있는지 판별하는데, 이때 정점 $y$만 통행 불가로 설정합시다. 이렇게 했을 때 도달이 가능하면 $y$가 더 오른쪽, 불가능하면 $y$가 더 왼쪽에 있다는 걸 알 수 있습니다. 이렇게 두 정점의 위치 관계를 알 수 있기 때문에 이걸 가지고 정렬을 하면 됩니다.

 

Subtask 4 (77점)

상당히 오랜 시간 고민했습니다. 일단 풀이의 전체적인 틀은 이렇습니다. 임의의 정점 $x$를 잡고, $x$에서 루트까지 가는 경로를 찾을 겁니다. 루트는 0번 정점입니다.

 

임의의 정점 $x$를 잡고 나서, 현재까지 위치를 파악한 정점들만을 이용해 루트에서 정점 $x$에 도달할 수 있는지 판별합니다. [Case 1] 이게 되면 정점 $x$는 현재까지 위치를 파악한 정점 중 하나와 인접하다는 겁니다. 따라서 어느 정점과 인접한 건지 이분 탐색을 통해 찾아줍니다. 이게 조금 복잡한데, 정점들을 깊이순으로 정렬한 후에 이분 탐색을 해야 동작할 겁니다. 이분 탐색에서 판별하는 건 범위 안의 노드의 부모를 모두 켜 주고 루트에서 도달 가능한지 보는 겁니다.

 

[Case 2] 만약 아직 $x$와 인접한 정점을 하나도 찾지 못했다면, $x$의 부모 중 하나를 아무거나 찾아서 루트에 더 가까워지는 전략이 필요합니다. 이것 역시 아직 찾지 못한 노드들을 반절씩 켜 보면서, 아직 찾지 못한 $x$의 부모 중 가장 번호가 큰 것을 찾아 주면 됩니다.

 

여기까지 구현하면 77점이 나옵니다.

 

Subtask 5 (100점)

여기까지의 풀이도 이미 충분히 어렵고, 배점도 크기 때문에 정해도 비슷할 거라는 추측을 할 수 있습니다. 일단 위 풀이를 그대로 적용한다고 가정해 봅시다. 이때 처음으로 문제가 생기는 부분이 어느 부분인지를 점검해 볼 필요가 있습니다.

 

만약 알고리즘이 가능한 가장 잘 작동한다고 가정해도, 우리가 기대할 수 있는 건 그래프의 임의의 스패닝 트리를 찾는 것 까지입니다. 그렇다면 이 알고리즘이 스패닝 트리를 찾을 수 있을까요? Case 1의 경우 문제될 부분은 없어 보이고, Case 2 역시 잘 작동합니다. 따라서 이걸 하면 일단 스패닝 트리를 찾을 수 있습니다. 사용하는 쿼리 횟수는 대충 계산해 보면 $O(N \log N + N)$회 정도가 되겠네요. (사실 정당성 증명의 가장 쉬운 방법은 그냥 섭테 5에서 Wrong Answer[6]이 뜨는 걸 보면 되긴 합니다...)

 

아직 쿼리 여유가 어느 정도 있으니, 이제 cross edge를 찾는 방법을 고민해 봅시다. 아직까지 각 정점의 차수가 7 이하라는 조건을 쓰지 않았으니, 이 조건을 써 보는 것도 좋겠네요.

 

0번 정점과 연결된 cross edge가 있는지를 생각해 봅시다. 이걸 판별하는 방법은 다음과 같습니다.

• 0번 정점과 인접한 아무 정점이나 하나 잡고 1번 정점이라고 하자. 마찬가지로 1번 정점과 인접한 아무 정점이나 하나 잡고 2번 정점이라고 하자.
• 0번 정점과, 2번 정점의 서브트리에 있는 정점들에만 통행 가능을 걸고 0 - 2가 통행 가능한지 보자. 만약 통행이 가능하면, 0번 정점과 2번 정점의 서브트리상에 있는 정점 최소 하나가 직접 연결되어 있다.

이걸 이제 모든 (0, 1, 2) 쌍에 대해 해 줘야 하는데, 시간이 꽤 많이 걸릴 것 같아 불안합니다. 이때 카운팅을 잘 해주면, 0-1 간선의 개수 $M$에 가능한 1-2 간선의 개수 $7-1=6$ (최대 차수에서 1을 빼 줌) 가지가 되어 이러한 쌍 개수는 총 $12M$개밖에 안 된다는 사실을 알 수 있습니다. 실제로는 훨씬 적을 것이고요. 만약 위의 판별 결과 False가 나오면 이 서브트리를 봐 줄 필요갸 없게 되니, 통행이 가능해서 cross edge가 존재한다는 사실까지 알았을 때 문제를 계속 풀어 보겠습니다.

 

이 부분은 Subtask 4의 [Case 1]과 사실 거의 같은 맥락으로 동작하기 때문에, 그 방법을 그대로 가져다 쓰면 됩니다. 문제는 그 다음입니다. 이렇게 연결된 정점을 하나 찾았다고 해서 더 이상 2번 노드의 서브트리에 연결된 정점이 없다고 단정지을 수 없습니다. 추가적으로 연결된 정점이 더 많을 수 있습니다.

 

위에서 찾은 0번 노드와 연결된 또 다른 노드를 $x$번 노드라고 합시다. 이때 현재 연결 관계는,

• 0 - 1 - 2 - ... - x - 0

입니다. 0번 노드와 연결된 또 다른 노드가 존재하는지를 판별해야 하는데, 이런 노드를 가상의 노드 $y$로 두고 이야기하겠습니다. 만약 가상의 노드 $y$가 $x$의 자식이 아닌 경우를 보고 싶다면, 2번 노드의 서브트리에서 $x$ 노드의 서브트리를 떼어내고 한 번에 생각해줄 수 있습니다. 문제는 $y$가 $x$의 자식인 경우를 봐줘야 한다는 것입니다. 이 경우도 당장 할 수 있는 최선은 $x$번 노드의 자식(최대 6개)에 대해서 이 똑같은 과정을 반복해 주는 거겠네요. 여기까지만 생각하고 이걸 그대로 짰더니, 쿼리 제한을 통과했습니다. 대충 계산해 보면 $7M + 2N \log N$ 비슷한 식이 나올 것 같은데, 쿼리 횟수 증명은 안 했습니다.

 

 

BOJ 14422. Soccer

할 수 있는 연산은 아래 두 가지로 정리할 수 있습니다.

• 현재 위치에 공이 있는 경우, 비용 $Ax+B$를 들여 공을 상하좌우 4방향 중 한 방향으로 $x$만큼 이동
• $C$의 비용을 들여, 상하좌우 4방향 중 한 방향으로 한 칸 이동 (공을 들고 있는 상태라면 공과 함깨 이동)

매우 당연한 관찰로, 한 명의 선수는 두 번 이상 공을 잡게 될 일이 없습니다. 어떤 선수가 위치 $x$와 $y$에서 모두 공을 줍게 된다면 이 선수는 이를 위해 $x$에서 $y$로 이동을 해야 하는데, 어차피 이동해야 한다면 그냥 처음부터 공을 들고 가는 게 낫습니다.

 

$x$의 거리만큼 공을 차는 연산에 대해서도 주목할 점이 있습니다. 만약 $Ax+B > Cx$라면, 그냥 공을 들고 $x$만큼 이동하는 게 더 효율적입니다. 이런 경우가 언제 발생하는지 살펴봅시다.

• $A \ge C$라면, 항상 위 식이 만족하고, 따라서 시작점에서 도착점까지 공을 나르고 가는 게 최적해입니다.
• $A < C$라면, $x \le \frac{B}{C-A}$일 때 공을 직접 들고 이동하는 것이 이득입니다. 

자연스러운 발상을 통해 아래와 같은 (틀린) 풀이를 이끌어낼 수 있습니다.

• $dist[x][y]$: $(x, y)$에 공을 든 선수가 위치하게 하기 위한 최소 비용으로 정의하자.
• $dist[x][y]$를 4방향으로 전파할 수 있다.
• 초기에 사람이 없는 칸으로 공을 차는 경우를 처리해야 한다. 각 칸별로 (맨해튼 거리로) 가장 가까운 선수와의 거리를 저장해 두자. 이 값에 $C$를 곱한 값을 더해 전이한다.
• Dijkstra 알고리즘을 통해 최적해를 구하자.
• 모든 칸에 대해, 해당 칸까지 $N$번 선수가 달려간다고 가정했을 때의 답 중 최솟값을 구한다.

하지만 위 알고리즘은 허점이 있습니다. 예를 들어 $(0, 0)$에 선수 P가 있다고 가정해 봅시다. 선수 P가 $(3, 0)$으로 공을 받으러 달려간 상황에서, 공을 $(-3, 0)$으로 차게 되면 같은 선수 P가 또 공을 받으러 가게 됩니다. 이것이 문제가 되는 이유는, 선수 P와 $(-3, 0)$의 거리가 실제보다 짧게 측정되기 때문입니다.

 

이 문제를 해결할 수 있는 방법은 각 칸별로 가장 가까운 선수를 두 명 구해 놓는 것입니다. 만약 (3, 0)에서 선수 P가 공을 잡았다면, 그 다음 사람이 없는 칸으로 공을 찰 때 선수 P를 가장 가까운 선수로 설정하는 일을 막으면 됩니다. 그렇다면 각 칸별로 가장 가까운 선수를 어떻게 찾을 수 있을까요? 간단한 BFS로 가능합니다. 단지, 각 칸을 최대 두 번 지날 수 있게 구현하면 됩니다.

 

다익스트라를 돌릴 때 역시 그냥 돌리면 간선이 $O(N^3)$개가 나오기 때문에 시간 초과가 발생할 것입니다. 간선 수를 줄이기 위해 상태 표현하는 방법을 조금 수정할 필요가 있습니다. 상태를 아래와 같이 표현합시다.

• (x, y, d, i): x와 y는 위치를 나타냅니다.
• 만약 현재 공을 가진 선수가 있는 경우, i는 그 선수의 번호입니다. 아닌 경우, i는 가장 최근에 공을 가졌던 선수의 번호입니다.
• 길이 $x$의 패스 과정을 공이 $x$만큼 굴러간다고 생각합시다. 선수가 공을 가진 경우 공은 굴러가는 상태가 아닙니다. $d$는 공이 굴러가지 않으면 4이며, 공이 굴러가는 중일 경우 0~3 중 하나로 공이 굴러가는 방향을 나타냅니다. 

위 상태면 $O(HW \log HW)$에 문제를 풀기 충분합니다. 상수가 매우 크기 때문에 최적화가 필요할 수 있습니다.

 

정해는 훨씬 더 쉬운 것 같습니다.

 

BOJ 14423. Rope

먼저 색깔 변경 연산은 사전에 한 번에 처리해도 됩니다. 따라서, 조건을 만족하는 상태로 끈을 만들기 위해 색을 조정해야 하는 최소 횟수를 구한다고 생각해도 됩니다.

 

끈 대신 종이를 접는다고 생각해 봅시다. 종이의 최종 상태를 봅시다. 종이를 위에서 본 모습은 종이 두 칸이 나란히 있는 모습일 것입니다. 종이의 모습을 A---B---C처럼 묘사해 봅시다. --- 부분이 종이가 겹쳐져 있는 부분이고, A B C는 종이상의 위치를 나타냅니다. (A와 C는 양끝, B는 정가운데)

 

펼쳐진 상태의 종이를 따라 한 칸씩 이동할 때 접혀진 상태의 위치는 이웃한 칸으로 이동합니다. 이러한 점을 잘 생각해 보면, 최종 종이의 상태는 아래와 같은 모습임을 알 수 있습니다.

 

... - B - A - B - A - B - C - B - A - ...

(B가 두 번마다 나온다.)

 

B-C-B같이 종이가 접혀 있는 경우 이 두 종이 칸의 색은 동일해야 합니다. 즉 우리가 만들어야 하는 상태는 아래와 같습니다.

• 두 색 $X$와 $Y$를 정한다. (둘이 같아도 된다.)
• 종이의 모든 칸은 $X$ 또는 $Y$의 색을 가진다.
• 종이의 길이가 짝수이고, 1번과 2번 조각, 3번과 4번 조각, 5번과 6번 조각, ..., 이렇게 홀/짝으로 인접한 두 조각은 색이 같은 경우를 기본 형태로 허용한다.
• 위 경우에서, 왼쪽 또는 오른쪽에 각각 0개 또는 1개의 X 또는 Y를 추가한 형태를 허용한다.

예를 들어 예제 1의 경우 종이의 각 칸의 색을 11 33 1로 바꾸는 것이 $c=1$의 최적해이고, 22 33 2로 바꾸는 것이 $c=2$ 또는 $c=3$의 최적해가 됩니다.

 

여기까지를 기본 전제로 잡고, 문제를 풀어 보겠습니다.

 

먼저 잡다한 처리와 관련해 먼저 짚고 넘어갈 것이 있는데, 인접하며 색이 같은 두 칸을 "그룹"이라고 합시다. 이때 그룹끼리는 겹치지 않으며, 양 끝 칸을 제외하고는 그룹이 무조건 줄지어 있어야 합니다. 위 예시의 [11] [33] 1 처럼 대괄호로 묶은 것이 그룹이 됩니다. 이런 그룹의 시작 지점이 1번 칸일지 2번 칸일지는 알 방법이 없습니다. 다시 말해, 1번 칸이 그룹에 속할지 속하지 않을지는 알 수 없습니다. 다행히 경우의 수가 두 가지뿐이고, 두 경우의 차이가 거의 없기 때문에 둘 다 해 보면 됩니다. 여기서부터는 아래를 가정하고 설명하겠습니다. 이외 케이스의 처리는 어렵지 않습니다.

• $N$이 짝수이고,
• 1번 칸과 2번 칸이 그룹을 이룬다. (즉 기본 형태)

 

색 $c$가 두 색 중 하나로 확정된 상황이라고 합시다. 나머지 색 하나도 $c$인 경우는 쉽게 처리되므로 생략합니다. 아닌 경우, 나머지 색으로 가장 좋은 선택지를 찾아야 합니다.

 

일단 위 가정들을 통해 현재 그룹들은 정해진 상태입니다. 만약 그룹의 두 칸 중 하나가 이미 색 $c$라면, 그 그룹은 색 $c$로 정해집니다. 만약 두 칸 모두 색이 $c$라면 당연하고, 한 칸만 색 $c$라고 한다면 두 칸의 색을 같게 만들기 위해 어차피 비용을 1은 사용해야 하니 비용 1을 들여 색 $c$로 정하는 것이 현명합니다.

 

그렇다면 남은 것은 두 칸 모두 색이 $c$가 아닌 그룹들뿐입니다. 나머지 색을 $x$라고 정했다고 해 봅시다. 어차피 $c$로 이 그룹의 색을 정하려면 비용 2가 필요하니, 모두 $x$로 정하는 시도를 해 볼 수 있습니다. 결국 추가 비용은 남은 칸들 중 색이 $x$가 아닌 칸의 개수입니다. 이들 중 최솟값을 구하면 되는데, 최솟값에서의 $x$는 가장 많이 등장하는 색이 되겠죠.

 

풀이를 요약하면,

1. 색 중 하나가 $c$로 확정된 경우 아래와 같이 답을 구한다.
2. 먼저 그룹 중 색 하나만이 $c$인 것의 개수를 구한다. (1)
3. 두 색 모두 $c$가 아닌 그룹의 개수를 구하고 (2), 여기에 2를 곱한 뒤 이 그룹들에서 가장 많이 나오는 색의 출현 빈도를 뺀다. (3)
4. 두 값을 더하면 답이 된다.

 

이제 이들을 어떻게 구하는지 알아봅시다. 1번과 2번은 전처리가 가능합니다. (2번의 경우 당연히 여집합을 전처리합니다.) 3번을 구하는 것이 조금 까다롭습니다. $O(N \log N)$으로 구하는 방법이 바로 떠오를 수 있지만 시간이 아슬아슬합니다. $O(N)$으로 구하는 방법은 BOJ 13548: 수열과 쿼리 6에서 사용하는 빈도 관리 방법을 사용하면 됩니다. 자세한 설명은 생략합니다.