2021 ICPC 서울 인터넷 예선

작년에 쓴 인예 풀이가 도움이 되었다는 말씀을 전해 주신 분들이 몇 있었다. 이번에도 문제가 백준 온라인 저지에서 상당 부분 채점이 되기 때문에 간단히 풀이를 적어보려고 한다. 자세하게 설명할 여력이 안 되는 점에는 양해를 구한다. 일단 DFG 외에는 백준에 전부 제출해서 맞은 코드들이지만, 풀이가 틀릴 가능성도 있다.

A. Best Student

여러 풀이가 있지만 내가 생각하기에 AC받기 제일 쉬운 풀이는 다음과 같다. (대회장 환경에 따라 시간 초과가 날 수도 있지만, 안 날 것 같다.)

구간을 크기 $B = 100$의 버킷 1000개로 쪼개자. 모든 $0 \le i \le j \le N / B$ 에 대해, 구간 $[iB, jB - 1]$ 에서 가장 많이 등장하는 숫자를 $O(N^2/B)$ 에 전처리한다.

이후 각 쿼리에 대해서, 쿼리의 왼쪽 / 오른쪽 끝에 있는 최대 $2B - 2$ 개의 원소들과, 해당 쿼리가 포함하는 가장 큰 버킷 구간 $[lB, rB - 1]$ 에서 가장 많이 등장하는 숫자를 모으자. 이 $2B - 1$ 개의 후보에 대해, 단순 이분탐색으로 해당 수가 실제로 구간에서 몇번 등장하는 지를 센다. 이들만 세어 줘도 그 중 최적해가 있음을 관찰할 수 있다.

쿼리 복잡도는 $O(B \log N)$ 이다. 고로 $B = \sqrt \frac{N^2}{Q \log N}$ 이 최적이고, 실제로 했을 때도 100이 가장 빨랐다.

B. Carrot Field

답은

1. 왼쪽 아래 모서리를 중심으로 하는 반지름 $L$ 의 270도 크기의 현과
2. 왼쪽 위 모서리를 중심으로 하는 반지름 $L - h$ 의 90도 크기의 현과
3. 오른쪽 아래 모서리를 중심으로 하는 반지름 $L - w$ 의 90도 크기의 현

의 합집합이다. 이것들은 $L$ 이 작기 때문에 잘 계산할 수 있다. (잘 계산한다 보다 적절한 단어를 모르겠다.)

이 중 2번과 3번은 교집합이 있을 수 있으니, 있다면 이것도 잘 빼주자.

C. Colorful Tower of Hanoi

옮기는 과정을 생각해 보면 대부분 의 경우 같은 크기의 블록들은 한꺼번에 움직여 줘야 한다. 그리고 같은 크기의 블록들을 한꺼번에 움직였을 경우, 그 순서가 뒤집힌다. 즉, $k \neq 1$ 인 경우, 블록에 적혀 있는 색은 해당 블록이 하노이 타워를 옮기면서 움직여야 하는 횟수의 홀짝성 을 나타낸다고 볼 수 있다. 예를 들어, 일반적으로 하노이 타워를 옮기면서 각 블록이 움직이는 횟수는, $n$ 번 블록이 1번, $n-1$ 번은 2번... $i$ 번 블록이 $2^{n-i}$ 번 움직인다.

각 블록이 움직이는 횟수가 원하는 홀짝성을 만족하게끔 하며, 총 횟수 합을 최소화해야 한다. 만약 현재 움직이는 횟수가 원하는 홀짝에 맞지 않으면, 억지로 움직이는 횟수를 늘려야 한다. 일반적으로

• A -> B 로 $n-1$ 번 블록 위를 옮기고
• A -> C 로 $n$ 번 블록을 옮기고
• B -> C 로 $n-1$ 번 블록 위를 옮기고

를 하는 것이 최적이라면

• A -> C 로 $n-1$ 번 블록 위를 옮기고
• A -> B 로 $n$ 번 블록을 옮기고
• C -> A 로 $n-1$ 번 블록 위를 옮기고
• B -> C 로 $n$ 번 블록을 옮기고
• A -> C 로 $n-1$ 번 블록 위를 옮기고

와 같이 2번 움직이고 $n-1$ 번 이후 블록을 3번 움직일 수 있다.

이제 각 블록의 이동 횟수를 $n$ 번부터 결정한다. $n$ 번 블록은 기본적으로 1번 움직여야 하는데, 만약 $n$ 번 블록을 짝수번 움직여야 한다면, $n$ 번 블록을 2번 움직이고 그 위 블록을 더 움직이게 할 수 있다.

이 논리를 반복하자면 다음과 같다. $i$ 번 블록을 $j$ 번 움직여야 한다면, 기본적으로 $j$ 번 움직이고, 그 위 블록을 $2j$ 번 움직인다. 만약 이 $j$ 가 홀짝이 맞지 않는다면, $j-1$ 번은 일반적으로 움직이지만, 남은 1번을 2번으로 업그레이드한다. 결국 $i$ 번 블록은 $j+1$ 번 움직이고, 그 위 블록은 $2j+1$ 번 움직이게 된다.

이를 반복하면 각 블록을 움직여야 하는 횟수가 모두 고정되지만, Wrong Answer를 받는다. 맨 위 가정을 다시 생각해야 한다. 같은 크기의 블록들은 대부분 한번에 움직이지만, $1$ 번 블록에 대해서는 예외적으로 이를 조금 줄여줄 수 있다. 예를 들어서,

1
B 3

의 답은 5이다. 이 케이스를 처리해 주면 만점을 받을 수 있다.

D. Drones

적당히 안에 들어간 점을 기준으로 좌표압축해주자. 최적해 집합에는 다음과 같은 두 성질이 있다.

• 포함 관계에 있는 두 구간이 같이 존재하지 않는다. 포함되는 구간을 지워도 여전히 해가 되기 때문이다.
• 위 조건에 의해, 구간을 시작점 순으로 정렬하면 끝점 역시 강하게 (strict) 증가한다. 세 구간이 겹치는 지점이 있으면, 이 중 시작점이 두번째인 구간을 지워도 여전히 해가 된다. 고로 최대 두 개의 구간만이 겹친다.

이제 최적해에서는 어느 위치에서도 최대 두 개의 구간만이 겹침을 알 수 있다. 이를 토대로 DP 점화식을 세울 수 있다. $dp_{i, j}$ 를, 구간들을 시작점 순으로 나열했을 때 마지막에 $i, j$ 번 구간이 있을 경우 최적해의 크기라고 하자. $e_i \le s_k \le e_j$ 를 만족하는 $k$ 가 다음 구간의 후보가 될 수 있다. 이를 나이브하게 전이해 주면 $O(n^3)$ 이고 세그트리 등을 사용하면 $O(n^2 \log n)$ 이 된다.

E. Histogram

$cost[i][j]$ 를, 구간 $[i, j]$ 를 하나의 버킷에 두는 비용이라고 하자. $cost[i][j] = \sum_{k = i}^{j} (x_i - m)^2$ 이다 ($m$ 은 평균). 이는 $x_i, \ldots, x_j$ 의 분산에 $n$ 을 곱한 것과 같으니, $cost[i][j] = \sum_{k = i}^{j} x_k^2 - \frac{(\sum_{k = i}^{j} x_k)^2}{j-i+1}$ 이다. 이 테이블은 $O(n^2)$ 에 채울 수 있다. 이제 전체 문제는 $dp[i][j] = min_{k < j}(dp[i-1][k] + cost[k+1][j])$ 라는 점화식으로 해결된다.

F. Logistical Warehouse

심플하게 될 법도 해서 꽤 많은 팀들을 낚은 문제이다. 찾아봤는데 그렇게 쉬운 풀이는 잘 나오지 않는다. 대충 이런 논문 이나 이런 논문에 비슷한 문제 (weighted discrete $p$-center problem on tree) 가 나와있는데 관심이 있다면 찾아보면 좋을 것 같다.

G. Moving Logs

막대기가 2개만 있을 때를 생각해 보면, 두 막대기의 $y$ 구간이 겹칠 경우 두 막대기를 동시에 뺄 수 없다. 정확히 말해, 이 중 $i$ 번 막대기가 $j$ 번 막대기보다 왼쪽에 있다면, $j$ 가 $i$ 보다 먼저 뽑혀야 한다. $N$ 개의 막대기들에 대해서, 두 막대기 $i, j$ 가 위와 같은 관계에 있을 경우 $i \rightarrow j$ 로 간선을 이어주자. 이 그래프는 DAG를 이룬다.

$Longest[v]$ 를 $v$ 번 막대기에서 시작하는 최장 경로의 길이라고 하자. $Longest[v] = i$ 인 막대기들은 모두 한 번에 뽑을 수 있다. 만약 이들을 한번에 뽑을 수 없다면, 이들 사이에 간선이 존재하고, $Longest[v] = i + 1$ 인 막대기가 그 중 존재한다는 모순에 도달하기 때문이다. 그래서, $Longest[v] = 0, 1, \ldots$ 인 순서대로 막대기 더미들을 뽑아갈 수 있다. 답은, $max_{v} (Longest[v]) + 1$ 이다. 이렇게 하면 $O(N^2)$ 풀이를 유도할 수 있다.

이를 최적화하기 위해서는 DAG의 크기를 줄여야 한다. $y$ 축이 증가하는 순서대로 스위핑을 하자. 선분은 해당 시점의 $x$ 축 정렬 기준으로 std::set 을 사용하여 관리한다. 선분을 삽입할 때 간선이 최대 2개가 생긴다 (해당 선분의 끝점의 왼쪽, 오른쪽에 있는 선분들), 선분을 제거할 때도, 해당 선분의 끝점의 왼쪽, 오른쪽 간에 새로운 간선이 생길 수 있다. 이렇게 할 경우 $O(N)$ 크기의 DAG를 만들 수 있다. 스위핑에 $O(N \log N)$, DP에 $O(N)$ 이 소모되어 시간 복잡도 $O(N \log N)$ 에 해결된다.

풀이는 쉬운 편이긴 하지만, 구현에서 꼬일 위험도 있고, F를 제외하면 다 이 문제보다 AC를 받기 쉬워서 3시간 대회에서 굳이 시도할 필요는 없는 문제인 것 같다.

H. Similarity

입력을 $(p_i, q_i)$ 쌍 순으로 정렬하자. $X[i] = (p_j < p_i, q_j < q_i$ 인 $j$ 의 개수$)$, $Y[i] = (p_i < p_j, q_i < q_j$ 인 $j$ 의 개수$)$ 라고 두면, 답은 $X[i]Y[i]$ 의 합이다. $X[i], Y[i]$ 는 Fenwick tree를 사용하여 하나 당 $\log N$ 에 계산할 수 있다.

I. Sport Climbing Combined

문제에서 주어진 규칙대로 두 선수를 비교하는 비교 함수를 구현한 후, 정렬을 하거나 최댓값을 3번 반복해서 지우는 식으로 답을 찾을 수 있다.

J. Ten

직사각형의 좌상단 모서리를 고정시키자. 모든 셀에 1 이상의 값이 적혀있기 때문에, 넓이가 10 초과인 직사각형은 고려할 필요가 없다. 넓이가 10 이하이기 위해서는 가로 길이나 세로 길이가 10 이하여야 한다. 가로 길이를 $1, 2, \ldots, 10$ 으로 고정시킨 후, 넓이가 10을 넘기지 않을 때까지 세로로 늘려나가면서, 넓이가 10인 지점에서 멈추면 된다. 좌상단 모서리를 고정시키는 데 $O(nm)$, 가로 길이 $10$ 개, 넓이가 $10$인 지점에서 멈추니까 세로로 가면서 최대 $10$개 셀을 방문. 고로 시간 복잡도는 $O(nm \times 100)$ 이다.

이 외에도 2차원 부분합 등 다양한 풀이가 있다.

참고로 이 문제는 $p_{i, j}$ 가 양수이기만 하면, 10이 아닌 임의의 숫자에 대해서 $O(nm(n+m))$ 에 해결할 수 있다.

K. Treasure Hunter

DAG에서 최소 Path Cover를 찾는 문제이다. Dilworth's Theorem을 사용하면, 이 문제는 모든 점들에 대해서 $r_i < r_j, c_i > c_j$ 가 성립하는 최대 크기 점 부분집합을 찾는 문제로 환원된다. 자세한 건 나의 블로그에 나와 있다. 이는 LIS 이니 $O(n \log n)$ 에 해결 가능하다.

이런 개념을 몰라도 그리디하게 풀 수 있다. 아마 std::set 에 현재 Chain의 열 번호를 관리하고 행이 증가하는 순으로 처리하며 가장 가까운 열을 매칭시키는 풀이일 것이다. 나도 옛날에 그런 풀이를 짰는데, 알고보니 그냥 내가 $O(n \log n)$ 에 LIS를 구하고 있었다는 사실을 깨닫고 놀란 적이 있었다.

L. Triangles

삼각형을 이루는 세 점 중, $(x, y)$ 좌표가 가장 작은 점을 고정시키자. 이것보다 좌표가 큰 점들은 모두 180도 각도 범위에 들어오니 CCW 각도순으로 정렬해 주자. 이제 두 점을 골라야 한다. 오른쪽 점 $i$ 을 고정시키고, 왼쪽 점의 후보 $j = i + 1, i + 2, \ldots $를 탐색한다. $i$ 를 기준으로 탐색할 때, $j$ 가 지금까지 만난 점 중 CCW 기준으로 가장 낮다면 (즉, $ccw(v_i, v_k, v_j) > 0$ 이 모든 $i < k < j$ 에 대해 성립하면) 원점과 $i, j$ 를 잇는 삼각형을 만들 수 있다. 이는 지금까지 만난 점 중 CCW 기준으로 가장 낮은 점을 그냥 관리해 주면 된다 (최솟값 갱신하는 것과 완전히 동일하다). 이렇게 하면 두 점을 고정시키고 $O(N)$ 루프이니 $O(N^3)$ 에 해결된다.