2022 국제정보올림피아드 선발고사 풀이

서브태스크의 경우 제가 풀이를 알면서 만점으로 가는 길에 있는 경우에만 설명합니다. 풀이들은 제가 해결한 방식이고, 다른 풀이들이 있을 수 있습니다.

1 - 1. 진화

서브태스크 5 (33점)

각 쿼리마다, 해당 서브트리에 대한 DP로 문제를 해결한다. 각 정점 $u$를 기준으로 해당 정점을 LCA로 가지는 경로들을 생각해보자. 이미 $u$의 서브트리 내에서 $u$에서 자식으로 향하는 간선들을 제외하면 모두 분류가 완료되었을 경우, $u$에서 자식으로 향하는 간선들 중 주요 진화로 정할 간선은 어떻게 정할까?

자식 쌍 $c1,c2$에 대해, $c1$과 $c2$를 지나며 $u$를 LCA로 가지는 경로들만 고려했을 때 부가 진화의 최댓값은 $d_{c1}+add_{c1}+d_{c2}+add_{c2}$이다. 여기서 $d_c$는 $c$의 서브트리에서 가장 깊은(가장 많은 부가 진화를 지나는) 정점의 깊이이고, $add_c$는 $c$로 향하는 진화가 주요 진화이면 0, 부가 진화이면 1이다.

동시에, $u$의 조상들에서의 처리를 위해서는 $d_u$를 구해야 한다. $d_u$는 $d_c + add_c$의 최댓값이다.

두 값들을 동시에 최소화하는 방법은 $d_c$값이 가장 큰 자식 $c$로 향하는 진화를 주요 진화로 하는 것임을 알 수 있다. 따라서 각 쿼리마다 $O(N)$에 해결할 수 있어, 문제를 $O(NQ)$ 에 해결할 수 있다.

서브태스크 3 (38점)

각 쿼리에서 트리의 모양은 서브트리의 크기에 따라 유일하게 결정된다. 미리 DP로 이 값들을 구해놓았다면, 적절한 수학적 계산으로 $N$에 대해 현재 서브트리의 크기 값을 구할 수 있다.

하지만 만점으로 향하는 다른 풀이 방법이 있는데, 바로 트리의 높이 값이 $O(\log N)$으로 매우 작다는 것이다. 정점 $u$가 새로 추가되었다면, $d$값이 수정되는 정점들은 $u$의 조상들 뿐이다. 각 조상 정점에 대해 $d$값을 업데이트하는 것은 자식이 최대 2개이므로 $O(1)$ 가능하다. 따라서 쿼리마다 $O(\log N)$에 모든 값들을 업데이트할 수 있다.

실제로 구해야 하는 값은 $d$값이 아닌, 각 정점 $u$에 대해 ($u$를 LCA로 하는 모든 경로들에 대해 지나는 부가 진화의 경로의 최댓값)의 최댓값이다. $sub_u$를 $u$의 서브트리만 고려했을 때 최댓값이라 하자. 이 값들도 같은 방법으로 업데이트할 수 있다.

서브태스크 4 (59점)

핵심적인 관찰은 최종 트리에서 DP값들이 $O(\log N)$이라는 것이다. 증명은 다양한 방법으로 가능한데, 간단하고 재밌는 증명을 소개한다. 결국 주요 진화와 부가 진화로 나누는 과정이 Heavy-Light Decomposition에서 heavy edge와 light edge로 나누는 과정과 일치하기 때문에, Heavy-Light Decomposition은 가능한 진화 분류 방법 중 하나이고, 이 경우 답이 $O(\log N)$이기 때문에, 최적의 방법 또한 $O(\log N)$이다.

이제 서브태스크 3의 두 번째 풀이와 비슷하게, 각 조상 정점에 대해 DP값을 업데이트한다. 그냥 모든 조상에 대해 업데이트를 시도하는 것은 은 이제 각 정점의 깊이가 $O(N)$이기 때문에 느리지만, 어떤 정점 $v$에서 $d$값이 바뀌지 않았다면, $v$의 조상들에 대해서도 $d$값이 바뀌지 않는다는 점을 이용해 바로 종료하는 최적화를 해 주자. $sub$에 대해서도 동일하다.

모든 쿼리에 대해, 총 업데이트의 수가 $O(\sum_u (d_u + sub_u) + Q)$임을 알 수 있다. $d_u$와 $sub_u$가 $O(\log N)$이므로, 문제를 $O(N \log N + Q)$에 해결할 수 있다.

서브태스크 5 (100점)

이제 정점 $u$에 대해 자식들이 매우 많을 수 있기 때문에, 더 효율적으로 $d_u$와 $sub_u$ 값들을 업데이트해야 한다. 이 처리만 해 준다면 서브태스크 4의 풀이를 그대로 적용할 수 있다.

쉽게 생각할 수 있는 방법으로는 std::multiset 등의 자료구조를 이용해 자식들의 $d_c$값을 관리하는 것이다. $d_u$ 값은 $d_c$의 최댓값 3개에 따라 정해지고, $sub_u$는 자식들의 $sub_u$의 최댓값과 $d_c$의 최댓값 3개에 따라 정해지기 때문에, $O(\log N)$에 새로운 $d_u$값과 $sub_u$값을 구할 수 있다. 시간복잡도는 $O(N \log^2 N + Q \log N)$이다. 조금 커 보이지만 굉장히 빠르게 돌아간다.

하지만 조금 더 생각해본다면, 이 $d_c$의 최댓값 3개를 어렵지 않게 $O(1)$에 관리할 수 있다. 특히, $d$값이 변할 경우 정확히 1 증가함을 이용하면 매우 편하게 짤 수 있다. 시간복잡도는 $O(N \log N + Q)$이다.

1 - 2. 플래피 버드

서브태스크 5 (15점)

$y$좌표가 변하지 않는 경로도 가능하지만, $X_{i,j} < W$이므로 그 경우 $x$좌표 $W$에서 $y$좌표가 변하는 같은 점수의 경로가 존재한다. 따라서 $y$좌표가 변하는 경로만 고려하자. $y$좌표가 상승 또는 하강할 수 있는데, 상승하는 경로만 고려하자.  하강하는 경로는 좌표를 뒤집으면 같은 방법으로 해결할 수 있다. 또한, 편의상 $X_{1,i} \le X_{2,i}$, $Y_{1,i} \le Y_{2,i}$를 가정한다.

 

경로를 $0 \le x \le W$, $0 \le y_1 < y_2 \le H$인 $(x,y_1,y_2)$로 표현할 수 있다: $(0,y_1) \to (x,y_1) \to (x,y_2) \to (W,y_2)$. 서브태스크 5에서는 $X_{1,i}=X_{2,i}$이므로 모든 선분이 수직한 선분이다. 이 경우, 선분의 $x$좌표에 따라 $(x,y_1,y_2)$ 경로 상에서 이 선분을 지나는 조건을 다음과 같이 정리할 수 있다.

• $X_{1,i} < x$라면 $Y_{1,i} \le y_1 \le Y_{2,i}$이면 선분을 지난다.
• $X_{1,i} = x$라면 $[y_1,y_2]$와 $[Y_{1,i},Y_{2,i}]$가 교점을 가지면 선분을 지난다.
• $X_{1,i} > x$라면 $Y_{1,i} \le y_2 \le Y_{2,i}$이면 선분을 지난다.

우리의 전략은 모든 $x$에 대해, 경로 $(x,y_1,y_2)$의 점수의 최댓값을 구하는 것이다.

 

$X_{1,i} < x$인 선분들은 $y_1$에, $X_{1,i} > x$인 선분들은 $y_2$에만 의존한다.

 

이제 $X_{1,i} = x$인 선분들을 고려해주자. '$[y_1,y_2]$와 $[Y_{1,i},Y_{2,i}]$가 교점을 가진다'는 $y_1$과 $y_2$에 모두 영향을 받기에 까다로운 조건이다. 대신, $X_{1,i} = x$인 모든 선분들의 가중치 합을 미리 구한 후, 지나지 않는 선분들을 빼 주자. 이 경우, 지나지 않는 선분들은 $Y_{2,i} < y_1$ 또는 $Y_{1,i} > y_2$를 만족하며, 동시에 만족할 수는 없다. 이제 빠지는 각 선분은 $y_1$과 $y_2$ 중 하나에만 의존하게 된다.

 

이제 모든 선분들을 $y_1$과 $y_2$ 중 하나에 의존하게 구분하였다. $L_y$를 $y_1 = y$로 했을 때 더해지는 가중치 합, $R_y$를 $y_2 = y$로 했을 때 더해지는 가중치 합이라 하자. 이제 경로 $(x, y_1, y_2)$의 점수의 최댓값은 $C_{x} + L_{y_1} + R_{y_2}$의 최댓값이다. $C_x$는 $X_{1,i} = x$인 선분들의 가중치 합이다.

 

$x = -1$에서, 모든 $L_y = 0$이다. $R_y$는 $Y_{1,i} \le y \le Y_{2,i}$인 선분들의 가중치 합으로, 부분합을 이용하면 $O(H)$에 계산할 수 있다. $x - 1$에서 $x$로 이동할 때, $L$와 $R$배열이 어떻게 바뀌는지 생각해보자.

• $X_{1,i} = x - 1$인 선분들에 대해, $L_{Y_{1,i}}, L_{Y_{1,i}+1}, \dots, L_{Y_{2,i}}$에 $A_i$를 더한다.
• $X_{1,i} = x - 1$인 선분들에 대해, $0 < Y_{1,i}$라면 $L_{0}, L_{1}, \dots, L_{Y_{1,i} - 1}$에 $A_i$를 더한다.
• $X_{1,i} = x - 1$인 선분들에 대해, $Y_{2,i} < H$라면 $R_{Y_{2,i} + 1}, R_{Y_{2,i}+2}, \dots, R_{H}$에 $A_i$를 더한다.
• $X_{1,i} = x$인 선분들에 대해, $R_{Y_{1,i}}, R_{Y_{1,i}+1}, \dots, R_{Y_{2,i}}$에 $-A_i$를 더한다.
• $X_{1,i} = x$인 선분들에 대해, $0 < Y_{1,i}$라면 $L_{0}, L_{1}, \dots, L_{Y_{1,i} - 1}$에 $ - A_i$를 더한다.
• $X_{1,i} = x$인 선분들에 대해, $Y_{2,i} < H$라면 $R_{Y_{2,i} + 1}, R_{Y_{2,i}+2}, \dots, R_{H}$에 $- A_i$를 더한다.

Lazy Propagation을 사용한 세그먼트 트리로 이 연산들을 구현할 수 있다. $L_{y_1} + R_{y_2}$의 최댓값을 구하기 위해, 각 노드에서 $L_y$의 최댓값, $R_y$의 최댓값, $L_{y_1} + R_{y_2}$의 최댓값을 저장하면 된다.

서브태스크 6 (10점)

서브태스크 6에서는 $Y_{1,i}=Y_{2,i}$이므로 모든 선분이 수평한 선분이다. 이 경우, 선분의 두 $x$좌표에 따라 $(x,y_1,y_2)$ 경로 상에서 이 선분을 지나는 조건을 다음과 같이 정리할 수 있다.

• $X_{2,i} < x$라면 $Y_{1,i}  = y_1$이면 선분을 지난다.
• $X_{1,i} \le x \le X_{2,i}$라면 $y_1 \le Y_{1,i} \le y_2$이면 선분을 지난다.
• $X_{1,i} > x$라면 $Y_{1,i} = y_2$이면 선분을 지난다.

우리의 전략은 서브태스크 5와 동일하게 모든 $x$에 대해, 경로 $(x,y_1,y_2)$의 점수의 최댓값을 구하는 것이다.

 

$X_{2,i} < x$인 선분들은 $y_1$에, $X_{1,i} > x$인 선분들은 $y_2$에만 의존한다.

 

이제 $X_{1,i} \le x \le X_{2,i}$인 선분들을 고려해주자. $y_1 \le Y_{1,i} \le y_2$는 $y_1$과 $y_2$에 모두 영향을 받기에 까다로운 조건이다. 대신, $X_{1,i} \le x \le X_{2,i}$인 모든 선분들의 가중치 합을 미리 구한 후, 지나지 않는 선분들을 빼 주자. 이 경우, 지나지 않는 선분들은 $Y_{2,i} < y_1$ 또는 $Y_{1,i} > y_2$를 만족하며, 동시에 만족할 수는 없다. 이제 빠지는 각 선분은 $y_1$과 $y_2$ 중 하나에만 의존하게 된다.

 

이제 모든 선분들을 $y_1$과 $y_2$ 중 하나에 의존하게 구분하였다. $L_y$를 $y_1 = y$로 했을 때 더해지는 가중치 합, $R_y$를 $y_2 = y$로 했을 때 더해지는 가중치 합이라 하자. 이제 경로 $(x, y_1, y_2)$의 점수의 최댓값은 $C_{x} + L_{y_1} + R_{y_2}$의 최댓값이다. $C_x$는 $X_{1,i} \le x \le X_{2,i}$인 선분들의 가중치 합이다. 부분합을 이용하면 $O(W)$에 계산할 수 있다.

 

$x = -1$에서, 모든 $L_y = 0$이다. $R_y$는 $Y_{1,i} = y$인 선분들의 가중치 합이다. $x - 1$에서 $x$로 이동할 때, $L$와 $R$배열이 어떻게 바뀌는지 생각해보자.

• $X_{2,i} = x - 1$인 선분들에 대해, $L_{Y_{1,i}}$에 $A_i$를 더한다.
• $X_{2,i} = x - 1$인 선분들에 대해, $0 < Y_{1,i}$라면 $L_{0}, L_{1}, \dots, L_{Y_{1,i} - 1}$에 $A_i$를 더한다.
• $X_{2,i} = x - 1$인 선분들에 대해, $Y_{1,i} < H$라면 $R_{Y_{1,i} + 1}, R_{Y_{1,i}+2}, \dots, R_{H}$에 $A_i$를 더한다.
• $X_{1,i} = x$인 선분들에 대해, $R_{Y_{1,i}}$에 $-A_i$를 더한다.
• $X_{1,i} = x$인 선분들에 대해, $0 < Y_{1,i}$라면 $L_{0}, L_{1}, \dots, L_{Y_{1,i} - 1}$에 $ - A_i$를 더한다.
• $X_{1,i} = x$인 선분들에 대해, $Y_{1,i} < H$라면 $R_{Y_{1,i} + 1}, R_{Y_{1,i}+2}, \dots, R_{H}$에 $- A_i$를 더한다.

Lazy Propagation을 사용한 세그먼트 트리로 이 연산들을 구현할 수 있다. $L_{y_1} + R_{y_2}$의 최댓값을 구하기 위해, 각 노드에서 $L_y$의 최댓값, $R_y$의 최댓값, $L_{y_1} + R_{y_2}$의 최댓값을 저장하면 된다.

서브태스크 7 (100점)

서브태스크 5와 6을 동시에 하면 된다.

1 - 3. 히스토그램

서브태스크 2, 서브태스크 3 (K = 2), 서브태스크 5 (K = 1) (7점)

$K = 1$인 문제는 잘 알려진 히스토그램에서 최대 넓이 직사각형을 구하는 문제다. 일반성을 잃지 않고 $H_i$가 모두 다르다고 하자. 히스토그램에서 최대 넓이 직사각형을 구할 때, 우리는 각 $i$에 대해 $H_{L_i},H_{{L_i}+1},\dots,H_{R_i}$중 $H_i$가 최솟값인 가장 긴 구간 $[L_i, R_i]$을 찾는다. 그렇다면 열 $L_i,L_i+1,\dots,R_i$을 차지하는 높이 $H_i$의 직사각형이 답의 후보가 된다. 이 $N$개의 직사각형들을 최대 직사각형이라 하자.

 

최대 직사각형들의 가능한 $\binom{N}{K}$개 조합 각각에 대해, $K$개의 직사각형들의 합집합의 영역을 구한다(포함-배제를 이용하면 깔끔하게 구현할 수 있다). 이 영역들만 고려해도 답을 구할 수 있다.

서브태스크 5 (K = 2) (28점)

$K = 2$에 대해, 최적해의 모양은 다음과 같은 케이스들 중 하나이다.

케이스 1에서 최적해가 나온다면, 두 직사각형은 각각 최대 직사각형이다. 그렇지 않다면 좌우로 또는 위로 직사각형을 늘릴 수 있는 방법이 있기 때문이다.

 

케이스 2에서 최적해가 나온다면, 직사각형 1은 최대 직사각형이다. 그렇지 않다면 좌우로 직사각형을 늘리거나, 위로 늘려 직사각형 2의 높이를 줄여 더 큰 넓이의 합을 얻을 수 있다. 단, 직사각형 2의 높이가 0이 될 수 있으니 $K = 1$에서의 답도 구해주자.

 

케이스 2에서 최적해가 나온다면, 직사격형 2를 아래로 끝까지 늘린 직사각형은 최대 직사각형이다. 그렇지 않다면 좌우로 또는 위로 직사각형을 늘릴 수 있는 방법이 있기 때문이다.

 

이제 최대 직사각형들만을 고려해도 $K = 2$에서 답이 나오는 이유를 알았다.

 

케이스 1은 스위핑을 통해 어렵지 않게 최댓값을 구할 수 있다.

 

최대 직사각형들을 분할정복을 통해 구하는 과정은 Cartesian tree를 구하는 과정이다. 각 최대 직사각형을 Cartesian tree의 정점으로 볼 수 있다. 케이스 2는 $u$가 $v$의 조상인 두 정점 $u$와 $v$를 골라야 한다. $H_u D_u + H_v D_v - H_u D_v$가 두 정점을 골랐을 때의 넓이 합이다. $D_u$는 정점 $u$가 나타내는 최대 직사각형의 너비이다.

 

각 $v$에 대해 최적의 $u$를 구한다. $H_v D_v$는 고정이므로 $ - H_u D_v + H_u D_u$의 최댓값을 구하면 되는데, $F_u(x) = H_u x + H_u D_u$라 정의하면, $-H_u D_v + H_u D_u = F_u(-D_v)$이니, CHT를 사용하면 될 것 같은 모양이 되었다. 트리에서 CHT를 $O(N \log N)$에 해결하는 아무 방법을 사용하면 된다. 트리에서 CHT는 BOJ 3319번 풀이를 찾아보면 좋은 자료들이 많다.

서브태스크 3 (40점)

$K = 3$에 대해, 최적해의 모양은 다음과 같은 케이스들 중 하나이다.

케이스 2의 경우는 반대로 직사각형 3이 왼쪽에 있는 경우 또한 포함이다.

 

각 케이스에 대해, $K = 2$에서와 비슷한 방식으로, 각 직사각형이 아래로 끝까지 늘린 경우 최대 직사각형임을 증명할 수 있다.

 

케이스 1은 스위핑을 통해 어렵지 않게 최댓값을 구할 수 있다. 이 때, 각 직사각형에 대해 왼쪽과 오른쪽에 있는 직사각형들 중 넓이의 최댓값 $M_i$를 추가로 구해주자.

 

케이스 2는 앞에서 구한 $M_i$값을 이용한다. $u$가 $v$의 조상인 두 정점 $u$와 $v$를 골라야 한다. $H_u D_u + H_v D_v - H_u D_v + M_u$가 두 정점을 골랐을 때의 넓이 합이다. $F_u(x) = H_u x + H_u D_u + M_u$로 정의하면, $F_u(-D_v) + H_v D_v$가 되므로 $K = 2$의 케이스 2처럼 트리에서 CHT로 구할 수 있다.

 

케이스 3은 $u$가 $v$의 조상이고, $v$가 $w$의 조상인 세 정점 $u,v,w$를 골라야 한다. $H_u (D_u - D_v) + H_v(D_v  - D_w) + H_w D_w$가 세 정점을 골랐을 때의 넓이 합이다. $F_u(x)  = H_u x + H_u D_u$로 정의하면, $H_u(D_u - D_v)$의 최댓값은 $F_u(-D_v)$의 최댓값이다. $G_v(x) = H_v x + \max F_u(-D_v) + H_v D_v$로 정의하면, 구하는 값은 $w$에 대해 $G_v(w) + H_w D_w$의 최댓값이다. 마찬가지로 트리에서 CHT로 구할 수 있다.

 

케이스 4의 경우, $u$가 $v$와 $w$의 조상이고, $v$와 $w$는 서로 조상-자손 관계가 아닌 세 정점 $u, v, w$를 골라야 한다. $H_u (D_u - D_v - D_w) +H_v D_v + H_w D_w$가 세 정점을 골랐을 때의 넓이 합이다. $v$와 $w$가 $u$의 두 자식의 서브트리에서 하나씩 온다고 생각하면 틀리며, 하기 쉬운 실수이니 유의하자. $u$를 고정하고, 각 $u$에 대해 답을 찾는다. $X_i$를 $i$의 서브트리 상의 정점들 $j$에 대해 $H_j D_j - H_u D_j$의 최댓값으로 정의하자. 트리 DP를 이용해 구할 수 있다. $u$의 서브트리 안의 각 정점 $x$에 대해, 해당 정점이 두 개의 자식 $y$와 $z$를 가지면, $H_u D_u + X_y + X_z$가 답의 후보가 된다. 이는 $v$와 $w$의 LCA가 $x$인 경우이다.

 

케이스 4를 제외하면 $O(N \log N)$에, 케이스 4를 $O(N^2)$에 해결했으니 총 시간복잡도는 $O(N^2)$이다. 다른 케이스들도 $O(N^2)$에 더 편하게 구현하는 것도 가능하다.

서브태스크 5 (100점)

케이스 4를 빠르게 해결하는 것이 관건이다. $u$가 $v$와 $w$의 조상이고, $v$와 $w$는 서로 조상-자손 관계가 아닌 세 정점 $u, v, w$를 고르는 것은 굉장히 조건이 많이 달려있어 최적화하기 어렵다. 우리는 이 조건을 완화한다: $v$와 $w$가 서로 조상-자손 관계가 아닌 세 정점 $u,v,w$를 고른다. 즉, $u$가 $v$와 $w$의 조상이라는 조건을 삭제한다.

 

이렇게 조건을 완화하면, 당연하게도 올바르지 않은 값이 나올 수 있다. 하지만, 이 올바르지 않은 값은 케이스 4의 식대로 했을 때의 올바르지 않은 값이며, 이 경우 $u,v,w$의 위치 관계가 케이스 1, 2에서 고려하는 위치 관계가 된다. 각 경우마다 케이스 1 또는 케이스 2에서 크거나 같은, "올바른" 값을 구했음을 증명할 수 있다. 따라서 이렇게 조건을 완화해도 최종적인 답은 올바르게 구할 수 있다.

 

이제 서로 조상-자손 관계가 아닌 $v$와 $w$에 대해, $F_{v,w}(x)=(D_v + D_w) x + H_v D_v + H_w D_w$로 정의하자. 각 $u$에 대해 $F_{v,w}(-H_u)$의 최댓값을 구해 $H_u D_u$와 더하면 $u$에서의 최댓값을 구할 수 있다. 다시 한 번 CHT를 적용하기 좋은 형태이다.

 

$F_{v,w}(x)$들이 총 $O(N^2)$개 있기 때문에, 바로 CHT를 적용하기는 어렵다. 하지만 각 기울기별로 최종 CHT에서는 하나의 직선만이 있을 것이고, 기울기는 $D_v + D_w$이니 $O(N)$개가 존재한다. 즉, 실제로 유의미한 직선들을 빠르게 구할 수 있다면, 문제를 해결할 수 있다.

 

유의미한 직선들을 구하는 과정을 분할 정복으로 해결한다. 아이디어는 $v$와 $w$가 서로 조상-자손 관계가 아니라는 것을, $R_v < L_w$로 해석하는 것이다. 즉, $R_v \le x \le L_w$인 $x$가 존재한다. 이를 $x$가 $v$와 $w$의 분할점이라는 것으로 정의하자.

 

$F(L,R,A)$을 $A$에 속한 정점들에 대해, $x \in [L, R]$이 분할점으로 가능할 때 유의미한 직선들을 구하는 함수로 정의하자. $L < R$이라면, $M = \left \lfloor \frac{L+R}{2} \right \rfloor$라 하자. $M$이 분할점인 경우를 구한다. $A$에서 $R_v \le M$인 $v$들의 집합을 $X$, $M < L_w$인 $w$들의 집합을 $Y$라 하자. $v \in X, w \in Y$인 모든 $v,w$는 $M$을 분할점으로 가진다.

 

$(D_v + D_w) x + H_v D_v + H_w D_w = (D_v x + H_v D_v) + (D_w x + H_w D_w)$이므로, 결국 $X$에서 구할 수 있는 $|X|$개의 직선들과, $Y$에서 구할 수 있는 $|Y|$개의 직선들의 일종의 convolution을 구하는 것이다. 결국, 각 $x$에서 $D_v x + H_v D_v$의 최댓값과 $D_v x + H_w D_w$의 최댓값이 중요하기 때문에 $X$를 이용해 구한 CHT와, $Y$를 이용해 구한 CHT들의 직선들만이 필요한 직선이다. 이 직선들 중에서도 현재 $x$에서 사용되는 직선들만이 중요하므로, 두 CHT들에서의 교점들 사이의 $x$좌표 구간에서는 최적의 직선이 고정된다. 즉, $O(|X|+|Y|)$개의 직선들만이 유의미한 직선들이 된다.

 

이후, $F(L,M,A_L)$, $F(M+1,R,A_R)$을 호출해 주자. $A_L$은 $v \in A, L_v \le M$인 $v$들이며, $A_R$은 $w \in A, M < R_w$인 $w$들이다.

 

각 $i$는 $O(\log N)$개의 분할정복 함수의 $A$에 들어간다($A$에서 $L_i$와 $R_i$를 서로 구분해서 넣는다고 생각하면 이해하기 쉽다). 따라서 분할 정복의 시간복잡도는 구현에 따라 $O(N \log N)$ 또는 $O(N \log^2 N)$이다.

 

유의미한 직선들의 수를 $O(N \log N)$개로 줄일 수 있었다. 이 직선들을 이용해 CHT를 만들면 $O(N \log ^2N)$이지만, 기울기가 $O(N)$임을 이용해 간단하게 $O(N \log N)$으로 줄일 수 있다. 이제 각 $u$에 대해 최댓값을 구하면 된다.

 

이제 케이스 4 또한 $O(N \log N)$에 해결하였으므로, 전체 문제를 $O(N \log N)$에 해결할 수 있다.

1 - 4. 날다람쥐

서브태스크 5 (33점)

우선, $(D_N,R)$에 가는 것은 예외처리가 생각보다 까다로우므로, $N+1$번째 기둥을 만들어 $D_{N+1} = D_N + R$, $H_{N+1} = W_{N+1} = 0$이라 합시다. $L$에 대해서도 비슷한 방식으로, $D_{-1} = W_{-1} = 0$, $H_{-1} = L$인 기둥을 만들어 처리가 가능하다. 이제 높이 0에서 출발해 높이 0으로 도달하는 문제가 되었다.

$i$번째 기둥의 가장 위인 $(D_i,H_i)$에서 오른쪽으로 날아갔을 때, 다음 기둥에 도달하지 못할 수 있다. 이 경우 해당 높이까지 가는 것이 의미가 없으니 $H_i = \min (H_i H_{i+1} + (D_{i+1} - D_i)$로 바꿔줍시다. $i=N$부터 $i=1$까지 순서대로 바꿔주면 된다. 도중에 $H_i < 0$이 된다면 이동이 불가능한 경우로 -1을 반환하면 된다. 추가적인 높이가 왼쪽 위에서 도달할 수 있게 해 주니 유의미하다고 생각할 수 있지만, 높이 감소에는 아무 비용이 들지 않으니 미리 높이를 감소시키고 가면 같은 비용의 경로를 얻을 수 있다.

이제 $0$부터 $N+1$까지 순서대로, 각 $i$에 대해 $i$번째 기둥까지 도달하는 최소 비용을 구한다. $i-1$번째 기둥까지 도달한 경로를 수정해, 경로가 $i$번째 기둥까지 도달하려면 앞의 기둥들에서 위로 움직여야 한다. 이 때 움직일 기둥은 위로 움직일 수 있는 기둥들 중 $W_j$가 최소인 $j$이다. 움직일 수 있다는 것은 $j$에서 경로를 위로 올리는 것이 나중에 어떤 기둥 $k$에서 $H_k$ 제한에 따라 막히지 않는다는 것을 의미한다.

따라서 위로 움직일 수 있는 기둥들 중 $W_j$가 최소인 $j$를 도달 가능할 때까지 계속 $O(N)$에 구하면, 각 상황마다 $i$에 도달이 가능해지거나 $j$가 더 이상 움직일 수 없어지기 때문에 $O(N^2)$에 문제를 해결할 수 있다.

서브태스크 6 (100점)

위로 움직일 수 있는 기둥들을 데크로 관리한다. 데크 안에서는 DP를 데크를 최적화할 때와 유사하게 비용 오름차순으로 관리한다. 만약 움직일 수 있는 기둥들 $j$와 $k$에 대해 $j < k$이고 $W_j \ge W_k$라면 $k$를 먼저 올라가게 되고, $k$를 모두 올라갔다면 $j$에서도 움직일 수 없게 되기 때문에 $j$는 의미가 없어지기 때문에 이러한 관리가 가능하다.

이제 $i$번째 기둥에 도달할 때까지 데크의 가장 앞 기둥에서 가능한 최대 높이까지 올라가는 것을 반복하고, 이후 $i$번째 기둥을 이용해 데크의 뒤에서 $W_j \ge W_i$인 기둥들을 빼 주고, 마지막으로 데크의 뒤에 기둥 $i$를 넣으면 된다.

2 - 1. 코딩 테스트

앞으로 1-based를 가정한다. 문제에서는 쿼리가 $L$과 $U$로 주어지지만, 앞으로 $l$과 $r$으로 설명합니다.

서브태스크 2 (18점)

답에 대한 이분 탐색을 하자. 답이 $X$ 이상인지 판단하는 결정 문제를 해결하자. $l$부터 $r$까지 순서대로, 우선 $A_i$개의 문제는 반드시 고를 수 있고, 이후 $B_{i-1}$개의 문제들 중 $i-1$번 문제가 사용하고 남은 문제들도 반드시 사용하는 것이 이득이다. 아직도 남은 문제가 있다면 $B_i$에서 남은 수만큼 추가로 문제를 사용해야 한다. 전부 사용해도 $X$ 미만이면 불가능한 경우이다. $r$까지 모든 난이도의 문제를 배정했다면 가능한 경우다. 각 결정문제를 해결하는 데에 $O(N)$ 시간이 필요하므로, 총 $O(NM\log 3 \times 10^8)$에 해결할 수 있다.

서브태스크 3 (54점)

쿼리 $[l, r]$에 대해, 쿼리의 답은 $\min_{l \le i \le j \le r} \left \lfloor \frac{A_i + \cdots + A_j + B_{i-1} + B_i + \cdots + B_j}{j - i +1} \right \rfloor$이다. 증명은 앞의 이분 탐색 풀이를 이용하거나, 홀의 정리를 이용하면 된다. 이분 탐색 풀이를 이용한 증명의 경우, 결국 결정 문제에서 불가능을 판단하는 데에 사용하는 값들이 저 꼴임을 관찰하자. 홀의 정리를 이용한 증명의 경우, 저 값은 연속한 난이도 집합을 기준으로 한 상한이고, 항상 최소 상한은 연속한 난이도 집합을 뽑을 때 나옴을 관찰하자.

$S_i = A_1 + \cdots + A_i + B_1 + \cdots + B_{i-1}$, $T_i = A_1 + \cdots + A_i + B_1 + \cdots + B_i$로 정의하자. 그러면 쿼리의 답이 $\min_{l - 1 \le i < j \le r} \left \lfloor \frac{T_j - S_i}{j - i + 1} \right \rfloor$이 된다.

$D_{l,r}$를 $[l, r]$쿼리에 대한 답이라 한다면, $D_{l,r}=\min(D_{l,r-1},D_{l+1,r},\left \lfloor \frac{T_r - S_{l-1}}{r-l+1} \right \rfloor)$이다. $O(N^2)$에 값들을 계산한 후 각 쿼리는 $O(1)$에 해결할 수 있다.

서브태스크 4 (77점)

모든 접두사에 대해 답을 구하면 된다. $j$번째 접두사에서의 답은 $j-1$번째 접두사에서의 답과, $\min_{0 \le i < j}^{} \left \lfloor \frac{T_j - S_i}{j - i} \right \rfloor$ 중 최솟값이다.

$\min_{0 \le i < j}^{} \frac{T_j - S_i}{j - i}$ 를 구하는 방법은 여러가지가 있는데, 이 값을 $(i, S_i)$와 $(j, T_j)$를 잇는 기울기라 생각한다면, Andrew's monotone chain 알고리즘을 이용해 $(i, S_i)$들의 윗쪽 볼록 껍질을 관리하면, $(j, T_j)$에 대해 이 볼록 껍질로 이은 접선의 기울기가 된다. 이 방법을 이용하면 $O(N \log N)$에 모든 답을 구할 수 있다.

또는 이 값에 대한 이분 탐색을 시도할 수 있다. $\min_{0 \le i < j} \frac{T_j - S_i}{j - i}$가 $X$ 이상이라는 것은 $\min_{0 \le i < j} (-jX + T_j) + (iX - S_i) \ge 0$이라는 뜻이고, 이는 CHT를 이용해 $O(\log N)$에 판단할 수 있어, 모든 답을 $O(N \log N \log 3 \times 10^8)$에 구할 수 있다.

서브태스크 5 (100점)

분할 정복을 이용해 문제를 해결한다. $[s, e]$에 대해, $r < m = \frac{s+e}{2}$인 쿼리들은 $[s, m]$에서, $m < l - 1$인 쿼리들은 $[m+1, e]$에서 해결하도록 넘겨준다. $s \le l -1 \le m < r \le e$인 쿼리들을 이제 한 번에 해결한다.

$j \le m$인 경우, $m < i$인 경우, $i \le m < j$인 경우를 모두 고려하면 $\min_{l - 1 \le i < j \le r} \left \lfloor \frac{T_j - S_i}{j - i + 1} \right \rfloor$을 구할 수 있다.

$j \le m$인 경우와 $m < i$인 경우는 각각 $[s, m]$에서의 접미사와 $[m+1, e]$에서의 접두사에서의 문제이므로 서브태스크 4의 풀이를 이용해 해결할 수 있다. 풀이에 따라 $O(N \log^2 N)$이나 $O(N \log^2N \log 3 \times 10^8)$이 걸린다.

$i \le m < j$인 경우는 서브태스크 4의 이분 탐색 풀이를 응용해 해결한다. $\min_{l - 1 \le i \le m < j \le r} \frac{T_j - S_i}{j - i + 1}$가 $X$ 이상인지 판단하는 결정 문제를 해결하자. $[l, m]$에서 $iX - S_i$의 최솟값과 $[m+1,r]$에서 $-jX + T_j$의 최솟값을 각각 CHT로 구한 다음, 합한 값이 0 이상인지 확인하면 된다. 접두사/접미사 CHT 쿼리가 필요한데, persistent CHT를 이용하는 방법 등이 가능하겠지만 parallel binary search를 사용하면 복잡한 자료구조 없이도 가능하다. 시간복잡도는 $O(N \log N \log 3 \times 10^8 + Q \log N \log 3 \times 10^8)$이다.

서브태스크 4의 볼록 껍질 풀이를 응용한 방식으로도 문제를 해결할 수 있다. 결정 문제를 해결하는 등 다양한 방법이 가능하다. 시간복잡도는 $O(N \log^2 N + Q \log N \log 3 \times 10^8)$, $O((N + Q) \log^2 N)$ 등 다양한 듯 하다.

2 - 2. 알록달록한 괄호열

서브태스크 4 (76점)

$D_{0,l,r}$을 괄호열의 $[l,r]$ 구간만 고려했을 때, $l$과 $r$의 괄호는 반드시 사용하며, $l$의 괄호와 $r$과 괄호가 짝지어질 때 뽑아낼 수 있는 알록달록한 괄호열의 수, $D_{1,l,r}$을 괄호열의 $[l,r]$ 구간만 고려했을 때, $l$과 $r$의 괄호는 반드시 사용할 때 뽑아낼 수 있는 알록달록한 괄호열의 수라고 정의하자.

$l$이 닫는 괄호이거나 $r$이 여는 괄호라면 $D_{0,l,r}=D_{1,l,r}=0$이다. $l$과 $r$이 색이 같다면 $D_{0,l,r}=0$이다.

우선, $D_{0,l,r}$을 계산하자.

우선, $l$과 $r$만 있는 경우가 하나 있다.

이제 안에 추가로 괄호가 있는 경우를 생각해보자. $l$ 왼쪽의 괄호가 $i$, $r$ 오른쪽의 괄호가 $j$인 경우를 생각해보자. $i$는 $A_i < 0, A_i \neq A_l$을 만족해야 하고, $j$는 $A_j > 0, A_j \neq A_r$를 만족해야 한다. 또한, 중복해서 세지 않기 위해서 $i$는 색이 $-A_i$인 위치들 중 가장 앞에 오는 $i$이고, $j$는 색이 $A_j$인 위치들 중 가장 뒤에 오는 $j$여야 한다. 이를 만족하는 모든 $(i,j)$에 대해 $D_{1,i,j}$를 더해주면 된다.

다음으로, $D_{1,l,r}$을 계산하자.

우선, $l$과 $r$이 서로 짝지어진 경우인 $D_{0,l,r}$이 있다.

이제 $l$과 $r$이 서로 짝지어지지 않은 경우를 생각해보자. $l$과 짝지어진 괄호가 $i$, $i$ 이후 첫 괄호가 $j$인 경우를 생각해보자. $i$는 $A_i > 0, A_i \neq -A_l$을 만족해야 하고, $j$는 $A_j < 0, A_j \neq - A_i$을 만족해야 한다. 또한, 중복해서 세지 않기 위해서 $j$는 색이 $-A_j$인 위치들 중 $i$ 이후 가장 앞에 오는 $j$여야 한다.

단순하게 생각한다면 경우의 수는 $D_{0,l,i}D_{1,j,r}$이다. 하지만 우리는 $j$에 대한 중복 계산을 고려했지만, $i$에 대한 중복 계산은 고려하지 않았다. $i$ 이전에 이미 색이 $A_i$인 위치들이 있었다면, 해당 위치들에서 이미 계산한 값들을 빼 줘야 한다. $i$ 바로 전에 등장한 $A_i$의 위치가 $bef(i)$라면, $l < bef(i)$라면 $D_{0,l,bef(i)}D_{1,j,r}$을 빼 주면 된다.

답은 $A_i < 0$이고 색이 $-A_i$인 위치들 중 가장 앞에 오는 $i$와, $A_j > 0$이고 색이 $A_j$인 위치들 중 가장 뒤에 오는 $j$들에 대해 $D_{1,i,j}$의 합이다. 하나의 DP값을 계산하는 데에 각 경우 $O(N^2)$가 걸려, 모든 DP값들을 채우는 데에 걸리는 시간은 $O(N^4)$이다.

서브태스크 5 (100점)

$D_{1,l,r}$은 $i$를 $l+1$부터 $r-1$까지 증가시키면서 먼저 각 $i$에 대해 $D_{0,l,i}$와 $D_{0,l,bef(i)}$를 구한 후, $i$를 $r-1$부터 $l+1$까지 감소시키면서 현재 각 색에 대해 가장 최근에 등장한 $j$들에 대해 $D_{1,j,r}$ 값들과 그 합을 관리하면 어렵지 않게 $O(N)$에 구할 수 있다.

$D_{0,l,r}$은 결국 $nxt(i)$를 $i$ 바로 다음에 등장한 $A_i$의 위치라 한다면, $bef(i) < l, l < i < r$인 $i$와 $nxt(j) > r, l < j < r$인 $j$에 대해 $D_{1,i,j}$의 합에 1을 더한 것이다. 반대로 각 $(i,j)$에 대해, 해당하는 $(l,r)$에 $D_{1,i,j}$를 더해준다고 생각하면, 직사각형 $[bef(i)+1, i-1] \times [j+1, nxt(j)-1]$에 $D_{1,i,j}$를 더하게 된다. 부분합으로 생각한다면 $(i-1,j+1)$과 $(bef(i), nxt(j))$에 $D_{1,i,j}$를 더하고, $(bef(i), j+1)$, $(i-1, nxt(j))$에 $D_{1,i,j}$를 더했을 때, $D_{0,l,r}$은 $x$가 $l$ 이상이고, $y$가 $r$ 이하인 $(x,y)$들의 값의 합에 1을 더한 것이다. 이렇게 생각하면 $r-l$이 증가하는 순서로 순회할 때 함께 계산이 가능함을 알 수 있다.

따라서 $O(N^3)$에 문제를 해결할 수 있다.

2 - 3. 마법 구슬 찾기

서브태스크 5 (29점)

$D_k$를 일반 구슬 $k-1$개와 마법 구슬 $1$개가 있을 때, 마법 구슬을 찾는 데에 필요한 비용이라 정의하자. $D_0 = -\infty,D_1=0$이다.

$D_k$를 이분 탐색을 이용해 구한다. $X$원이 있을 때 마법 구슬을 찾을 수 있는 지 판단하는 결정 문제를 해결하자. 각 주머니 $i$에 대해, 이 주머니에 $Y$개의 구슬을 넣었다면, 해당 주머니에 마법 구슬이 있을 때 비용은 $A_i Y + B_i$원이고, $Y$개의 구슬에 대해 문제를 다시 해결해야 하므로 $D_Y$원만큼 추가로 비용이 든다. 즉, $i$번 주머니에는 $A_i Y + B_i + D_Y \le X$인 최대 $Y$만큼의 구슬을 넣을 수 있다. $Y$는 다시 이분 탐색을 이용해 찾으면 된다.

모든 주머니에 대해 넣을 수 있는 구슬의 개수의 합이 $k$ 이상이라면 $X$원으로 마법 구슬을 찾을 수 있다. 시간복잡도는 $O(NM \log Ans \log N)$이다.

서브태스크 6 (53점)

서브태스크 5의 이분 탐색의 결정 문제는 마지막에 구슬의 개수의 합이 $k$ 이상인지를 비교하는 것만 제외하면 $k-1$에서의 결정 문제와 동일하다. 또한 자명히 $k-1$개의 구슬에서의 답은 $k$개의 구슬에서의 답 이하이다. 또, $X$원이 있을 때 각 주머니에 넣을 수 있는 구슬의 수는 $X < X'$인 $X'$원이 있을 때 각 주머니에 넣을 수 있는 구슬의 수 이하이다.

위의 관찰들을 바탕으로 느리지만 올바른 다음과 같은 풀이를 얻을 수 있다: 현재 $k-1$에서의 답 $D_{k-1}$에 대해, $X=D_{k-1}$원이 있을 때 각 주머니에 넣은 구슬의 개수를 가지고 있다. $X$를 계속 1씩 증가시킨다. 만약 어떤 주머니에 구슬을 추가로 넣을 수 있는 시점이 되었다면, 그 주머니에 구슬을 추가로 넣는다. $D_k$는 현재 시점의 $X$이다.

$X$를 1씩 증가시키면 느리지만, 각 주머니 $i$에 대해 구슬을 하나 더 넣기 위해 필요한 최소 $X$는 현재 구슬의 개수 $C_i$에 대해, $A_i (C_i + 1) + B_i + D_{C_i + 1}$이다. 모든 $i$에 대해 해당 값들 중 최솟값이 $D_k$가 되고, 해당 주머니에 구슬을 하나 더 넣어 $C_i$를 1 증가시키면 된다. 시간복잡도는 $O(NM)$이다.

유의할 점은 $C_i + 1 = N$이 되면 식이 이상해진다는 것이다. 하지만 2 이상의 $N$에 대해선 반드시 처음에 서로 다른 주머니들에 구슬을 넣어야 한다. 즉 $D_2$까지만 따로 처리해주면 아무 문제가 생기지 않는다. 구슬이 2개일 때에는 $A_i + B_i$가 가장 작은 두 주머니에 구슬을 넣으면 되고, 필요한 최소 비용은 $A_i+B_i$의 두 번째 최솟값이다. $A_i + B_i$가 가장 작은 두 개의 주머니에는 구슬을 하나씩 넣어 $C_i=1$이고, 나머지 주머니는 $C_i=0$이다.

서브태스크 7 (100점)

서브태스크 6의 풀이를 우선순위 큐를 이용해 최적화한다. 시간복잡도는 $O((M + N) \log M)$이다.

2 - 4. 보안 시스템

서브태스크 1 (5점)

모든 가능한 $2^N$개의 방법에 대해, 실제로 가능한 경우인지 확인해 본다. $O(N^2)$에 체크해 $O(2^N N^2)$에 구현해도 충분하다.

서브태스크 2 (13점)

meet in the middle 기법을 사용한다. 크기 $\frac{N}{2}$의 두 집합으로 나눈 후, 각 집합에 대해 가능한 모든 조합들을 구한다. 왼쪽 집합의 조합 $S$에 대해, 오른쪽 집합에서 $S$와 겹치지 않는 센서들의 집합을 $F(S)$라 하자. 오른쪽 집합의 조합 $T$를 $S$와 함께 사용할 수 있는 조건은 $T \subseteq F(S)$이다. SOS DP를 이용하면 $F(S)$에 대해 가장 가중치 합이 큰 $T$를 구할 수 있다. $O(2^{\frac{N}{2}} N^2)$ 등에 구현하면 된다. 최적화가 잘 된 백트래킹도 통과한다.

서브태스크 5 (24점)

가장 $x$좌표가 작은 오른쪽 방향 센서를 $P(x_P,y_P)$로 고정하자. 이제 좌표평면의 각 영역을 다음과 같이 구분할 수 있다.

• $x < x_P$인 영역에서는 위쪽 방향 센서와 아래쪽 방향 센서만이 존재한다.
• $x \ge x_P, y \ge y_P$인 영역에서는 위쪽 방향 센서와 오른쪽 방향 센서만이 존재한다.
• $x \ge x_P, y < y_P$인 영역에서는 아래쪽 방향 센서와 오른쪽 방향 센서만이 존재한다.

아래 그림은 $P$에 대해서 나누어진 영역들을 나타낸다.

각 영역은 다이나믹 프로그래밍을 이용해 $O(N^2)$ 전처리 후 $O(1)$에 가중치 합의 최댓값을 구할 수 있다. 모든 오른쪽 방향 센서에 대해서 해당 센서가 가장 $x$좌표가 작은 오른쪽 방향 센서인 경우의 최댓값을 구하면 된다. 오른쪽 방향 센서를 사용하지 않는 경우도 처리해야 함에 유의하자.

서브태스크 3 (45점)

서브태스크 5의 풀이를 확장한다. 가장 $x$좌표가 큰 왼쪽 방향 센서를 $P(x_P,y_P)$로 고정하고, 가장 $x$좌표가 작은 오른쪽 방향 센서를 $Q(x_Q,y_Q)$로 고정하자. 이 때, $x_P < x_Q$를 가정하자. 이제 좌표평면의 각 영역을 다음과 같이 구분할 수 있다.

• $x \le x_P, y \ge y_P$인 영역에서는 위쪽 방향 센서와 왼쪽 방향 센서만이 존재한다.
• $x \le x_P, y < y_P$인 영역에서는 아래쪽 방향 센서와 왼쪽 방향 센서만이 존재한다.
• $x_P < x < x_Q$인 영역에서는 위쪽 방향 센서와 아래쪽 방향 센서만이 존재한다.
• $x \ge x_Q, y \ge y_Q$인 영역에서는 위쪽 방향 센서와 오른쪽 방향 센서만이 존재한다.
• $x \ge x_Q, y < y_Q$인 영역에서는 아래쪽 방향 센서와 오른쪽 방향 센서만이 존재한다.

아래 그림은 $P$와 $Q$에 대해서 나누어진 영역들을 나타낸다.

서브태스크 5와 같은 다이나믹 프로그래밍으로 $O(1)$에 최댓값을 구할 수 있다. 가능한 쌍이 총 $O(N^2)$이니, $x_P < x_Q$인 경우는 $O(N^2)$에 최댓값을 구할 수 있다.

 

이번에는 가장 $y$좌표가 큰 아래쪽 방향 센서를 $R(x_R,y_R)$로 고정하고, 가장 $y$좌표가 작은 위쪽 방향 센서를 $S(x_S,y_S)$로 고정하자. 이 때, $y_R < y_S$를 가정하자. 위의 풀이에서 좌표를 90도 회전한 이후 동일한 방식으로 해결할 수 있다.

 

이제 남은 경우는 $x_P \ge x_Q$, $y_R \ge y_S$인 경우이다. 일반성을 잃지 않고 $y_P < y_Q$를 가정하자. 네 개의 센서가 서로 겹치지 않아야 하므로, $x_S < x_Q \le x_P < x_R$, $y_P < y_S \le y_R < y_Q$를 만족한다. 즉, 아래 그림과 같이 소용돌이 모양을 만든다. $y_P > y_Q$인 경우는 90도 회전한 이후 다시 해결하면 된다.

이제 좌표평면의 각 영역을 다음과 같이 구분할 수 있다.

• $x \le x_P, y \le y_P$인 영역에서는 아래쪽 방향 센서와 왼쪽 방향 센서만이 존재한다.
• $x \le x_P, y_P < y < y_S$인 영역에서는 왼쪽 방향 센서만이 존재한다.
• $x \ge x_Q, y \ge y_Q$인 영역에서는 위쪽 방향 센서와 오른쪽 방향 센서만이 존재한다.
• $x \ge x_Q, y_R < y < y_Q$인 영역에서는 오른쪽 방향 센서만이 존재한다.
• $x \ge x_R, y \le y_R$인 영역에서는 아래쪽 방향 센서와 오른쪽 방향 센서만이 존재한다.
• $x_P < x < x_R, y \le y_R$인 영역에서는 아래쪽 방향 센서만이 존재한다.
• $x \le x_S, y \ge y_S$인 영역에서는 위쪽 방향 센서와 왼쪽 방향 센서만이 존재한다.
• $x_S < x < x_Q, y \ge y_S$인 영역에서는 위쪽 방향 센서만이 존재한다.
• $x_Q \le x \le x_P, y_S \le y \le y_R$인 영역에서는 센서가 없다.

아래 그림은 $P$와 $Q$, $R$과 $S$에 대해서 나누어진 영역들을 나타낸다.

이번에도 다이나믹 프로그래밍을 이용한 $O(N^2)$ 전처리 후 $O(1)$에 가중치 합의 최댓값을 얻을 수 있다. 가능한 쌍이 총 $O(N^4)$이니, 이 경우는 $O(N^4)$에 최댓값을 구할 수 있다.

 

위의 영역 분리를 조금 단순화해서 해결하는 방법도 가능하다. $x \le x_P, y_P < y < y_S$인 영역에서도 아래쪽 방향 센서를 허용한다고 한 후, $x \le x_P, y < y_S$인 영역에 대해, 아래쪽 방향 센서와 왼쪽 방향 센서만 존재할 경우의 최댓값을 구하자. 이렇게 구한 값은 $P$가 가장 $x$좌표가 큰 왼쪽 방향 센서라는 제약을 어길 수 있지만, 올바른 배치를 만들기에 그대로 사용해도 무방하다. 이런 방식을 통해 영역들을 4개의 꼭짓점을 포함한 영역들과 센서가 존재하지 않는 중앙의 영역으로 단순화할 수 있다. 이 경우 중요한 좌표의 수가 4개이므로 $O(N^4)$에 해결할 수 있다.

서브태스크 4 (60점)

$R$과 $S$를 고정하자. 센서가 존재할 수 있는 영역만 고려한다면, $P$에 의해 나뉘는 센서가 영역들과 $Q$에 의해 나뉘는 영역들이 서로 구분된다. $x$좌표를 증가시키면서 현재 가능한 $Q$들 중 $Q$에 의해 나뉘는 영역들의 가중치 합이 최대인 것을 관리하자. 이제 가능한 $P$를 만날 때마다 최댓값을 구할 수 있어, 고정된 $R$과 $S$에 대해 $O(N)$에 문제를 해결할 수 있다. 따라서 문제를 $O(N^3)$에 해결할 수 있다.

 

서브태스크 3의 단순화된 영역 분리를 이용한 풀이도 비슷한 방법으로 $O(N^3)$으로 최적화할 수 있다.

서브태스크 6 (77점)

$R$을 고정한 후, 각 $S$에 대해 최적의 $(P, Q)$ 쌍을 찾을 것이다. 이를 위해, 각 영역의 값을 어떻게 배정할 것인지를 결정해야 한다.

 

우선, $R$이 고정되었으므로 $x \ge x_R, y \le y_R$인 영역은 고정된다. 따라서 이 영역의 값은 상수로 취급한다.

 

$P$를 고정했을 경우, 추가적으로 고정되는 영역들은 다음과 같다. 이 두 영역들의 값은 $P$에 배정된다.

• $x \le x_P, y \le y_P$인 영역
• $x_P < x < x_R, y \le y_R$인 영역

$Q$를 고정했을 경우, 추가적으로 고정되는 영역들은 다음과 같다. 이 두 영역들의 값은 $Q$에 배정된다.

• $x \ge x_Q, y \ge y_Q$인 영역
• $x \ge x_Q, y_R < y < y_Q$인 영역

$P$와 $Q$의 조합을 고정했을 경우 $S$에 따라 결정되는 영역들은 다음과 같다. 가운데의 센서가 없는 영역은 제외했다.

• $x \le x_P, y_P < y < y_S$인 영역
• $x \le x_S, y \ge y_S$인 영역
• $x_S < x < x_Q, y \ge y_S$인 영역

$x \le x_S, y \ge y_S$인 영역은 $S$가 고정되었을 경우 고정되므로, $S$에 배정된다. 나머지 두 영역은 특정 점에 배정할 수 없으며 $P, Q, S$의 선택에 따라 바뀐다. 즉, $P, Q, S$에 대한 값은 $C_P + C_Q + C_S + f(P, S) + g(Q, S)$의 꼴로 표현할 수 있다.

 

우리의 전략은 $y = 0$에서 시작해, $y$좌표를 올리면서 가능한 $P$와 $Q$들에 대해 현재 비용, 즉 $C_P + f(P, S)$와 $C_Q + g(Q, S)$를 관리하고 가능한 $S$를 만나면 최적의 $(P, Q)$ 쌍을 찾는 것이다. 가능한 $Q$들은 $R$에 따라 고정이지만, 가능한 $P$들은 $y$좌표를 올리면서 점점 늘어남에 유의하자.

 

$f(P, S)$는 $x \le x_P, y_P < y < y_S$인 영역에서 왼쪽 방향 센서들의 가중치 합이다. 이는 $y$좌표를 올리며 왼쪽 방향 센서 $A(x_A, y_A)$를 만난 경우, $x_A \le x_P$를 만족하는 $P$들에 대해 $w_A$를 더해주는 방식으로 관리할 수 있다.

 

$g(Q, S)$는 $x_S < x < x_Q, y \ge y_S$인 영역에서 위쪽 방향 센서들의 가중치 합이다. 이를 ($x < x_Q, y \ge y_S$인 영역에서 위쪽 방향 센서들의 가중치 합) $-$ ($x \le x_S, y \ge y_S$인 영역에서 위쪽 방향 센서들의 가중치 합)으로 처리하자. 이제 $x \le x_S, y \ge y_S$인 영역은 $S$에 배정할 수 있다. $x < x_Q, y \ge y_S$인 영역에서 위쪽 방향 센서들의 가중치 합은 $y$좌표를 올리며 위쪽 방향 센서를 $A(x_A, y_A)$를 만난 경우, $x_A < x_Q$를 만족하는 $Q$들에 대해 $w_A$를 빼 주는 방식으로 관리할 수 있다.

 

따라서, $f(P, S)$와 $g(Q, S)$를 $x$좌표 구간에 대한 덧셈 연산을 통해 관리할 수 있다. $f(P, S)$ 또는 $g(Q, S)$에 대한 구간 덧셈 연산, $x_S < x_Q \le x_P$를 만족하는 $(P, Q)$에 대해 $C_P + C_Q + f(P, S) + g(Q, S)$의 최댓값을 구하는 연산이 필요하다. 이는 세그먼트 트리를 이용해 각 연산 당 $O(\log N)$에 구할 수 있다.

 

따라서 $R$이 고정된 경우의 최댓값을 $O(N \log N)$에 구할 수 있어, 전체 문제를 $O(N^2 \log N)$에 해결할 수 있다.

 

이 서브태스크의 경우 의도되지 않은 다른 풀이가 있다. 왼쪽/오른쪽 방향 센서끼리는 서로 겹치지 않고, 위쪽/아래쪽 방향 센서끼리는 서로 겹치지 않는다. 즉, 교차 관계를 그래프로 표현할 경우 이 그래프는 이분 그래프이다. 이분 그래프에서 최대 가중치 독립 집합을 구해야 한다. 이는 Min Cut Max Flow 정리를 이용해 해결할 수 있다.

서브태스크 7 (100점)

어떠한 센서가 바라보는 방향에 같은 방향의 더 큰 가중치를 가진 센서가 있다면 이 센서는 의미가 없고, 지워도 무방하다. 이 처리를 통해 무의미한 센서들을 미리 지워주자.

 

같은 좌표를 가진 센서들이 여럿 있을 수 있으므로 $f(P, S)$와 $g(Q, S)$를 이제는 다순히 가중치 합으로 처리할 수 없다.

$f(P, S)$는 $y_P < y < y_S$를 만족하는 각 $y$에 대해, $x \le x_P$를 만족하는 왼쪽 방향 센서들의 가중치 중 최댓값의 합이다. 앞에서 무의미한 센서들을 지웠기 때문에 $x \le x_P$를 만족하는 센서들 중 가장 $x$좌표가 큰 센서가 우리가 원하는 센서이다. $y$좌표를 올리며 왼쪽 방향 센서 $A(x_A, y_A)$를 만난 경우, $A$가 최적인 $x$좌표 구간의 $f(P, S)$에 $w_A$를 더하면 된다. $A$ 오른쪽의 왼쪽 방향 센서를 $B(x_B, y_A)$라 하자. 이 구간은 $[x_A, x_B - 1]$이다.

 

$g(Q, S)$는 $x_S < x < x_Q$를 만족하는 각 $x$에 대해, $y \ge y_S$를 만족하는 위쪽 방향 센서들의 가중치 중 최댓값의 합이다. 서브태스크 6과 유사하게 이를 ($x < x_Q$를 만족하는 각 $x$에 대해, $y \ge y_S$를 만족하는 위쪽 방향 센서들의 가중치 중 최댓값의 합) $-$ ($x \le x_S$를 만족하는 각 $x$에 대해, $y \ge y_S$를 만족하는 위쪽 방향 센서들의 가중치 중 최댓값의 합)으로 처리하자. 이제 $x \le x_S, y \ge y_S$인 영역은 $S$에 배정할 수 있다. $x < x_Q$인 영역에서는 $y \ge y_S$를 만족하는 센서들 중 가장 $y$좌표가 작은 센서가 우리가 원하는 센서이다. $y$좌표를 올리며 위쪽 방향 센서 $A(x_A, y_A)$를 만난 경우, $A$ 위쪽의 위쪽 방향 센서를 $B(x_A, y_B)$라 하자. $x$좌표 구간 $[x_A + 1, N]$의 $g(Q, S)$에 $w_B - w_A$를 더하면 된다. $B$가 존재하지 않을 경우 $w_B = 0$으로 취급한다.

 

같은 $y$좌표에서 여러 센서가 존재할 경우, 위쪽 방향 센서들을 먼저 순회하며 각 $S$에 대한 최댓값을 구한 후, 다음 $y$좌표로 넘어가기 위해 $f(P, S)$와 $g(Q, S)$들을 업데이트해야 한다.

 

또한, 같은 $x$좌표를 공유하는 $P$와 $Q$들이 있을 수 있다. 세그먼트 트리에서는 각 좌표마다 하나의 센서만을 나타내야 하므로, 적절한 순서를 통해 서로 다른 좌표를 배정해야 한다. 같은 $x$좌표 내에서는 오른쪽 방향 센서에 더 작은 좌표를 배정해야 $x_P = x_Q$인 경우에 대한 처리가 가능함에 유의하자.

 

따라서 $R$이 고정된 경우의 최댓값을 $O(N \log N)$에 구할 수 있어, 전체 문제를 $O(N^2 \log N)$에 해결할 수 있다.