2024 KAIST RUN Spring Open Contest

올해 KAIST에서 열린 런 봄 대회에 검수진으로 참여했다. 처음으로 온사이트 대회를 검수해 보아서 신기한 경험을 많이 해 본 것 같다. 풍선을 달아 주거나 온사이트 대회 안내 등의 경험을 처음으로 해 봐서 재미있었다.

 

문제 셋은 전체적으로 좋지만, (특히 어려운 문제의 경우) 구현량이 많아서 제한 시간 내에 풀기 힘든 셋이었다고 생각한다. G는 특히 기억에 남는 문제로 최근에 본 문제들 중에서도 매우 좋은 편에 속하는 것 같다.

A. RUN 수

뺄 수 있는 가장 큰 수를 그리디하게 빼면 된다. 증명이 생각보다 어려운데, 재미있으니 스스로 해 볼 가치가 있다고 생각한다.

B. 문자열과 쿼리

$f(i, j, k)$의 값을 더하는 것으로 생각하지 말고, 새로운 함수 $g(i, j)$를 정의하자. $f(i, j, k)$는 $k$가 증가함에 따라 $1$에서 $0$으로 딱 한 번 바뀌는 시점이 있는데, 여기서 영감을 얻어 $g(i, j)$를 $f(i, j, k) = 1$인 최소의 $k$로 정의할 것이다. 이렇게 하면 $\sum_{k=1}^{\min(n-i+1,n-j+1)} f(i, j, k) = g(i, j)$가 되어 $g(i, j)$들의 합만 구하면 된다.

 

$g(i, j)$를 하나당 $O(n )$에 구하면 $O(n^3)$에 문제를 해결할 수 있다. 하지만 잘 생각해 보면 $g(i, j)$는 $g(i+1, j+1)$의 값을 이용해 $O(1)$에 구할 수 있다. 따라서 $(i, j)$를 큰 값의 순서쌍부터 처리하면 Dynamic Programming의 느낌으로 전체 $g$ 테이블을 구할 수 있다. 이제 남은 값들을 다 합하면 문제를 $O(n^2)$에 해결할 수 있다.

C. Constructing Graph

일단 가능성 판별은 Floyd Warshall을 한 번 돌리면 된다.

 

이제 최소 가중치로 construct 조건만 잘 만들어보자. 우선 $O(N^4)$ 풀이는 쉽다. 가장 가중치가 작은 간선부터 만들어가면서, 해당 간선이 꼭 필요한 경우에만 만들어주는 그리디가 자명하게 성립한다. 간선 하나하나가 추가될 때마다 Floyd Warshall을 돌려 주면 $O(N^4)$에 해결할 수 있다.

 

$O(N^3)$에 문제를 해결하기 위해서는 각 정점에서 Dijkstra를 돌려 $dist[i][j]$와 $dist2[i][j]$를 찾아주면 된다. $dist[i][j]$는 $i$번 정점에서 $j$번 정점으로 가는 최단경로이고, $dist2[i][j]$는 두 번째 최단경로이다. $dist[i][j]$는 당연히 $D_{i, j}$와 같다. $dist2[i][j]$가 만약 $D_{i, j}$와 같다면 해당 간선은 굳이 필요가 없다. 그렇지 않다면 해당 간선은 더하지 않아도 된다.

 

더 쉬운 풀이가 있을 것 같은데, 결국 정점 $i$에서 $j$로 갈 때 간선 $(i, j)$를 사용하지 않고도 최단거리로 갈 수 있는지를 보면 되는 것이기 때문에, Floyd-Warshall을 하되 초깃값을 조금 다르게 넣어 간선을 최소 두 개 이상 거친 길이만 나오게 하는 식으로 풀 수도 있을 것 같다.

D. Closet

일단 답에 대한 이분 탐색을 하자. 답이 $X$가 되는 것이 가능한지 판별하려면 주어진 수열에서 길이 $N-M$ 이상의 almost beautiful sequence가 있는지 찾으면 된다. 이게 존재하는지 찾는 것은 LIS를 Segment Tree로 찾는 방법을 조금만 변형해서 찾으면 된다. 시간 복잡도는 $O(N \log^2 N)$인데, 상수가 조금 커서 시간이 오래 걸린다. 세그먼트 트리가 prefix max query만 주어진다는 점을 이용해서 Fenwick Tree로 구현을 하면 시간이 많이 줄어든다.

E. Two Histograms

일단 어떤 그림이 최종적으로 가능한 형태인지를 생각해보자. 편의상 아래/왼쪽부터 시작해 좌표평면 방향으로 격자점에 좌표를 매기자. 가장 왼쪽 아래 점이 $(1, 1)$이고, 가장 오른쪽 위 점이 $(N, N)$이다. 또 $x=t$에서 위쪽 방향 히스토그램 높이를 $U_t$, $y=t$에서 오른쪽 방향 히스토그램 높이를 $R_t$라고 하자.

 

$K>1$일 때 해를 만드는 것이 항상 가능하다는 것을 증명할 수 있다. $R_y$를 모두 $N$으로 잡고, $U_x$는 $k$개씩 번갈아가며 $N$과 $0$을 넣으면 된다.

 

이제 $y$좌표별로 생각해 보자. 한 $y$좌표에 여러 직사각형이 있다고 해 보자. 이 경우 $R_y$는 최대 마지막 정사각형의 첫 번째 칸까지는 닿아야 하기 때문에, 이전의 정사각형들은 모두 $U_x$를 한쪽에서 내리는 방법으로만 제어할 수 있다. 이 경우 특정 관계가 생긴다: 두 정수 $a$와 $b$에 대해, $U_a \ge y > U_b$거나 $U_b \ge y > U_a$여야 한다. $U_a \ge y$이면 $t$점을 얻고, $U_b \le y$이면 $u$점을 얻는다. 이런 식의 관계를 일단 모두 모아 두자.

 

또한, 각 $y$좌표의 맨 오른쪽에 있는 행에서는 조금 다른 관계가 생긴다. 만약 오른쪽 칸을 검은색으로 만들고 싶은 경우 이전과 같이 $U_b \ge y > U_a$ 조건을 만족해야 하지만, 왼쪽 칸을 검은색으로 만들고 싶은 경우 $U_a \ge y$ 조건만 만족하면 되기 때문이다. $U_b$에 대한 제한이 사라진다. 이런 관계도 모두 모아 두자.

 

이제 각 열($x$좌표)에 대한 관계를 모았으니, $U_x$들을 잘 맞춰 점수를 최대화해 보자. $k$로 나눈 나머지가 같은 것들끼리 보면 좋다. $k$칸씩 건너뛰며 번호를 $1$, $2$, $\cdots$로 붙였다고 생각해보자. 그럼 가지고 있는 조건은 다음과 같다.

• $U_{i} \ge y > U_{i+1}$이거나 $U_{i+1} \ge y > U_{i}$이고, 전자일 경우 $a_i$점, 후자일 경우 $b_i$점을 얻는다. (입력에 주어진 $a_i$, $b_i$와는 다를 수 있다.)
• $U_i \ge y$거나 $U_{i+1} \ge y$이고, 전자일 경우 $c_i$점, 전자가 아니고 후자일 경우 $d_i$점을 얻는다.
• 각 $i$에 대해 $U_i$와 $U_{i+1}$ 사이의 조건은 여러 개가 중첩되어 있을 수 있다. 위 두 종류의 조건을 차례대호 1번 유형, 2번 유형이라고 하자. 여러 유형의 중첩을 처리하는 방법은 다음과 같다.
• 1번 유형끼리 중첩될 경우, 다음과 같이 된다: $U_i$ 와 $U_{i+1}$ 중 정확히 하나는 $p_i$ 이하이고, 정확히 하나는 $q_i$ 이상이다. ($p_i < q_i$) 새로운 유형이 나왔는데, 기존의 1번 유형이 여기에 포함된다고 해석할 수 있으므로, 그냥 이걸 1번 유형의 정의로 바꾸자.
• 2번 유형끼리 중첩될 경우, 케이스워크를 하면서 잘 계산해 보면 이 $x$좌표에서 얻을 수 있는 점수의 합이 나오는데, 크게 직전 행이 가장 높은 $y$값 이상인지 미만인지로 케이스를 나누면 두 가지 경우가 나올 것이다.

이 조건들을 모두 모은 뒤, $U_i$가 속하는 구간들로 DP를 하면 문제를 해결할 수 있다. 이 DP를 설명하는 게 조금 까다로운데, 각 열에서의 DP 결과가 $U_i \in [L_j, R_j]$ 일 때 최댓값 얼마 같은 식으로 나오고, 이 구간의 개수 합이 $O(N)$이라 해결할 수 있다. 총 시간 복잡도는 $O(N \log N)$이다.

F. Discount Event

$Q$개의 쿼리를 처리해야 하는데, 각 쿼리는 $u-v$ 경로의 정점을 모두 하나로 합친 뒤, 지름을 구하는 문제이다. 크게 세 가지 케이스가 있다.

• 지름이 $u-v$ 경로의 점을 지나지 않고, $u-v$ 경로에서 가장 가까운 점이 $u$ 또는 $v$이다.
• 지름이 $u-v$ 경로의 점을 지나지 않고, $u-v$ 경로에서 가장 가까운 점이 $u$ 또는 $v$가 아닌 경로 사이의 점이다.
• 지름이 $u-v$ 경로의 점을 지난다.

각 케이스를 따로 처리해 보자.

첫 번째 케이스

$v$를 루트로 했을 때 $u$의 서브트리 내에서 지름을 찾아 주면 된다. 이러면 해당 서브트리에서 LCA가 $u$인 경우도 포함되겠지만 이건 포함되어도 좋다. 각 정점에 대해, 트리 DP로 $diam[x]$ ($x$의 서브트리의 지름) 전처리를 하고, 이걸 양방향으로 쓰는 방법으로 $O(1)$에 (비교적) 쉽게 구할 수 있다.

두 번째 케이스

위에서 한 DP를 기본적으로 차용한다. $val[x]$를 $x$의 부모 $p$에서 $x$ 방향 노드들을 무시하고 구한 $diam[p]$의 최댓값이라고 하자. 이제 경로에서 $val[x]$ 최대를 구하는 sparse table을 하나 만들고, 경로의 LCA에서 추가적으로 처리를 해 주면 쿼리당 $O(\log N)$에 해결할 수 있다.

세 번째 케이스

$diam[x]$와 마찬가지로, 가장 먼 점까지의 거리를 전처리해 두면 같은 방식으로 문제를 해결해줄 수 있다. 이걸 각 점에 대해서 구해준 뒤 가장 큰 두 개를 더해 주면 쿼리당 $O(\log N)$에 해결할 수 있다.

결과적으로 문제를 $O(Q \log N)$에 해결할 수 있다. 구현이 정말 복잡하다.

G. 하나 둘 셋

$N \le 300 , 000$

일단 가장 먼저 생각해볼 만한 것은 마지막으로 남아 있을 수 있는 수열의 상태이다. $4$나 $8$의 합을 만드는 연속구간이 없는 상태를 말하는 것이다. 그리고 실제로 세어 보면 그 형태가 극히 제한됨을 확인할 수 있다. 가능한 형태들은 다음과 같다.

• 3만 있는 경우 (길이 제한이 없다.)
• $111$, $123$, $212$, $232$의 부분문자열 (뒤집는 경우도 고려)
• 아무것도 남지 않는다.

이렇게 최종 형태로 남을 수 있는 문자열의 종류는 꽤 적다. 우리는 다음과 같은 관찰을 해야 한다.

• 초기 수열에서 어떤 구간 $[l, r]$ 만을 제거할 수 있을 조건은 구간 합이 $4$의 배수이고 (1의 개수) + (2의 개수 × 2)가 (3의 개수) 이상임과 동치이다.

따라서 위 조건을 만족하는 구간들을 제거해 주면서 세그먼트 트리로 DP를 한다는 느낌으로 문제를 해결하면 $O(N \log N)$에 답을 구할 수 있다. 이 풀이를 구현하면 60점을 받을 수 있다.

 

역추적 역시 간단하다. 세그먼트 트리에 값을 업데이트할 때 인덱스까지 같이 업데이트하면 해당 값이 어디서 왔는지를 알 수 있다. 이제 역추적을 하면 제거해야 하는 수들의 구간을 얻을 수 있다. 이 구간들은 앞에서 보았듯이 $3$이 그리 많지 않은, 구간 합이 $4$의 배수인 구간을 이룰 것이다. 여기서는 먼저 $3$을 양옆의 $1$이나 $2$ 등으로 최대한 제거하고, 남은 $1$과 $2$를 앞에서부터 그리디하게 보면서 제거해 주면 된다. 이렇게 역추적까지 짜면 100점을 얻을 수 있다.

추가: $O(N)$에 푸는 방법

문제는 $O(N \log N)$으로 출제되긴 했지만, 놀랍게도 이 문제는 선형에 풀 수 있다. 물론 아무리 봐도 DP 식은 로그가 떨어질 것 같지 않게 생겼다. 이 문제에서는 정말 특이한 방법으로 로그를 뗀다.

 

일단 위 풀이에서 세그먼트 트리 대신 셋을 관리해도 문제를 풀 수 있다는 것을 생각해 보자. DP를 조금 더 명확히 서술하면 다음과 같다. 먼저 $Sum[i]$를 정의하는데, $Sum[i] = Sum[i-1] + arr[i]$이다. 또한 $Score[i]$를 정의하는데, $Score[i] = Score[i-1] + f(arr[i])$이다. $f(1)=1$, $f(2)=2$, $f(3)=-1$이다. $DP[x]$를 $x$까지 얻을 수 있는 (최소 합, 최고 가치 합)이라고 하자. $DP[x]$는 $DP[x-1]$에 수 $arr[x]$를 추가해서 얻는 방법과 $w < x$인 임의의 $w$에 대해 구간 $[w+1 , x]$를 제거한 뒤 $DP[w]$을 그대로 가지고 오는 방법이 있다. 구간 $[w+1, x]$를 통째로 제거할 필요 충분 조건은 이미 앞에서 보였는데, 이를 여기서 정의한 변수들로 나타내면 $(Sum[x] - Sum[w]) \equiv 0 \bmod 4$여야 하고 $Score[w] \le Score[x]$여야 한다. 이때 $Score[x]$의 위치에 $DP[x]$를 저장하는 셋을 관리함으로써 문제를 풀 수 있다.

 

앞에서는 Segment Tree를 썼기 때문에 적당한 prefix 구간 $[-\infty, s]$에서 set에 든 값의 최솟값을 찾는 연산을 할 수 있었는데, 이걸 셋으로 관리하는 방법은 간단하다. $s$가 증가할수록 감소하는 값들을 체인으로 관리해 주면 된다. 대략 그림으로 그려 보면 아래와 같다. 선으로 이어진 정보들만 실제로 prefix minimum이 될 수 있으므로 set에 관리해 주고, 나머지 값은 버려 주면 된다.

 

 

위에서 만든 셋에 $x$까지 함께 저장하면 역추적 역시 가능해진다. 이렇게 하면 아까와 비슷하게 $O(N \log N)$에 문제를 풀 수 있다.

 

중요한 사실은 쿼리와 업데이트 위치가 $Score[x]$라는 것이다. $Score[x]$는 $i$가 $1$부터 $N$까지 증가할 때 총 변화량이 $O(N)$ 미만이다. 따라서, Set을 사용하지 않고 연결 리스트를 통해 DP의 정보를 관리해 주면 총 이동거리가 $O(N)$이므로 문제를 $O(N)$, 즉 선형에 풀 수 있게 된다.

H. Tree Kadane

일단 이걸 쿼리별로 $O(N)$에 푼다고 생각한다면 어떻게 풀어야 할까? $DP[x]$를 $x$ 서브트리에서 $x$를 포함하는 연결 성분의 최대 합이라고 해 보자. $DP[x]$는 $A[x]$에 양수인 $DP[y]$들을 모두 합한 값이 된다. (이때 $y$는 $x$의 모든 자식을 말한다.) $DP[x]$의 최댓값이 답이 될 것이다.

 

이걸 쿼리와 함께 처리하는 방법은, 조금 사전지식성이 강하긴 하지만, 비교적 간단하다. Dynamic Tree DP를 하면 된다. 편의상 $DP[x]$ 말고 $ans[x]$라는 걸 정의하는데, $ans[x]$는 $x$를 포함해, $x$의 모든 자손들에 대해 $DP[x]$의 최댓값이다. 이러면 모든 $DP$ 값을 볼 필요 없이 $ans[root]$가 답이 된다는 장점이 있다. 이제 남은 부분은 진짜 깡으로 Dynamic Tree DP를 짜면 되고, 그러면 아마도 $O(Q \log^2 N)$ 정도에 풀릴 것이다. 구현을 잘 하면 로그를 하나 더 줄일 수도 있을 텐데, 거기까지 생각해 보진 않았다.