안녕하세요? seonah라는 핸들로 PS/알고리즘대회 커뮤니티들에서 활동 중인 김해울 입니다! 저희 Softeer에서는 커뮤니티 내에 대회 문항 공개에 대한 수요가 존재함을 인지하고 이를 반영하여 이번 본선에 사용된 문제들과 풀이를 동시에 공개하게 되었습니다!

이번 대회의 준비 과정에서 제 주된 업무는 문제 선정과 검수였습니다. 문제에 대한 평이 안 좋으면 어떡하지 계속 걱정했는데 문제가 좋았다는 분들이 많이 보여서 기분이 좋네요 ㅎㅎ... 좋게 봐주셔서 감사합니다!

문제 검수자로서 대회를 진행하면서 느낀 점 몇 가지를 적고 문제 해설로 넘어가도록 하겠습니다.

예선 때 많은 분이 좋은 성적을 보여주시고 다 푸신 분이 생각보다 빨리 나와서 본선 난이도를 더욱 어렵게 잡아야겠다고 다짐했었습니다...만 분명 더 어렵게 고른다고 골랐는데도 다 푸신 분이 예선 때만큼 빨리 나와서 많이 놀랐었네요... 다들 예선 때 힘을 숨기셨던건가... 더 힘을 줘야 했구나 생각했습니다.

추가로 가장 어려운 문제를 의도하고 선정했던 E번 문제의 경우 기존에 의도는 오일러 경로 테크닉, 리루팅, Square Root Decomposition, 최소 공통 조상 등을 복합적으로 사용하는 것이 의도였는데 정작 대회 때는 생각보다 센트로이드로 푸신 분들이 좀 있었습니다. 제가 센트로이드를 몰라서 의심도 못 했는데 이참에 배워보는 것도 좋겠죠?

개인적으로 본선 문제 중 가장 좋아하는 건 C번 탑의 높이입니다. 이진 탐색이 좋아하는 알고리즘이기도 하고 나이브한 풀이 에서 시작해서 이진 탐색을 사용해 최적화된 풀이로 발전시키는 과정이 꽤 아름답다고 생각합니다.

B번 문제가 비트마스킹에 익숙한지 아닌지, 그리고 자료구조에 저장하는 값을 어떤 거로 잡는지에 따라 실제 난이도랑 별개로 말리는 참가자가 있을 수 있다고 생각했습니다. 실제로 퍼솔(first solve)이 대회 시작 9분 만에 나오거나 A번은 해결 못 했지만 B번을 해결하신 분도 있었지만, 오히려 B번은 못 푸셨지만 C번을 푸신 분, 또는 40번(!) 넘는 제출 끝에 맞으시는 분이 나오는 등 확실히 해프닝이 다소 있었던 문제라고 느꼈습니다.

이번에 Softeer CodeRun의 운영에 참여하면서 커뮤니티에서만 봐왔던 다양한 분들과도 실제로 뵙고 소통할 기회가 되어 즐거웠습니다. 특히 대회가 끝나고 디스코드나 개인 블로그를 통해 좋은 후기를 남겨주신 분들 정말로 감사드립니다! 이제 문제 해설로 넘어가보도록 하겠습니다.

문제 해설

A - GPT식 숫자 비교 (Lv. 2)

' . '을 기준으로 문자열을 나눈 후, 양쪽을 정수 쌍으로 변환해 저장하고, 주어진 조건에 맞게 정렬해야 합니다. 이때 ' . '이 없는 경우(정수만 있는 경우)는 해당 수가 같은 정수부를 가진 다른 쌍들보다 먼저 위치하도록 해야 하므로, 소수부를 $-1$로 저장하는 트릭을 사용할 수 있습니다.

정렬 알고리즘의 복잡도가 $\mathcal{O}(N^2)$이어도 $N \le 1000$이므로 충분히 통과할 수 있습니다.

B - CPTI (Lv. 3)

$M \le 30$이므로, 주어진 이진 문자열을 32비트 정수로 저장 가능하며 $M$비트 정수로 취급할 수 있습니다.

각 사람의 CPTI를 순서대로 순회하며, 현재 사람의 CPTI를 나타내는 이진 문자열을 $M$비트 정수 $x$로 변환한다고 합시다. 그러면 그 사람이 친밀감을 느낄 수 있는 CPTI는 $x$와 최대 두 위치의 비트가 다른 $M$비트 정수입니다. 이를 위해 고려할 경우는 다음 세 가지입니다:

$x$와 동일한 값.
$x$와 한 개의 비트에서만 차이가 나는 값.
$x$와 두 개의 비트에서 차이가 나는 값.

이 값들이 사람들의 CPTI 목록에서 이전에 등장한 횟수를 전부 더하면 현재 사람이 친밀감을 느끼는 사람의 수를 구할 수 있습니다. 등장 횟수를 효율적으로 구하고 저장하기 위해 HashMap이나 TreeMap을 사용합니다.

2번, 3번에 해당하는 값들 모두 bitwise XOR 연산을 사용해 각각 $\mathcal{O}(M)$, $\mathcal{O}(M^2)$에 순회할 수 있습니다. 최종 시간 복잡도는 선택한 자료 구조에 따라 $\mathcal{O}(NM^2 \log N)$ 또는 $\mathcal{O}(NM^2)$이 됩니다.

한 가지 주의할 점은 각 사람에 대해 $\mathcal{O}(M^2)$개의 후보들의 등장 횟수를 Map에 저장하는 방식으로 문제를 풀 경우 Map의 원소의 크기가 너무 커져서 시간/메모리초과가 발생하게 됩니다. 따라서 각 단계에서 $x$의 등장 횟수만 Map에 누적해야 합니다.

C - 탑의 높이 (Lv. 4)

부분 문제로 나눠서 접근해 봅시다.

부분 문제 1

고정된 $x$에 대해 $H_x$를 최대화하는 것을 목표로 한다고 합시다. 모든 $x$를 순회하면서 $H_x$의 최댓값을 구하고, 그 중 최댓값을 구하면 답이 됩니다.

$H_i$를 $1$ 증가시키려면 어떤 조건을 만족해야 할지 생각해 봅시다. 현재 $H_i - 1 \le H_{i-1} \le H_i + 1$인 상황인데, 증가 이후에도 $H_i \le H_{i-1} \le H_i + 2$가 성립해야 할 것입니다. 두 부등식이 동시에 성립하려면 $H_i \le H_{i-1} \le H_i + 1$이어야 합니다. $H_{i+1}$ 역시 $H_i$ 또는 $H_i + 1$ 둘 중 하나여야 합니다.

$H_{i-1}$ 또는 $H_{i+1}$ 둘 중 하나라도 $H_i$미만이라면 $H_i$를 $1$ 증가시킬 수 없습니다.

이 점에서 착안하여, 나이브하게 생각해 보면 매번 어떤 원소를 증가시킬지를 아래와 같은 알고리즘을 통해 정할 수 있습니다.

$H_{x-1} < H_x$라면 : $H_{x-1}, H_{x-2}, \dots, H_1$ 순서대로 $1$ 증가시킬 수 있는 상황인지 확인하고, 증가 가능한 것을 찾으면 증가시킨다.
$H_{x+1} < H_x$라면 : $H_{x+1}, H_{x+2}, \dots, H_N$ 순서대로 $1$ 증가시킬 수 있는 상황인지 확인하고, 증가 가능한 것을 찾으면 증가시킨다.
위의 두 조건 모두 만족하지 않는다면 : $H_x$를 그냥 $1$ 증가시킨다.

이러한 전략을 통해 "$H_x$을 최대한 많이 증가시킨다"는 목표를 최소한의 횟수로 달성할 수 있습니다.

$x$를 정하는 데에 $\mathcal{O}(N)$, 연산 횟수가 $K$, 각 연산에서 어떤 원소를 증가시킬지 정하는 데에 $\mathcal{O}(N)$이므로, 총 시간 복잡도는 $\mathcal{O}(N^2K)$입니다.

부분 문제 2

위의 알고리즘에서 $x = 10$이고, $H_9 < H_{10}$이며 $H_6 \ge H_7 < H_8 < H_9 < H_{10}$이어서 $H_7$을 증가시켰다고 합시다.

그러면 $H_7 = H_8$이 되어서, 바로 다음에는 $H_8$을 증가시킬 것입니다.

그러면 $H_8 = H_9$이 되어서, 바로 다음에는 $H_9$을 증가시킬 것입니다.

이런 식으로 $H_i$를 $1$증가시킨 경우, 그다음에 $x$ 쪽으로 가까운 원소를 $1$증가시키게 됨을 알 수 있다. 따라서 $x$에서 $i$까지 매번 반복해서 찾아갈 필요가 없게 됩니다.

평균적으로 amortized $\mathcal{O}(1)$ 시간에 어떤 원소를 증가시킬지 알 수 있게 되었으므로, 총 시간 복잡도는 $\mathcal{O}(NK)$입니다.

부분 문제 3

$H_x$를 $h$로 만들기 위해 최소 몇 회의 연산이 필요한지를 계산하는 함수 $f(x, h)$를 작성해 봅시다. $f(x, h_0) \le K$인 가장 큰 $h_0$를 이분 탐색을 통해 구할 수 있고, 이를 위해 $\mathcal{O}( \log \max (H_i))$회의 함수 실행이 필요합니다.

예시를 위해 $N = 15$이고, 높이가 아래와 같은 상황이라고 합시다.

..##..#.....#..
.#####.#..#####
###############
123456789012345

$H_7$이 $7$이 될 수 있는지를 판단하고자 합니다. 아래 그림의 ' * ' 위치에 $H_7$의 꼭대기가 위치해야 합니다. 좌우로 높이 차이가 $1$이하려면, 양 옆의 높이는 $6$ 이하, 두 칸 차이 위치는 높이가 $5$ 이하, ... 여야 할 것입니다. 아래 그림에서 ' / ', ' \ ' 그래프가 높이 범위를 표현한 것입니다. 대문자 ' X ' 는 이 그래프와 기존 히스토그램이 겹치는 위치입니다. 그래프와 히스토그램 사이의 영역만큼은 반드시 연산을 통해 높이를 높여 줘야 합니다.

...............
...............
......*........
...../.\.......
..../...\......
.../.....\.....
..X#..#...\.#..
.X####.#..#X###
X###########X##
123456789012345

왼쪽으로는 $3$번째 열에서, 오른쪽으로는 $12$번째 열에서 겹칩니다. 그런데, 이렇게 한번 겹치고 나면 그 왼쪽 (1 ~ 3 열) 이나 오른쪽 (12 ~ 15열)은 건드리지 않아도 됩니다. 그래프의 기울기가 $1$ 또는 $-1$인데, 인접한 높이 차이가 $1$이하이므로, $H_i$가 그래프 아래로 내려갈 수 없기 때문입니다. (최악의 경우에도 그래프와 겹친다)

따라서, 양옆으로 최초로 겹치는 열을 찾아서, 그 사이의 빈공간의 넓이를 구해 주면 됩니다. 이는 $\mathcal{O}(N)$에 처리할 수 있습니다. $x$를 정하는 데에 $\mathcal{O}(N)$, 이분 탐색을 하는 데에 $\mathcal{O}( \log \max (H_i))$, 함수 실행에 $\mathcal{O}(N)$ 시간이 필요하므로, 총 시간복잡도는 $\mathcal{O}(N^2 \log \max (H_i))$입니다.

부분문제 4

위의 풀이에서 찾고 싶은 것은, $H_i \ge h - \left| x - i \right|$ 인 $i$의 구간 $[l , r]$입니다. $i \le x$일 때는, 위의 식은 $H_i \ge h - x + i \rightarrow H_i - i \ge h - x \rightarrow i - H_i \le x - h$ 로 정리할 수 있습니다.

$i - H_i$는 단조증가 하기 때문에, 이분 탐색을 통해 $l$을 구할 수 있습니다.

$i \ge x$일 때는, 위의 식은 $H_i \le h + x - i \rightarrow i + H_i \le x + h$ 로 정리할 수 있습니다. $i + H_i$는 단조증가 하기 때문에, 이분 탐색을 통해 $r$을 구할 수 있습니다.

$i \pm H_i$ 가 단조증가 하는 이유 : $-1 \le H_{i+1} - H_i \le 1$의 양변에 $1$을 더하면, $0 \le (H_{i+1} + i + 1) - (H_i + i) \le 2$

쉽게 말해, 위 그림에서 그래프가 처음으로 왼쪽으로 겹치는 지점, 처음으로 오른쪽으로 겹치는 지점을 구하는 것입니다.

이렇게 구간을 구하고 나면, 구해야 할 넓이는 (그래프와 $x$축 사이의 넓이) - (히스토그램의 넓이) 로 계산할 수 있습니다. 이 넓이가 필요한 연산 횟수와 일치하게 됩니다.

그래프와 $x$축 사이의 넓이는, 등차수열의 합 공식을 통해 $\mathcal{O}(1)$시간에 구할 수 있습니다. C++과 같이 정수형의 범위가 크지 않을 경우, 오버플로우가 날 수 있으므로, 넓이가 너무 넓으면 적절한 INF값으로 간주하는 식으로 방지해야 합니다. (__int128_t를 사용하는 방법도 있습니다.) Java등의 언어의 내장된 Big Integer 구현체를 사용할 경우 만약 구현체 속도가 느리다면 큰 수 연산이 필요한 경우에만 사용하는 식으로 시간초과를 방지 해야 합니다.

히스토그램의 넓이는 $H_i$의 누적합 (prefix sum)을 계산해 두면 $\mathcal{O}(1)$시간에 구할 수 있습니다.

이제 함수 실행에 총 $\mathcal{O}(\log N)$시간이 필요하므로, 총 시간 복잡도는 $\mathcal{O}(N \log N \log max(H_i))$입니다.

D - 레이저 게임 (Lv. 5)

보드판의 크기 $N$과 각 셀의 값을 입력받습니다. 각 행에 대한 누적합을 미리 계산하여 나중에 특정 열 범위의 합을 빠르게 구할 수 있도록 준비합니다. 모든 가능한 열 범위에 대해 반복하면서, 해당 범위 내 각 행의 합을 계산합니다.

플레이어 $B$는 항상 모든 구간에 레이저를 발사하는 방식으로 답을 구성할 수 있습니다. 따라서 플레이어 $B$의 가로, 세로 방향은 크게 중요하지 않습니다. 즉, 플레이어 $A$는 가로, 세로를 정할 때 플레이어 $B$의 레이저를 신경쓰지 않아도 됩니다.

이제 가능한 직사각형의 두 행의 가능한 모든 조합을 고정하는 방식으로 접근합니다. 직사각형의 행 두개를 고정하게 될 경우, 격자를 1차원으로 줄여서 생각할 수 있게 됩니다. 이렇게 모델링하면 플레이어 $A$의 레이저 발사를, 특정 구간을 모두 (직사각형의 행의 길이 $l$) 만큼으로 변경한다는 연산으로 이해할 수 있습니다.

이제, 구간의 상태를 정의합니다. 상태는 $1, 2, 3$으로 이루어져 있으며, $1$은 레이저가 아직 발사되지 않은 상태, $2$는 현재 레이저가 발사되고 있는 상태, $3$은 이미 레이저가 발사되고 지나간 상태로 정의합니다. 그러면 다음과 같이 DP의 점화식을 세울 수 있게 됩니다.

$DP[i][j]$ : $i$번째 인덱스에서, $j$상태에 있을때 만들어질 수 있는 최대 구간합이라고 정의합니다. 위 상태에 따르면,

$$DP[i][3] = max(0, max(dp[i - 1][2], dp[i - 1][3]) + a[i])$$

$$DP[i][2] = max(0, max(dp[i - 1][1], dp[i - 1][2]) + l)$$

$$DP[i][1] = max(0, dp[i - 1][1] + a[i])$$

점화식을 바탕으로 A와 B의 레이저 발사에 따른 값을 DP에 모델링해 업데이트합니다. 또한 보드판을 90도 회전시킨 후 동일한 과정을 반복하여 가로와 세로 방향 모두를 고려합니다. 최종적으로 계산된 최대 점수에 $2$를 곱하여 결과를 출력합니다. 최종 시간 복잡도는 $\mathcal{O}(N^3)$입니다.

E - 축제 (Lv. 5)

2번 이벤트가 없는 부분 문제를 고려해 봅시다. 각 정점마다 따로 계산을 진행하기에는 너무 느립니다. 먼저, 각 가지의 길이가 답에 어떤 영향을 미치는지 생각해 봅시다. 어떤 가지를 기준으로 트리를 나눈다고 생각해 보면, 양쪽에 서브트리가 두 개 달린 구조가 됩니다. 한쪽 서브트리에 있는 모든 깐프들은, 반대쪽 서브트리에서 축제가 열린다면 반드시 이 가지를 지나야 합니다.

즉, 가지의 길이를 $L$, 한쪽 서브트리에 있는 깐프의 총 수를 $G$라고 하면, 반대편 서브트리에서 축제가 열릴 때의 답은 모두 $L \times G$만큼 증가해야 합니다.

이제 트리의 초기 상태에 대해 각 정점에서 축제가 열렸을 때 세계수에 가해지는 부담을 계산해 봅시다. 이는 오일러 경로 테크닉을 이용한 서브트리 누적합과 리루팅 기법을 사용해 $\mathcal{O}(N)$에 계산할 수 있습니다.

우선 오일러 경로 테크닉을 이용해 어떤 정점에 들어온 시점과 나간 시점을 기록합니다. 이 과정에서 특정 서브트리에 속한 정점들은 들어온 시점을 기준으로 나열하면 연속한 번호를 가지게 됩니다. $1$번 정점이 루트라고 가정해 봅시다. 그리고 어떤 정점 $x$를 루트로 하는 서브트리에 사는 깐프의 수를 $W$, 전체 트리에 사는 깐프의 수를 $T$, $x$와 $x$의 부모를 연결하는 가지의 길이를 $L$, $x$에 들어온 시점을 $in_x$ 나간 시점을 $out_x$라고 합시다. 추가로 누적합 계산을 위한 배열 $pre$를 정의합니다. 처음에 $pre$의 모든 값은 $0$입니다.

$x$에 가까운 깐프들이 $x$와 $x$의 부모 사이 가지를 타고 $x$의 부모로 이동하면서 생기는 부담은 $W \times L$입니다. 이를 $S_1$이라 합시다. $x$의 부모 쪽에 가까운 깐프들이 이 가지를 타고 이동하면서 생기는 부담은 $(T - W) \times L$입니다. 이를 $S_2$이라 합시다.

루트를 $1$번으로 고정했으니 일단 $pre_1$에 $S_1$을 더합니다. 그리고 $pre_{in_x}$에 $S_2 - S_1$을 더하고 $pre_{out_x + 1}$에 $S_1 - S_2$를 더합니다. 오일러 경로 테크닉과 동일한 순서대로 DFS 순회를 하며 이 과정을 모든 정점에 대해 반복해준 후 $pre_i = pre_i + pre_{i - 1}$을 통해 누적합을 계산해 주면 $pre_{in_x}$에 저장된 값은 $x$번 정점에서 축제가 열릴 때 세계수에 가해지는 부담이 됩니다.

왜 그런지 설명을 해보겠습니다. $1$번 정점이 루트임을 가정했으니 $pre_1$은 $1$번 정점에서 축제가 열릴 때의 부담과 같음은 자명합니다 (부모를 따라가는 과정을 전부 더하면 루트로 이동하게 되니까).

동시에 $pre_1$은 모든 정점에 대해 그 정점을 루트로 하는 서브트리의 모든 깐프들이 부모로 이동하면서 생기는 부담을 가지고 있습니다 ($S_1$들의 합). 그러면 $x$를 루트로 하는 서브트리의 정점들에 대해서 답을 구할 때는 $pre_1$에서 정점 $x$에서 계산한 $S_1$을 빼줘야 합니다. 그리고 추가로 $x$의 부모 쪽에서 $x$로 오면서 생기는 부담, 즉, $S_2$를 더해줘야 합니다.

따라서 $pre_{in_x}$에는 $S_2 - S_1$을 더해둔 채로 누적합을 계산하면 자연스럽게 위 두 값을 더하고 빼는 과정이 진행됩니다. $x$를 루트로 하는 서브트리를 벗어날 때는 이 두 값의 영향이 없어져야 하기 때문에 $-(S_2 - S_1) = S_1 - S_2$를 $pre_{out_x + 1}$에 더하는 것입니다.

DFS 순회에 $\mathcal{O}(N)$, 누적합 계산에 $\mathcal{O}(N)$이므로 초기 상태에 대한 답을 구하는데 총 시간 복잡도는 $\mathcal{O}(N)$입니다. 참고용으로 아래에 자바 솔루션의 일부분을 첨부했습니다.

void dfs(int cur, int dep, int ln, boolean[] vis) {
    d[cur] = dep;
    vis[cur] = true;
    len[cur] = ln;
    in[cur] = ++time;
    for (int[] edge : edges.get(cur)) {
        int nxt = edge[0];
        int l = edge[1];
        if (vis[nxt]) continue;
        par[nxt] = cur;
        dfs(nxt, dep + 1, ln + l, vis);
    }
    out[cur] = time;
}


void dfs2(int cur, int par) {
    weight[cur] = val[cur];
    for (int[] edge : edges.get(cur)) {
        int nxt = edge[0];
        long l = edge[1];
        if (nxt != par) {
            dfs2(nxt, cur);
            weight[cur] += weight[nxt];


            long s1 = weight[nxt] * l;
            long s2 = (total - weight[nxt]) * l;
            int st = (int) in[nxt];
            int en = (int) out[nxt];
            presum[1] += s1;
            presum[st] += s2 - s1;
            presum[en + 1] -= s2 - s1;
        }
    }
}


void reroot() {
    Arrays.fill(presum, 0);
    dfs2(1, -1);
    for (int i = 1; i <= 2 * N; i++) {
        presum[i] += presum[i - 1];
    }
}

이제 2번 이벤트를 포함해 $G$값(깐프의 수)에 변화가 있는 상황을 고려해봅시다.

2번 이벤트가 적당히 쌓이기 전까지는 $G$값을 업데이트 하지 않고, 미리 계산된 값에다가 업데이트가 예정되어 있는 $G$값에 그때 그때 거리를 곱한 다음 더해서 답을 내는 것입니다.

트리에서 두 정점 사이의 거리는 최소 공통 조상 알고리즘을 통해 $\mathcal{O}(\log N)$에 구할 수 있습니다. 즉, 2번 이벤트의 업데이트를 최대 $C$개 쌓는다고 하면 쿼리마다 $\mathcal{O}(C \log N)$의 시간이 걸리고 총 $\mathcal{O}(QC \log N)$의 시간이 걸리게 됩니다. 그리고 업데이트가 $C$개 쌓였다면 실제 $G$값을 새롭게 업데이트한 다음 다시 답을 구합니다.

업데이트 과정은 단순히 초기 상태에 대해 답을 구했듯이 다시 답을 계산하면 되므로 $\mathcal{O}(N)$이 걸리고 $C$번의 이벤트 당 한번 일어나기 때문에, 총 $\mathcal{O}(\frac{Q}{C}N)$시간이 걸리게 됩니다.

$C$를 $\sqrt{Q}$정도로 정하면, $\mathcal{O}(\sqrt{Q}(Q \log N+N))$의 시간에 충분히 빠르게 문제를 해결할 수 있습니다.

이상으로 문제 해설을 마치겠습니다! 다시 한번 Softeer CodeRun에 관심 가져 주시고 참가해 주신 여러분 모두 감사합니다! 위 문제들은 [연습문제] 에서 풀어볼 수 있으니, 대회에 참가 못 하신 분들 또는 문제를 다시 풀어보고 싶으신 분들은 한번 풀어 보시는 걸 추천해 드립니다! 앞으로도 Softeer에 많은 관심 부탁드립니다. 감사합니다!

소프티어

블로그

Softeer CodeRun 본선 대회 후기 및 문제 해설