2022.07.17 problem solving

PA 2012. Mecze

두 선수가 경쟁하지 않았다는 것은, 두 선수가 항상 같은 팀에 있었다는 것과 동치입니다. 고로 각 선수가 무슨 팀에 있었는지를 크기 $M$ 의 배열에 저장하고, 배열들을 정렬한 후 중복 원소가 있는지를 체크하면 됩니다. 배열을 정렬하기 위해서는

• 배열간 비교가 가능한 vector<int> 같은 자료형을 쓰거나
• $M \le 50$ 이니 배열 대신 long long 자료형에 비트마스크로 저장하거나

등등의 방법이 있습니다.

Petrozavodsk Winter 2022 Day 1 - Kyoto U Contest. Build The Grid

사진으로 대체합니다:

이러한 구성을 찾는 방법은 여러 가지가 있습니다. 저의 경우에는 그냥 백트래킹을 돌려서 조건을 만족하는 그리드를 찍어보고, 규칙을 찾았습니다.

COCI 2019/2020 Contest 2. Popcount

편의상 $N = 2^k$ 라고 가정합시다. 다음과 같은 과정을 $k$ 번 반복하면 원하는 결과를 얻을 수 있습니다.

• 홀수번째 비트와, 짝수번째 비트를 분리합니다. A & (홀수번째 비트만 켜진 $N$비트 정수), A & (짝수번째 비트만 켜진 $N$비트 정수) 와 같이 분리할 수 있습니다. 위 숫자의 범위가 long long을 초과함에 유의하세요.
• 짝수번째 비트들을 1비트 right shift해서 홀수번째 비트와 포갭니다.
• 두 수를 더합니다.
• 이후 수를 2비트씩 끊어 읽으면, 각 비트의 합이 저장되어 있음을 알 수 있습니다. 두 비트를 한 비트로 묶어서 생각하고 (4진법 표현이라고 생각) 반복합니다.

고로 $k = \lceil \log_2 N \rceil$ 번의 연산 안에 답을 구할 수 있습니다. 이걸로 모든 입력 데이터를 해결할 수 있습니다.

여담으로 채점 시스템에서 Python 등을 지원하지 않았고, 큰 수 구현을 요구하기도 애매해서 Output only로 출제했습니다.

이 문제를 풀면 이것도 날로 먹을 수 있습니다.

Petrozavodsk Winter 2022 Day 1 - Kyoto U Contest. Flatland Currency

첫 번째 관찰은, 5원과 1원 동전만 고려해도 된다는 것입니다. 어차피 5원 동전을 가지나 500원 동전을 가지나 1원 동전이 아닌 건 동일합니다. 5원 동전이 100개 되면 그냥 자동으로 500원으로 묶이고, 사용 시에 적당히 풀린다고 생각해도 괜찮습니다.

두 번째 관찰은, 물건 값이 $X$ 일 때 $5\lceil X/5 \rceil$ 만큼의 돈을 5원 동전으로 지불하고, 물건과 1원 동전을 얻는 것이 최적입니다. 1원 동전을 지불하면 금액으로 사용되거나 돌려받는 경우의 수 밖에 없기 때문에 사용할 필요가 없으며, 이보다 더 많은 5원 동전을 사용했다면 어차피 돌려받으니 낼 필요가 없습니다.

이제 문제는 5원 동전이라는 한정된 재화를 사용하여 1원 동전의 개수를 최대화하는 문제가 됩니다. 먼저, 초기 금액을 5원 동전과 1원 동전으로 나눈 후 1원 동전은 남겨둡니다 (답에 추가해줍니다). $C = \lfloor X/5 \rfloor$ 가 현재 가지고 있는 5원 동전의 개수라면, 각 음식을 살 때

• $\lceil X/5 \rceil$ 개의 5원 동전을 지불해서
• $5\lceil X/5 \rceil - X$ 개의 1원 동전을 받을 수 받습니다.

이 조건 하에 1원 동전의 개수를 최대화하는 Knapsack 문제가 됩니다. 그런데 5원 동전이 너무 많아서 Knapsack을 그냥 돌릴 수는 없습니다.

여기서 관찰할 수 있는 것은, 받는 1원 동전의 개수가 1개에서 4개이기 때문에, 물건을 삼으로서 얻을 수 있는 동전의 개수는 최대 $4N$ 개 입니다. 이를 토대로 변형을 합시다. 목표로 하는 1원 동전의 개수가 $K$ 라면

• $5\lceil X/5 \rceil - X$ 개의 1원 동전을 얻는데
• $\lceil X/5 \rceil$ 개의 5원 동전을 지불해야 한다

라고 문제를 변형할 수 있습니다. 이는 일반적인 Knapsack을 사용하면, $O(4N^2)$ 에 해결할 수 있습니다. 고로 다항 시간 알고리즘을 얻었으나 조금 느립니다.

이를 최적화하는 방법은 크게 두 가지가 있는데, 모두 받는 1원 동전의 개수가 1개에서 4개라는 성질을 사용합니다.

• 일반적으로 생각할 수 있는 그리디는 5원 동전 지불양 대비 1원 동전 지불양 (가성비) 를 최대화하는 원소를 반복적으로 뽑는 것입니다. 이 그리디의 문제점은, 그리디를 통해서 정확히 $K$ 개의 1원 동전을 지불하는 해를 찾으면 괜찮지만, $K$ 를 초과할 경우 그 과정에서 의미없이 비싼 물건을 살 수 있다는 것입니다. 하지만 동전 개수가 1~4 정도이기 때문에, 대략 $lcm(1, 2, 3, 4) = 12$ 근처까지는 웬만하면 그리디의 선택이 맞습니다. 고로 적당히 작은 수까지는 그리디를 돌리고, 그 이후 $100$ 개 정도에 대해서만 남은 원소로 Knapsack을 하면 됩니다. 엄밀한 증명이 있고 어렵지도 않을텐데 귀찮으니 생략합니다. 복잡도는 대략 $O(4! N)$ 정도라고 볼 수 있습니다.
• $dp[i][j] = $ ($1, 2, \ldots, i$ 개의 1원 동전을 주는 물건들만 사서 $j$ 개를 얻는 최소 비용) 이라고 정의합시다. DP 점화식이 대략 $dp[i][j] = min_k ( dp[i-1][j - ik] + ( i$ 개의 1원 동전을 주는 물건들 중, 비용이 가장 낮은 $k$개의 물건 비용 합)) 로 나옵니다. 이렇게 하면 여전히 $O(4N^2)$ 인데, 최적해에 단조성이 있기 때문에 (가장 낮은 $k$ 개의 물건 비용 합 함수가 아래로 볼록하기 때문) 분할 정복 최적화를 사용하여 $O(4 N \log N)$ 에 해결할 수 있습니다. SMAWK등을 사용하면 $O(4N)$ 까지 줄일 수 있습니다.

첫번째 알고리즘은 복잡도가 $4$에 지수적이고, 두 번째 알고리즘은 복잡도가 $4$에 선형적입니다. 하지만 이 문제에서는 동전 개수가 적기 때문에, 첫번째 알고리즘이 훨씬 효율적으로 작동합니다.

Petrozavodsk Summer 2021 Day 7 - Moscow IPT Contest. No Rest for the Wicked

코로나 위험도를 시간 으로 바꾸면 문제의 조건을 더 직관적으로 이해할 수 있습니다. 시간으로 바꿀 경우, 문제는 다음과 같이 해석됩니다.

• 무방향 그래프가 있다. 각 정점에는 시간 구간 $[c_i, t_i]$ 가 있는데, 어떠한 정점에 도착 하는 시간은 $[c_i, t_i]$ 사이어야 한다. (맨 처음 시작하는 것 역시 도착에 포함) 하지만 해당 정점에서 출발하는 시간은 어떤 시간이어도 상관없다. 각 정점에서 도달할 수 있는 정점 중 $s_i$ 의 최댓값을 계산하라.

각 정점에서 도달할 수 있는 최대 $s_i$ 를 계산하는 대신, 반대 방향으로 $s_i$ 를 뿌려주는 식으로 문제를 해결합시다. 이를 위해서 시간 구간도 $[-t_i, -c_i] = [l_i, r_i]$ 로 뒤집어서 생각합시다. 시간 구간을 좌표압축한 후, 다음과 같은 점화식을 세웁시다.

$DP[t][i] = {t$ 까지 시간이 흘렀을 때 정점 $i$ 에 도달할 수 있는 최대 $s_k}$

어떠한 정점에 대해 $l_i \le t < r_i$ 라면 정점 $i$ 가 시간 $t$ 에 active 하다고 합시다. 상태 전이는 다음과 같습니다.

1. 만약 $t < l_i$ 라면 $DP[t][i] = -\infty$ 입니다.
2. 만약 $t > r_i$ 라면 $DP[t][i] = DP[t-1][i]$ 입니다.
3. 그 외 경우에는 $i$ 번 정점에 도착할 수 있기 때문에 DP 값이 바뀔 수 있습니다. 먼저, 시간 $t$에 active한 정점만을 남기고, 이 정점들의 연결 컴포넌트를 구성합시다. 같은 연결 컴포넌트에 있는 정점들은 모두 같은 DP 값을 가지게 됩니다.
4. 추가로, $i$ 에 $t > r_j$ 인 정점이 인접해 있다면, $DP[t][j]$ 의 값을 가져올 수 있습니다.

만약 1~3까지만 고려하게 된다면, 이 문제를 Offline dynamic connectivity랑 상당히 비슷한 방법으로 풀 수 있습니다. 시간 축에 대한 세그먼트 트리를 만들고, 각 정점을 $\log N$ 개의 시간 구간으로 나눕니다. DP 값은 Union-find를 통해서 관리하는데, 각 컴포넌트에 대해서 해당 컴포넌트의 DP 최댓값을 관리하는 식입니다.

만약 세그먼트 트리를 타고 내려가면서 새로운 정점을 추가할 경우, 두 컴포넌트 $x, y$가 합쳐지게 될 텐데, 이 경우 새로운 컴포넌트에는 두 컴포넌트의 DP 최댓값을 저장합니다. ($x$ 에 $y$ 를 물릴 경우, $dp[x] = max(dp[x], dp[y])$)

세그먼트 트리를 타고 올라갈 경우, 정점을 다시 지워줘야 합니다. 일반적인 경우 단순히 롤백해 주지만, 여기서는 지금까지의 DP 값을 보존할 필요가 있습니다. 이는, 컴포넌트 두 개를 끊어줄 때, 끊기는 컴포넌트의 DP 값을 올바르게 맞춰주면 됩니다. ($x$ 에서 $y$ 를 뗄 경우, $dp[y] = dp[x]$)

마지막으로 4번 부분을 고려해야 하는데, 이는 세그먼트 트리를 타고 내려가면서 새 정점을 추가할 때, 현재 active하지 않은 정점의 $s_i$ 최댓값을 계산하고 이를 컴포넌트에 적어주면 됩니다.

Petrozavodsk Winter 2022 Day 1 - Kyoto U Contest. Announcements

$\lfloor A_i / T \rfloor$ 가 같은 날짜는 한 번에 처리할 수 있습니다. 서로 다른 $\lfloor A_i / T \rfloor$ 값의 개수를 찾는 문제이고, 정렬이나 std::set 등 $O(n \log n)$ 정도의 알고리즘이면 아무거나 괜찮습니다.

ICPC Seoul Regional 2018 - Circuits

https://koosaga.com/220 에 쓴 글로 대체합니다. 여담으로 이 문제를 풀면 이것도 날먹할 수 있습니다.

Petrozavodsk Winter 2022 Day 6 - PKU Contest. Station

문제 설정을 그래프로 변환하면 다음과 같습니다. 일반성을 잃지 않고 $i$ 에서 오른쪽으로 가는 간선만 고려했을 때

• $max(i + 1, j - 1) < a_j < a_i$ 인 $j$ 로 $r_i$ 가중치의 방향 간선 추가
• $a_i \leq a_j$ 인 최소 $j$로 $r_i$ 가중치의 방향 간선 추가

를 했을 때 $s \rightarrow t$ 로 가는 최단 경로 쿼리를 지원하는 문제입니다. 위 그래프는 스택을 사용하여 $O(n)$ 시간에 구성할 수 있고, 이에 따라 위 그래프의 간선이 $O(n)$ 개임도 확인할 수 있습니다 (고로 나이브하게 Dijkstra를 돌리면 $O(q n \log n)$ 시간에 문제가 해결됩니다).

사실 여기까지만 관찰해도, Treewidth를 사용한 PS 문제 해결 글을 보면 이 문제를 풀 수 있습니다. 제 생각에는 저 글을 굳이 보지 않아도, Distance on Triangulation 문제로 적당히 환원해서 풀 수 있다고 생각합니다. 다만 풀이로 적절한 지 모르겠어서, 일단 정해에 나온 접근을 간략하게 정리합니다.

편의상 모든 $a_i$ 가 다르다고 가정합니다. 길이 $N$ 인 수열 $a_1, a_2, \ldots, a_N$ 의 Cartesian tree는 다음과 같이 구성됩니다:

• 최댓값 $a_p$ 가 루트입니다.
• $a[1 \ldots p - 1], a[p + 1 \ldots N]$ 을 토대로 한 Cartesian tree를 재귀적으로 만듭니다.
• 각각을 $a_p$ 의 왼쪽, 오른쪽 자식으로 둡니다.

Cartesian tree의 노드 하나는 원래 수열의 구간에 대응될 것입니다. $par(v)$ 를 Cartesian tree 상 부모 정점이라고 합시다. 구간 $[l \ldots r]$ 에 대응되는 어떠한 노드 $p$에 대해, $fpar([l \ldots p - 1]) = l - 1, fpar([p + 1 \ldots r]) = r + 1$ 으로 정의합시다. 그렇다면, 위에서 만든 그래프의 모든 간선은 $par(v) - v$, $fpar(v) - v$ 꼴임을 알 수 있습니다. $par(v)$ 를 타고 올라가다 보면 정점 인덱스가 감소하거나 증가할텐데, 여기서 $fpar(v)$ 는 이 인덱스 증감 부호가 바뀐 첫 지점임을 관찰하면 좋습니다. 당연하지만 $fpar(v)$ 도 $v$의 조상입니다.

쿼리로 들어온 두 정점 $x, y$ 에 대해서, Cartesian tree상 LCA를 $l$ 이라고 합시다. 최적 경로가 Cartesian tree 상에서 거치는 노드 중 가장 깊이가 낮은 노드는 $l, par(l), fpar(l)$ 셋 중 하나입니다. (증명은 생략합니다.)

셋 간의 최단 경로는 다음과 같습니다:

• $l \rightarrow par(l)$: $l, r$ 의 단조성을 사용하면 Cartesian tree 따라 한 번에 가는게 최적임을 증명할 수 있습니다.
• $l \rightarrow fpar(l)$: Cartesian tree를 0번 이상 따라가다가, 한번 $fpar(v)$ 로 전환해주면 해당 노드에 도달할 수 있습니다. prefix minimum 비슷하게 전처리해 둘 수 있습니다.
• $par(l) \rightarrow fpar(l)$: 위와 동일

위 정보를 사용하면, $s \rightarrow t$ 로 가는 경로를, $s \rightarrow x, x \rightarrow t$ 로 가는 경로로 분해할 수 있습니다. ($x$ 는 세 가지 경우를 다 해보면 됩니다). 또한, 여기서 $s \rightarrow l$ 로 가는 경로가 항상 부모 방향으로 간다고 가정해 줄 수 있습니다. 결국 $fpar$ 를 사용할 지 $par$ 를 사용할 지 두 가지 경우가 있는데, $par(v)$ 와 $v$ 의 대소관계가 같은 트리 상 노드들을 "체인" 으로 묶어주면, 체인 내부에서 전이가 일관되게 나와 관리하게 편합니다. 이를 토대로 DP를 간단한 형태로 적어준 후, 적당히 행렬 사용한 세그트리를 넣어 합쳐주면 된다고 합니다. 세그트리는 HLD 써서는 아마 시간 초과가 날 것 같고, DFS 하면서 오프라인으로 한번에 처리해야 할 것 같습니다.

사실 $l, par(l), fpar(l)$ 같은 정의와 이에 따른 성질들이 나오는 이유는 결국 Tree decomposition을 했을 때 각 Bag을 이루는 노드가 저 세 노드이기 때문입니다. 솔직히 저런 거 다 분석할 시간에 그냥 일반화된 그림을 얻어가는게 도움이 더 될거 같긴 합니다.

Petrozavodsk Winter 2022 Day 1 - Kyoto U Contest. Lion and Zebra

윤교준의 최적 전략은 대략 다음과 같습니다:

• 이민제와의 거리가 $3$ 이상일 때까지, 이민제를 찾아서 한 방향으로 움직임
• 이민제의 위치를 얼추 찾았을 경우 (정확히는, 이민제가 어느 방향 서브트리에 있는지를 찾았을 경우), 이민제가 있지 않은 방향으로 최대한 멀리 도망감

초기 이민제의 시작점을 루트로 둔다면, 결국 이민제는 윤교준이 있는 방향의 서브트리로 내려가면서 후보를 좁혀 나갈 것입니다. 이민제가 윤교준의 최종 정점에 도착하는 순간 게임이 끝나니, 윤교준의 목표는 결국 "도착하는 정점의 깊이" 를 최대화하는 것이고, 위와 같은 방법을 통해서 도착 가능한 정점의 집합을 최대화할 수 있습니다.

최적 전략은 정확히는 다음과 같습니다. $t$ 를 $v$ 에서 가장 먼 정점이라고 하고, $u$ 를 $t$ 에서 가장 먼 정점이라고 합시다. 트리의 지름을 구하는 알고리즘을 생각해 보면, $t - u$ 는 트리의 지름임을 알 수 있습니다. 윤교준은 이민제와의 거리가 $3$ 이상이며, 자신의 움직임이 이민제와의 거리를 좁힐 때까지 $t$ 방향으로 계속 움직입니다.

만약 더 이상 그럴 수 없다면 이는 두 가지 경우 중 하나인데

1. 이민제와의 거리가 좁혀지지 않았습니다. 윤교준이 마지막으로 한 움직임이 $p \rightarrow c$ 라고 합시다. 우리가 정점 $p$로 움직였을 때까지만 해도 이민제와의 거리가 좁혀지고 있었으니, 이민제의 위치는, $p$ 를 루트로 했을 때, $c$ 혹은 $v$ 를 포함하지 않는 $p$ 의 자식 서브트리에 속할 것입니다.
   $p$ 에서 가장 먼 정점은 이민제가 속하는 서브트리에 있지 않음을 보일 수 있습니다. $p$ 에서 가장 먼 정점은 지름 위에 있으니, $t$ 혹은 $u$ 일 것입니다. 만약 가장 먼 정점이 $t$ 라면, $c$ 와 같은 서브트리에 속하니 바로 없음을 보입니다. 만약 가장 먼 정점이 $u$ 라면 (그리고 그 거리가 $dist(p, t)$ 를 초과한다면) $u$ 는 $v$ 와 같은 서브트리에 속하게 됩니다. 다른 서브트리라고 하면, $v$ 에서 가장 먼 정점은 $t$가가 아니라 $u$ 가 되기 때문입니다.
   고로, 여기서부터는 $p$ 에서 가장 먼 정점 방향으로 달려가면 되며, 이 과정에서 이민제를 만날 걱정도 할 필요가 없습니다.
2. 이민제와의 거리가 2 이하입니다. 이는 정확히 $\lfloor (d-1)/2 \rfloor$ 번의 이동 이후 일어납니다. 윤교준이 마지막으로 한 움직임이 $p \rightarrow c$ 라고 합시다. (초기 $d \le 2$ 일 경우 마지막 움직임이 정의되지 않는데, 이 경우는 $p = \emptyset$ 이라고 표현하겠습니다.) 윤교준은 한번이라도 잘못된 선택을 할 경우 바로 죽기 때문에, 무조건 이민제가 없음이 보장된 서브트리로 가야 합니다. 그러한 경우는 두 가지가 있는데, 하나는 $p$가 있는 쪽의 서브트리로 가는 것, 다른 하나는 이민제가 움직이기 시작했다고 믿기에는 너무 깊이가 낮은, 다시 말해 최대 깊이가 $\lceil (d-1)/2 \rceil$ 이하인 서브트리로 가는 것입니다.
   여기서 관찰해야 할 것은, $p$ 가 있는 쪽으로 가면 최소 $\lfloor (d-1)/2 \rfloor$ 만큼은 이동할 수 있습니다. $v$ 로 가면 되기 때문입니다. 고로 다른 하나의 케이스가 유효하려면, $d$ 가 짝수이고, $p$ 가 있는 서브트리에서 $v$ 보다 더 깊은 정점이 없어야 합니다.

1번의 경우가 발생하였다면, 이민제는 무조건 현재 정점에서 가장 멀리 떨어진 정점으로 이동해야 하기 때문입니다. 고로 1번의 경우는 이민제에게 최악이고, 이민제가 고르는 시작점은 항상 2번의 경우로 끝남을 가정할 수 있습니다.

이제 각 쿼리에 대해 문제를 $O(\log N)$ 에 해결할 수 있습니다.

• 지름 $t, u$ 는 초기 전처리로 구합니다.
• Sparse table로 $c$ 를 구합니다.
• 모든 정점 $v$ 에 대해, $v$ 를 루트로 했을 때 각 서브트리의 최대 깊이 리스트를 저장해 둡니다. 이렇게 할 경우, $c$ 에서 최대 깊이가 정확히 $\lceil (d-1)/2 \rceil$ 인 정점이 있는지, 그리고 $p$ 방향으로 최대 깊이가 얼마인지 계산할 수 있습니다. 이 값을 모두 계산한다면, 정답 역시 구할 수 있습니다.

Open Cup 2018/2019 - GP of Peterhof. Machines on the Moon

High level idea

추상적으로는, 결국 각 사람이 $\log^2 N$ 개의 비트를 사용해서 두 사람이 정점 교집합이 있는지를 찾아야 합니다. $O(\log^2 N)$ 개의 비트가 아니라, 각 사람이 $\log N$ 개의 정점 인덱스를 보낼 수 있다고 생각합시다. 결론부터 말하자면, 다음과 같은 라운드를 $\log N$ 번 반복하면 항상 답을 판별할 수 있습니다.

• Alice 가 클리크 상에서 차수가 가장 낮은 정점 $x \in C$ 를 Bob 에게 보냅니다.
• Bob 가 클리크 상에서 차수가 가장 높은 정점 $y \in I$ 를 Alice 에게 보냅니다.
• 이제 _Alice_와 _Bob_은 공통적으로 두 정점 $x \in C, y \in I$를 알고 있습니다.
  • 만약 $x \in I$ 혹은 $y \in C$ 라면 $x_k = 1$ 혹은 $y_k = 1$ 을 적어서 교집합을 찾았다고 보고합니다.
  • 이후 그래프에서 $y$ 에 인접하지 않으며, $x$에 인접한 정점만을 남깁니다. 정점 $x, y$는 모두 지웁니다.
• Alice 와 Bob 이 지운 정점 집합은 동일합니다. 지운 정점 집합만 가지고 계속 반복합니다.

이 알고리즘이 올바르다는 사실은 쉽게 확인할 수 있으나, 이 알고리즘을 $\log N$ 라운드만 반복해도 답을 찾을 수 있는 이유는 증명해야 합니다.

한 라운드가 끝나면 그래프의 정점 개수는 $min(deg(x), N - 1 - deg(y))$ 로 줄어듭니다. $x$ 의 차수가 크고 $y$ 의 차수가 작으면 이 값이 $N / 2$ 이하가 되지 않을 수 있지만, 최소한 교집합이 존재할 경우 에는 그렇게 됩니다. 어떠한 정점 $v$ 가 $C \cap I$ 에 속하면, $deg(x) \leq deg(v)$, $N - 1 - deg(y) \leq N - 1 - deg(v)$ 입니다. 결론적으로, $min(p, q)$ 항에서 $p + q \leq N - 1$ 이 성립하니, 정점의 개수는 $\lfloor (N-1)/2 \rfloor$ 로 줄어듬을 알 수 있습니다. 고로, 알고리즘이 꼭 모든 정점 집합을 소모하고 끝나지는 않지만, 최소한 그렇게 되지 않을 경우 답은 존재하지 않음을 관찰할 수 있습니다.

Implementation

위 내용을 통상적인 프로그래밍 언어로 구현하는 것은 아주 쉬운 일이지만, 애석하게도 문제에서 설명한 기계어에 가까운 언어로 구현해야 합니다. 대략 이런 식으로 하셔야 합니다.

• $L = \lceil \log_2(n) \rceil$ 번의 라운드를 하는데, 매 라운드의 $L - 1$ 개의 비트는 정점의 인덱스를 반환하는 데 사용하고, 마지막 $1$ 비트는 교집합을 찾았을 경우 1을 적어주는 데 사용합니다.
• 지금까지 찾은 $x, y$ 및 이에 인접한 / 인접하지 않은 정점을 지워야 합니다. 인접한 정점을 지우는 것은 적절한 비트연산으로 각 정점당 $O(m \log n)$ 개의 노드로 할 수 있습니다.
• 인접하지 않은 정점을 지우는 것을 비슷하게 하면 각 정점당 $O(n^2 \log n)$ 개의 노드가 필요해서 줄여줘야 합니다. 지우는 노드가 $O(m)$개의 연속 구간으로 표현될 수 있으니, Sparse table을 사용하여 $[i, i + 2^j - 1]$ 구간에 지운다는 사실을 마킹해 주고, 이후 Sparse table의 자식 노드로 마킹을 전파시켜나가면서 효율적으로 노드 마킹을 해 줘야 합니다. 각 구간마다 2개의 추가 노드가 필요하고, Sparse table 자체는 $O(n \log n)$ 개의 노드를 사용하니 인접한 정점 케이스와 노드 복잡도는 동일합니다. (이건 세그먼트 트리를 사용하여 마킹을 하는 것과 아주 유사한데, 세그먼트 트리를 사용할 경우 각 구간마다 $2 \log n$ 개의 추가 노드가 필요합니다. 아마 이는 노드 개수를 초과할 것 같습니다.)
• $L - 1$ 개의 비트를 채울 때는 살아있는 정점 중 차수 최대 / 최소를 찾아줘야 합니다. 먼저 차수를 계산해야 하는데 덧셈 연산을 구현하면 계산 가능합니다. 최솟값 계산은 비교 연산을 구현하면 계산 가능합니다. 이 부분은 알고리즘적으로 어렵지는 않고 그냥 조심히 잘 짜시면 됩니다.
• 마지막 비트를 채울 때는 주어진 $x, y$ 가 $C, I$ 에 속하는 지를 봐야 하는데 적절한 비트 연산으로 할 수 있습니다.
• 최종적으로, 입력으로 주어지는 마지막 1의 위치를 토대로 현재 라운드를 유추하고, 유추한 값을 토대로 마지막 노드를 세팅합니다. 이유는 모르겠지만 1라운드에서는 1이 주어지지 않습니다. 지문에도 나와 있는 내용이니 유의해서 예외처리해주면 됩니다.

최종적으로 전체 문제를 $O(m \log n)$ 개의 노드를 사용하여 해결할 수 있습니다.

별 의미는 없지만, 커뮤니케이션 라운드가 $O(\log^2 n)$ 이니, 알고리즘의 시간 복잡도가 $O(m \log^3 n)$ 이라고 생각할 수도 있겠습니다.