2021.12.02 problem solving

티스토리 뷰

공부/Problem solving

2021.12.02 problem solving

구사과 2021. 12. 2. 02:53

Algorithmic Engagements 2010. Rectangles 2

부분 직사각형의 크기가 $w \times h$ 라면, 그 둘레는 $2(w+h)$ 이고, 등장 횟수는 $(n-w+1)(m-h+1)$ 입니다. 이를 토대로 모든 가능한 경우를 나열한 후 횟수를 합해주면 됩니다.

Algorithmic Engagements 2010. Coins

문자열을 수열로 변환합니다. 앞면에 대해서는 $1$ 을, 뒷면에 대해서는 $-k$ 를 적어줍시다. 이렇게 하면, 구간의 합이 $0$ 인 것과 앞면의 수가 뒷면의 수보다 $k$ 배 많이 나온 것이 동치입니다.

고로 구간 합이 0인 가장 긴 구간을 찾아야 합니다. 위 수열의 부분합 $S[i] = \sum_{i = 1}^{n} A[i]$ 를 구해줍시다. 이제 답은 $S[i] = S[j]$ 를 만족하는 $i, j$ 에 대해 $j - i$ 의 최댓값을 구하는 문제입니다. $(S[i], i)$ 쌍으로 정렬하면 이 값을 계산할 수 있습니다.

Russian OI 2021 Day 2 Problem 2. Гаджеты на дереве

입력이 트리가 아닌 방향 그래프의 형태로 주어지지만, 방향성을 무시하고 무방향 그래프의 형태로 관리합니다. 대신 각 간선에 대해서 (해당 방향의 간선이 존재하는가, 역방향의 간선이 존재하는가) 를 2개의 boolean 내지는 $[0, 3]$ 내의 숫자로 관리해줍니다. 이렇게 할 경우 문제의 그래프는 포레스트 형태가 되는데, 각 컴포넌트에 대해서 따로 해결합니다.

Bottom-up으로 문제를 해결합니다. 각 노드 $v$ 에 대해서 "$v$ 의 서브트리 안에 있는 간선들을 최대한 많이 가젯으로 묶고, 남은 간선이 하나 있으면 ($v$ 에서 자식으로 가는 간선, 혹은 $v$ 의 자식에서 $v$ 로 오는 간선일 것입니다) 이를 반환" 하는 함수를 만들어줍니다. 서브트리 안에서는 최대 하나의 간선밖에 나올 수 없는게, $v$ 와 그 부모를 잇는 간선하고만 매칭을 할 수 있기 때문입니다. (엄밀히는 2개도 되기는 되겠지만 그건 따로 매칭해 줄 수 있습니다.)

이 루틴은 다음과 같이 구현할 수 있습니다. 먼저 $v$ 의 자식 서브트리 $w$ 에 대해서 문제를 해결하고, $w$ 에서 나온 간선이 있으면 $(v, w)$ 에 있는 간선과 매칭을 시도합니다. (매칭이 불가능한 경우 해는 없습니다.) 이 과정에서 매칭에 들어가지 않은 간선 $(v, w)$ 들은 모두 리스트에 따로 넣습니다. 이제 리스트에 "$v$ 에서 서브트리로 가는 간선", ""서브트리에서 $v$ 로 오는 간선" 들의 리스트가 각각 있을 것입니다. 최대한 이것들을 가젯으로 묶어보고, 남은 간선이 1개 이하면 이를 반환해 주면 됩니다. 2개 이상이 남은 경우, 해는 없습니다.

알고리즘의 정당성은, $v$ 의 서브트리에서 나올 수 있는 간선이 최대 1개이기 때문에, 위 작업을 Bottom-up으로 하였을 때 매칭을 항상 최대 매칭으로 진행해야 하고, 고로 리프부터 봤을 때 위와 같은 선택이 강제된다는 점에서 보여집니다.

Google Code Jam 2015 World Finals A. Costly Binary Search

이 문제는 DP를 사용하여 해결할 수 있습니다. 현재 센서를 통해서 블랙홀의 강도가 구간 $[s, e]$ 안에 있음을 알았을 때 답을 찾는 최소 비용을 $DP[s][e]$ 라고 정의합시다. 이 경우 이 구간에서 처음으로 작동시킨 센서 $i$ 를 고정하면, $DP[s][e] = min_{i = s}^{e - 1}(max(DP[s][i], DP[i+1][e]) + A[i])$ 라는 점화식을 유도할 수 있습니다. 이 점화식은 $O(N^3)$ 에 작동하니, 최적화가 필요합니다.

여기서 중요한 관찰은 $DP[1][N + 1] \le \lceil \log(N+1) \rceil * 9 \le 180$ 이라는 것입니다. 일반적인 이분 탐색을 사용하면 항상 $\lceil \log (N+1) \rceil$ 번의 쿼리 안에 답을 찾을 수 있고, 그리고 각 쿼리에서 소모되는 값이 최대 9이니 항상 180 이내에 답을 찾을 수 있음을 알 수 있습니다. 반환값이 작기 때문에, 상태와 반환값을 전환하는 시도를 해 볼 수 있습니다.

$DP[s][e] \le DP[s][e + 1]$ 임을 활용하여, $Pos[s][k] = (DP[s][e] \le k$ 가 만족하는 최대 $e$) 라고 정의합니다. 이제 위 점화식을 새 정의에 맞게 변형해 봅시다. 일단 $A[i] = m$ 이라고 하면, $DP[s][i] \le k - m, DP[i+1][e] \le k - m$ 이 성립해야 합니다. 사용 가능한 $i$ 는 $i \le Pos[s][k - m], A[i] = m$ 을 만족하는 $i$ 들이고, 이 중에서 최대를 고르지 않을 이유가 없으니 최대인 $i = i_{max}$ 를 찾아줍시다. 이렇게 되면 해당 선택에서 가능한 $e$ 의 최댓값은 $Pos[i_{max} + 1][k - m]$ 으로 결정됩니다.

$i \le X, A[i] = m$ 을 만족하는 최대 $i$ 는 초기에 $9N$ 시간에 전처리하면 $O(1)$ 에 찾을 수 있습니다. 고로 이를 모든 $1 \le m \le 9$ 에 대해서 해 주면 한 항을 채우는데 $9$ 의 시간이 사용됩니다. DP 테이블의 크기가 $9 N \log N$ 이니, 전체 문제가 $O(9^2 N \log N)$ 에 해결됩니다. 시간 제한 안에 통과하지만, 아쉽게도 약간의 상수 조절이 필요할 수 있습니다. (토글링이나 2차원 배열 순서를 바꾸는 식으로 캐시 미스를 줄이는 방법이 좋습니다.)

Russian OI 2019 Day 1 Problem 4. Чёрная дыра

(원 문제에는 서브태스크가 있어서 이를 기준으로 설명합니다.)

서브태스크 1 (7점)

이분 탐색을 합니다. 한 원소를 3번 물어보면, 그 중 2번 이상 등장한 결과가 참입니다. 이를 토대로 이분 탐색을 하면 $3 \log N$ 번의 질의로 답을 찾을 수 있습니다.

서브태스크 2, 3 (21점)

이분 탐색을 합니다. 한 원소를 2번 물어봅니다. 만약 두 결과가 같다면 그 결과가 참입니다. 다르다면 그 중 하나는 거짓말입니다. 한 번 더 물어보면 진실을 알 수 있습니다. 센서는 거짓말을 한 번만 하니, 이를 토대로 이분 탐색을 하면 $2 \log N + 1$ 번의 질의로 답을 찾을 수 있습니다. 이렇게만 해도 $N \le 4$ 일 때는 이것이 최적 전략입니다.

서브태스크 7 (45점)

애드혹한 전략으로는 이 문제에서 20~40점 정도까지만 점수가 나옵니다. 최적의 탐색을 하기 위해서는 DP를 사용해야 합니다.

핵심적인 관찰은 다음과 같습니다. 센서에 물어본 정수 중 "$x$ 이상" 이라는 결과가 나온 정수들의 리스트를 ${d_1, d_2, \ldots, d_k}$ 라고 합시다. (이 때, $d_i > d_{i + 1}$), 같은 방식으로 "$x$ 미만" 이라는 결과가 나온 정수들의 리스트를 ${u_1, u_2, \ldots, u_k}$ 라고 합시다. (이 때, $u_i < u_{i + 1}$).

일반적인 이분 탐색에서는, 우리는 최대한의 정보를 주는 $d_1, u_1$ 에만 관심이 있습니다. 하지만, 이 문제에서는 $x \geq d_1, x < u_1$ 이라는 정보 중 최대 하나 는 틀릴 수도 있습니다. 하지만 둘 중 최대 하나가 틀리더라도, $x \geq d_2, x < u_2$ 라는 정보는 무조건 정확합니다. 고로, 이분 탐색 중인 어떠한 상태는 $(d_1, d_2, u_1, u_2)$ 라는 네 개의 정수 쌍으로 표현할 수 있습니다. 이 때 가능한 해집합은 $x \geq d_1$ 이 틀렸을 경우 $[d_2, u_1 - 1]$, $x < u_1$ 가 틀렸을 경우 $[d_1, u_2 - 1]$ 이니, 둘의 합집합이 됩니다. 기저 조건은, 두 집합의 합집합 크기가 1이거나 (자명), 두 집합의 교집합이 비어 있는 경우 (이분 탐색 사용) 입니다.

이제 동적 계획법을 사용하면, 어떠한 상태에 대해서 가능한 질의를 $1, \ldots, N$ 중 모두 해 보고, 그 중 최악의 경우 사용되는 질의 횟수를 최소화하는 것이 무엇인지 찾을 수 있습니다. 상태가 $O(N^4)$ 개이고, 전이가 $O(N)$ 이니, 시간 복잡도는 $O(N^5)$ 입니다. $N \le 15,000$ 인 전체 문제를 풀기에는 택도 없이 느려보이지만, 놀랍게도 이 풀이를 개선해 나가면서 전체 문제를 해결할 것입니다.

서브태스크 8 (50점)

$(d_1 + 1, d_2 + 1, u_1 + 1, u_2 + 1)$ 에서의 전략은 $(d_1, d_2, u_1, u_2)$ 의 전략과 동일한데, 단순히 질의를 하는 지점이 1씩 평행이동 되었다는 차이만 있습니다. 고로, $d_2 = 0$ 이라고 하고 $(d_1 - d_2, u_1 - d_2, u_2 - d_2)$ 를 상태로 하여도 무방합니다. 상태가 한 차원 줄었으니 시간 복잡도는 $O(N^4)$입니다.

서브태스크 9 (63점)

쉬운 블랙홀 문제에서 했던 것처럼 상태를 뒤집어 봅시다. $(x, y, z)$ 를 $Q$ 번 이하의 질의로 해결할 수 있다면, $(x, y, z - 1)$ 역시 물론 $Q$ 번 이하의 질의로 해결할 수 있습니다. 고로, $g(Q, x, y)$ 를 $Q$ 번의 질의를 사용하여 해결할 수 있는 최대 $z$ 라고 정의합시다. 이 때, 서브태스크 2에서 보였듯이 $Q \le 2 \log N + 1$ 이니, 상태의 개수는 $O(N^2 \log N)$ 개가 됩니다.

여기서도 위와 비슷하게, 가능한 질의를 $1 \ldots N$ 중 모두 해 보고, 그 중 양 쪽으로 내려가는 두 부분문제가 $Q - 1$ 번의 질의를 사용하며 $z$ 를 최대화하는 선택을 해 주면 됩니다. $N^4$ DP 보다는 케이스를 조금 더 구체적으로 따져야 하는데 ($i$ 가 $[d_2, d_1], [d_1 + 1, u_1 - 1], [u_1, u_2 - 1]$ 중 어떠한 구간에 있는 지 여부에 따라 전이가 갈립니다) 이 부분에 대한 설명은 생략합니다.

시간 복잡도는 $O(N^3 \log N)$ 입니다.

서브태스크 12 (75점)

상태 전이를 하는 케이스 3가지를 모두 최적화시키면 됩니다.

질의 위치가 $[d_2, d_1], [u_1, u_2 - 1]$ 에 있다면, 이 질의의 결과 중 하나는 무조건 전체 상태를 모순으로 만듭니다 (즉 이분 탐색을 적용할 수 있는 케이스가 됩니다). 질의가 어떤 결과로 나오든 $Q-1$ 번 안에 남은 문제를 해결할 수 있어야 하니, 이분 탐색을 적용하는 케이스가 나오게 되면, 그 때의 후보는 $2^{Q - 1}$ 개 이하여야 합니다. 이 사실을 활용하여 수식 전개를 하면, 실제로 유효한 질의 위치는 각 케이스당 단 하나 밖에 없습니다.
질의 위치가 $[d_1 + 1, u_1 - 1]$ 에 있다면, 이 질의의 결과가 "미만" 으로 나왔을 때 남은 부분 문제를 해결하려면 $g(Q - 1, d_1, j) \geq u_1$ 이 만족해야 합니다. $g(Q, i, j) \geq g(Q, i, j+1)$ 이니, 이것이 만족하는 최대 $j$ 는 $(Q_1, d_i)$ 를 고정하면 two pointers로 찾을 수 있습니다. 이러한 최대 $j$ 에서 쿼리를 하면 "이상" 으로 나왔을 때의 상태가 가장 Tight하니, 가장 좋은 $u_2$ 도 거기서 나올 것입니다. 고로 유효한 질의 위치는 여기서도 하나이고 이 위치를 찾는 것도 Amortized $O(1)$ 에 가능합니다.

고로 각 상태 당 전이가 최대 3개이고, 상태 전이 역시 Amortized $O(1)$ 에 찾을 수 있어서 시간 복잡도가 $O(N^2 \log N)$ 입니다.

만점 풀이

당황스럽겠지만 만점 풀이는 여기서 시간/공간 복잡도를 더 줄이려고 하지 않고, 제출하는 코드의 길이 제한은 100000byte 이하임을 사용 합니다. 초기 $k$ 번의 질의에서 센서가 반환할 수 있는 답의 경우의 수는 $2^k$ 개 입니다. 여기서 최적의 방법으로 질의를 날렸다면. 그 이후 $u_1 - d_2$ 의 값은 충분히 줄어있다고 가정할 수 있고, 실제로도 그렇습니다.

서브태스크 12의 풀이는 결국 쿼리 개수 $\times ($최대 $u_1 - d_2$ 의 크기$)^2$ 에 비례하는 시간 및 공간 복잡도에 작동합니다. 초기 $k$ 번의 질의에서의 최적의 질의를 $2^k$ 개의 정수로 하드 코딩 한다면, 이후 질의는 충분히 작은 크기를 가지니 동적 계획법으로도 처리할 수 있습니다.

하드코딩 할 최적의 질의는 서브태스크 12의 풀이를 로컬에서 돌려보면서 계산할 수 있습니다. 컴퓨터가 힘들어 하겠지만... 열심히 해 보시기 바랍니다. 빠르게 하면 대략 10분 안에 계산할 수 있습니다.

시간 및 공간 복잡도는 $O(N^2 \log N)$ 입니다.

Algorithmic Engagements 2011. Computational Geometry

$n$ 이 홀수면 답이 없습니다. 변이 가로 세로가 번갈아가면서 등장해야 하기 때문입니다. $n= 2$ 여도 답이 없습니다.

그 외 경우에는 항상 가능합니다.

$n = 4$ 이면 예제처럼 하면 됩니다.
$n > 4, n \pmod 4 = 0$ 이면, ㅜ 모양을 $n / 4$ 개 왼쪽에서 오른쪽으로 이어주면 됩니다. 넓이가 모자라면, 넓이가 찰 때까지 오른쪽 끝을 늘려주면 됩니다.
$n > 4, n \pmod 4 = 2$ 이면, $n + 2$ 라고 치고 비슷하게 하는데, 왼쪽 끝에 튀어나온 ㄷ 자를 깎아 없애주면 됩니다.

제 3회 IDTCup H. SAT-2

만약에 어떠한 변수가 한번 등장하거나, 두 번 등장할 때 같은 값을 (둘 다 $x_i$ 거나 둘 다 $\lnot x_i$) 가진다면, 이 변수의 값은 처음부터 결정된다고 볼 수 있습니다. 만약 이러한 변수가 등장한다면, 해당 변수에 값을 설정해 주고, 해당 변수를 가진 절을 만족됨 이라고 체크해 줍시다.

그렇지 않은 경우, 어떠한 변수는 항상 두번 등장하고, 이 변수에 참이나 거짓을 대입시키는 선택은 어떤 절을 만족시킬지를 선택하는 것과 동일합니다. 이를 통해 문제를 변환하면, 절을 정점으로, 변수를 간선으로 둘 경우, 각 간선의 양 끝점 중 하나를 골라서 모든 정점을 만족시킬 수 있는 지를 찾는 문제로 볼 수 있습니다.

이 문제를 각 컴포넌트에 대해서 독립적으로 해결해 줍시다. 만약 어떠한 컴포넌트에 이미 만족된 절이 존재한다면, 이 컴포넌트의 모든 절은 만족시킬 수 있습니다. 만족된 절을 루트로 하는 DFS 스패닝 트리를 구하고, 스패닝 트리에 속한 간선 (변수) 들이 자식 방향의 정점 (절) 을 만족시키게 배정하면 되기 때문입니다. 스패닝 트리에 속하지 않은 간선은 아무렇게나 만족시켜도 됩니다.

그렇지 않다고 가정합시다. 만약 컴포넌트가 트리일 때는 모든 절을 만족시킬 수 없습니다. 변수는 $n-1$ 개인데 정점은 $n$ 개이기 때문입니다. 그 외의 경우에는 항상 모든 절을 만족시키게 할 수 있습니다. 트리가 아니기 때문에 해당 컴포넌트에는 사이클이 존재합니다. 해당 사이클 위의 점을 루트로 하는 DFS 스패닝 트리를 구하면, 항상 루트 방향을 향하는 Back edge가 존재할 것입니다. DFS 스패닝 트리 안에서는 자식을 만족시키게 하고, Back edge들은 부모를 만족시키게 합니다. 그 경우 루트 방향으로 향하는 Back edge가 항상 존재하니, 루트를 제외한 모든 점은 Tree edge로, 루트는 Back edge로 만족됩니다. 시간 복잡도는 $O(n + m)$ 입니다.

제 3회 IDTCup I. 2차원 점과 쿼리

맨하탄 좌표계를 45도 돌리는 트릭을 여러번 해 봤으면 알겠지만, $max(a, b) = \frac{|a + b|}{2} + \frac{|a - b|}{2}$ 입니다. 이를 위 식에 그대로 대입하면 우리가 찾는 것은 $min_{u \in A[1], v \in A[2]}(|u.x + u.y + v.x + v.y| + |u.x - u.y + v.x - v.y|) / 2$ 입니다.

$f(u) = u.x + u.y, g(u) = u.x - u.y, h(u) = u.y - u.x$ 라고 합시다. 그렇다면 우리가 원하는 것은 $min_{u \in A[1], v \in A[2]}(f(u) + f(v) + |g(u) - h(u)|)$ 라는 값을 빠르게 계산하는 것입니다. $max(|g(u)|, |h(u)|) \le 250,000$ 이니, $g(u), h(u)$ 를 Key로 하는 세그먼트 트리를 만들어 봅시다. $minV(1, x)$ 를 $v \in A[1], g(v) = x$ 인 $v$ 중 $f(v)$ 최소, $minV(2, x)$ 를 $v \in A[2], h(v) = x$ 인 $v$ 중 $f(v)$ 최소 라고 하면, 구하는 값은 $|x - y| + minV(1, x) + minV(2, y)$ 로 표현할 수 있습니다.

$minV$ 라는 함수를 set이나 priority queue를 통해서 관리하고, 각 노드에 대해서

해당 노드가 대표하는 구간 안의 최적해
$minV(1, x) - x$의 최솟값
$minV(1, x) + x$ 의 최솟값
$minV(2, x) - x$ 의 최솟값
$minV(2, x) + x$ 의 최솟값

이라는 5가지 값을 관리하면 이를 합쳐줄 수 있습니다. 시간 복잡도는 $O(q \log q)$ 입니다.

Atcoder Grand Contest 047 F. Rooks

$O(n^2)$ 풀이

좌표 압축을 해 주면, 모든 점의 $x, y$ 좌표가 각각 $[1, n]$ 구간의 서로 다른 정수를 이룬다고 생각할 수 있습니다. $i (1 \le i \le n)$ 번 점의 좌표가 $(i, p_i)$ 라고 하면, 점의 좌표를 길이 $n$ 의 순열 $p$ 로 표현할 수 있습니다.

중요한 관찰은, 어떠한 점에서 도달할 수 있는 점들의 집합을 $S$ 라고 했을 때, $S$ 의 $x$ 좌표 및 $y$ 좌표는 연속된 구간을 이룬다는 것입니다. 만약 그렇지 않고, 한 좌표에서 $S$ 의 점들을 포함하는 구간이 두 개 이상이라고 합시다. 시작점을 포함하는 구간에서 시작점을 포함하지 않는 구간으로 움직일 때, 그 사이에 있는 도달할 수 없는 점에 의해서 공격을 받게 되고, 결국 도착이 불가능하게 됩니다.

이 관찰을 사용하여 DP를 할 수 있습니다. $DP[i][j][0/1]$ 을, 현재 $[i, j]$ 구간에 있는 점들을 방문하였고, 그 중 마지막으로 방문한 점이 $i$ 면 0, $j$ 이면 $1$ 일 때, 남은 점들을 최대한으로 방문하는 최소 시간이라고 정의합시다. 상태 전이는, $i-1$ 으로 공격받지 않고 움직일 수 있으면 $i-1$ 쪽으로 움직여 보고, $j+1$ 으로 공격받지 않고 움직일 수 있으면 $j+1$ 쪽으로 움직여 보는 두 가지가 있습니다. 이 때의 이동 횟수는 (좌표압축 전의 맨하탄 거리) - 1 입니다. 문제의 정답은 $DP[i][i][0]$ 에 저장되어 있으니, 전체 문제가 DP 테이블을 채우는 데 드는 시간인 $O(n^2)$ 에 해결됩니다.

$O(n \log n)$ 풀이

여러 가지 방법이 있습니다. 사실 일반적인 방법은 복잡한 사전지식을 요구하지 않으나, 여기서는 교육적 이유로 복잡한 사전지식을 요구하는 풀이를 설명합니다.

Permutation Tree는 순열 $P$가 주어졌을 때, $max_{i = l}^{r} P_i - min_{i = l}^{r} P_i = r - l$ 을 만족하는 구간 (여기서는 프레임 구간 이라고 표현합니다) 들을 효율적으로 표현하는 구조입니다. 이 트리는 이러한 구간들이 가지는 굉장히 멋진 조합적 성질들을 표현해 주는 점에서 의외가 있습니다. (아마 그 이상의 의미도 있을텐데, 여기부터는 제가 공부를 하고 알려드리는게 맞는 것 같습니다...)

길이 2 이상의 어떠한 순열은 다음과 같은 두 가지 방법으로 재귀적으로 분할할 수 있습니다.

만약에 어떠한 $1 \le i \le n - 1$ 가 존재하여 $[1, i]$ 가 프레임 구간 이라면, 이 순열은 Join Node입니다. 이 때, 순열은 $[1, i_1], [i_1 + 1, i_2], \ldots, [i_{k-1}+ 1, i_k]$ 각각이 모두 프레임 구간 인 Maximal한 구간들로 분할할 수 있습니다. (이 경우, $[1, i]$ 가 프레임 구간인 모든 $i$ 를 breakpoint로 삼으면 됩니다.)
그 외 경우 이 순열은 Cut Node입니다. 이 때, 순열은 $[1, i_1], [i_1 + 1, i_2], \ldots, [i_{k-1} + 1, i_k]$ 각각이 모두 프레임 구간 인 Minimal한 구간들로 분할할 수 있습니다. 여기서 Minimal하다는 것은, 저 구간들 중 2개 이상, $k-1$ 개 이하의 연속 구간을 골라서 더 큰 프레임 구간 을 만들 수 없음을 뜻합니다.

이 트리의 정확한 정의는 블로그 글을 보면 좋을 것 같습니다. 트리는 세그먼트 트리를 사용하여 $O(n \log n)$ 시간에 구성할 수 있고 아마 더 빠르게도 할 수 있을 것입니다.

이제 프레임 구간을 위와 같이 크기 $O(n)$ 의 구조로 표현하였으니, 여기서 DP를 돌려봅시다. 사실, 구조가 $O(n)$ 이긴 하지만, Join Node의 모든 연속된 부분구간은 프레임 구간을 이루기 때문에, 당연히 프레임 구간 자체가 $O(n)$ 개가 되지는 않습니다.

이 부분을 해결하기 위해 한 가지 관찰이 필요합니다. 편의상 순열이 $P = [1, 2, 3, \ldots, n]$ 이라고 합시다. 이 경우, 시작점에서 최소의 비용으로 모든 점을 방문하는 방법은

$1$ 번 점을 들러서 $n$ 번 점에 도달하거나
$n$ 번 점을 들러서 $1$ 번 점에 도달하거나

의 두 가지 방법밖에 없습니다. 이 점을 활용하면 다음과 같이 트리 DP를 할 수 있습니다:

Cut Node는 합쳐줄 것이 없습니다. 각 프레임 구간을 벗어날 수 없어서 그냥 그걸로 끝입니다.
Join Node에서 문제를 해결할 때는, 특정 프레임 구간에서 앞 뒤로 길이 1인 구간들을 붙일 수 있습니다. 만약 이렇게 해서 전체 구간에 도달할 수 있다면 부모의 값을 전해줍니다. 그렇지 않다면, 적절한 전처리로 도달할 수 있는 새로운 길이 1인 구간을 계산한 후, 위의 요령으로 붙여주면 됩니다.

시간 복잡도는 $O(n \log n)$ 입니다.

ICPC Yokohama Regional 2020 D. Colorful Rectangle

첫 번째 관찰은 다음과 같습니다. 만약 직사각형을 이룰 세 개의 점 $x, y, z$ 를 골랐을 때, 이 점을 모두 포함하는 최소 둘레 직사각형의 둘레는 $dist(x, y) + dist(y, z) + dist(z, x)$ 입니다. 이 때 $dist(x, y)$ 는 두 점의 맨하탄 거리를 뜻합니다. 증명은, 직사각형의 둘레를 $x, y, z$ 순으로 한바퀴 돌았다고 할 때, 각 점 사이를 최단 거리로 움직이지 않았다고 하면 모든 점을 포함하는 더 작은 직사각형을 찾을 수 있음으로 보이면 됩니다.

이제 일반성을 잃지 않고 $x.x \le y.x \le z.x$ 이며 색깔이 각각 0, 1, 2라고 합시다 (그 외 경우는 $3!$ 개의 경우를 모두 따져보면 됩니다.) 또한 편의상 모든 점의 $x$ 좌표와 $y$ 좌표가 다름을 가정합니다. 같아도 구현에 큰 차이는 없습니다.

Case 1. $x.y < y.y, z.y < y.y$: 일반성을 잃지 않고 $x.y < z.y$ 라고 합시다 (아닌 경우는 $y$ 좌표 뒤집어서 한번 더). 이 경우 부호를 전부 정리하면 $2 (z.x - x.x) + 2(y.y - x.y)$ 라는 값을 최소화해야 합니다. $a(p) = - 2 (p.x + p.y), b(p) = 2 p.x$ 라고 하면, $a(x) + b(z)$ 를 최소화해야 합니다. 세그먼트 트리에, 구간에 있는 검은 점들의 $a(x)$ 최소, 하얀 점들의 $b(z)$ 최소, $x.y < z.y$ 인 $a(x) + b(z)$ 의 최솟값을 관리하면, $O(1)$ 시간에 합쳐줄 수 있습니다. 고로 스위핑하면서 이 세그먼트 트리를 관리해 주면 $O(n \log n)$ 시간에 해결됩니다.
Case 2. $x.y < y.y < z.y$: 부호를 전부 정리하면 $2(z.y - x.y)+ 2(z.x - x.x)$ 를 최소화해야 합니다. $y.y$ 의 오른쪽에 있는 하얀 점들에 대해서 $x + y$ 값 최대, 왼쪽에 있는 검은 점들에 대해서 $x + y$ 값 최소를 관리해 주면 충분합니다.
Case 3. $x.y > y.y, z.y > y.y$: Case 1이랑 똑같이 하면 됩니다. 설명은 생략합니다.
Case 4. $x.y > y.y > z.y$: $y$ 좌표 뒤집고 해 주면 됩니다.