IOI 2023 Day 1

(9/5 23:27 - 다 썼습니다)

IOI 2023 Day 1 대회가 종료되었다. 올해 대회의 개최지는 헝가리로, 한국 팀은 2019년 이후 처음으로 현지에서 오프라인으로 대회를 진행하고 있다.

한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라.

• 이동현, 52 / 70 / 65.5, 187.5점, 29등
• 반딧불, 43 / 60 / 65.5, 168.5점, 33등
• 박상훈, 43 / 60 / 65.5, 168.5점, 33등
• 이성호, 43 / 40 / 61, 144점, 56등

모든 학생들의 성적이 금메달 / 은메달의 경계선에서 멀지 않아서 Day 2의 결과가 매우 중요할 것으로 보인다. 한국 학생들은 매년 Day 2 결과가 더 좋은 편이다. Day 2에서 좋은 결과를 내기를 소망한다.

문제는 예년 대비 상당히 어려운 편이다. 만점자 수만 봐서는 2018 Day 2, 2021 Day 1보다도 적은, 거의 전례가 없는 수준이다 (11 / 10 / 3). 쉬운 문제가 없어서 긴장하기 쉬운데, 그럼에도 꿋꿋히 문제를 풀어 준 국가대표 학생들에게 박수를 보낸다. Day 1에는 세 명의 만점자가 있으며 모두 중국 학생들이다. 예년과 같이 중국 학생들의 성적이 아주 우수하며, 그 뒤를 일본의 Yuki Tanaka (277.5), 폴란드의 Antoni Buraczewski 학생 (265.5) 가 따랐다.

구현한 코드는 https://github.com/koosaga/olympiad/tree/master/IOI 에 모두 올라와 있다.

Day 1 Problems PDF

notice-ISC.pdf

0.11MB

notice-KOR.pdf

0.19MB

closing-KOR.pdf

0.30MB

longesttrip-ISC.pdf

0.18MB

soccer-ISC.pdf

0.64MB

closing-ISC.pdf

0.17MB

soccer-KOR.pdf

0.75MB

longesttrip-KOR.pdf

0.31MB

Problem 1. 봉쇄 시간

서브태스크 1 (8점)

문제 조건에 따라 어떠한 도시가 $X, Y$ 에서 모두 도달 가능하게 배정하는 것은 불가능하다. 고로 각 도시가 둘 중 가까운 도시에 배정되게 하는 것이 최선이고, 이를 위해 배정해야 하는 봉쇄 시간은 DFS를 사용하여 계산할 수 있다. 필요한 봉쇄 시간이 작은 것부터 차례대로 배정하고, 배정할 수 있었던 도시의 개수를 출력하면 된다. 봉쇄 시간을 정렬해야 하니 시간 복잡도는 $O(n \log n)$ 이다.

서브태스크 2 (17점)

$X$ 에서 도달 가능한 정점의 집합과, $Y$ 에서 도달 가능한 정점의 집합은 선 위에서 연속 구간을 이룬다. 고로 시도해 볼 수 있는 집합의 후보가 $O(n^4)$ 개이다. 이 집합을 가능하게 하기 위해서 필요한 봉쇄 시간의 합을 계산한 후, 이것이 $K$ 이하인지 확인하면 된다. 시간 복잡도는 $O(n^5)$ 이다.

서브태스크 3 (29점)

$X$ 와 $Y$ 에서 도달 가능한 정점 집합의 교집합을 고정하자.

교집합이 비었다면, $X$ 에서 각 정점으로 가는 거리 집합과 $Y$ 에서 각 정점으로 가는 거리 집합을 모두 모은 후, 합이 $K$ 이하로 유지되는 한 최대한 많은 수를 고르면 된다. 한 정점을 두 번 고를 수도 있는데, 이 경우 해당 정점에 대해 필요보다 많은 비용을 소모한 것일 뿐이고 해가 불가능하지는 않아 상관이 없다.

교집합이 비지 않았다면, 이 교집합은 선 위에서 연속 구간을 이룬다. 일단 교집합 내부에서는 $X, Y$ 모두를 도달할 수 있는 봉쇄 시간이 배정되어야 하고, $X$ 와 $Y$ 에서 교집합을 도달하는 경로에도 충분한 봉쇄 시간이 필요하며, 여전히 비용이 남는다면 이 비용으로 남는 정점들에 대해 가까운 정점으로 가게끔 하면 된다.

교집합의 후보가 $O(n^2)$ 개이고, 교집합 내부 / 교집합을 도달하는 경로 상 비용을 계산하는 데 부분합을 사용하여 $O(1)$ 의 시간, 남는 정점들을 배정하는 데 $O(n)$ 의 시간이 소모된다. 시간 복잡도는 $O(n^3)$ 이다.

서브태스크 4 (43점)

서브태스크 4를 해결하는 방법은 다양한데 그 중 정해와 다소 비슷한 것을 설명한다.

교집합이 빈 경우는 당연히 따로 처리한다. 선 상에서 $[X, Y]$ 를 잇는 구간을 고려했을 때, 이 구간에서 $X, Y$ 에서 모두 도달 가능한 정점 집합을 고정하자. 즉, 구간 $[X, Y]$ 에 포함되는 또 다른 구간 $[l, r]$ 을 고르는 것이다. 이 때

• $[X, l)$ 에 있는 정점들은 $X$ 에서 도달 가능
• $[l, r]$ 에 있는 정점들은 $X, Y$ 에서 도달 가능
• $(r, Y]$ 에 있는 정점들은 $Y$ 에서 도달 가능

하기 때문에 $[X, Y]$ 안에 있는 정점들에 배정하는 봉쇄 시간은 결정되며, 이것이 편의성 기여하는 값 역시 고정된다.

$[X, Y]$ 구간 밖에 있는 정점들은, $X, Y$ 에서 모두 도달 가능하거나 그 중 가까운 것에서만 도달 가능하다. 예를 들어, $[0, X-1]$ 구간에 있는 어떤 suffix들은 $X$ 에서 도달 가능한 정점들이고, 또 어떤 suffix는 $X, Y$ 에서 모두 도달 가능할 것이다. suffix는 물론 비어 있을 수 있다.

이 때 구성한 도달 가능성 집합이 $[X, Y]$ 구간에서 정해준 도달 가능성과 모순일 수도 있다. 다시 말해, 여기서는 $X - 1$ 번 정점이 $X, Y$ 에서 모두 도달 가능한 정점이라고 고정했는데, 정작 $X$ 번 정점은 $Y$ 에서 도달 불가능한 경우가 있을 수 있다. 하지만 이 경우에는 $X-1$ 번 정점의 도달 가능성을 만들어 주기 위해서 쓴 비용을 그냥 $X$ 번 정점에 쓰면, 같은 이득을 더 작은 비용으로 볼 수 있다. 이는 중요한 것을 시사하는데, $[X, Y]$ 에서 구간 $[l, r]$ 을 어떻게 골랐든 그 밖의 선택과 독립이며, 고로 구간 안과 밖의 문제를 따로 해결할 수 있다는 것이다. 이제 다음과 같은 값을 계산하자:

• $Left[i]$: $[0, X - 1]$ 에서 도달 가능성을 적절히 설정하여 $i$ 만큼의 편의성을 얻을 수 있는 최소 비용
• $Mid[i]$: $[X, Y]$ 에서 도달 가능성을 적절히 설정하여 $i$ 만큼의 편의성을 얻을 수 있는 최소 비용
• $Right[i]$: $[Y+1, N-1]$ 에서 도달 가능성을 적절히 설정하여 $i$ 만큼의 편의성을 얻을 수 있는 최소 비용

위 세 값은 모두 부분합을 사용하여 $O(n^2)$ 시간에 구할 수 있다. DP (max convolution) 으로 이를 $O(n^2)$ 에 합쳐주면 전체 문제 역시 해결된다.

서브태스크 5 (52점)

아주 단순한 완전 탐색은 되지 않는다. 모든 교집합을 고정한 후 나머지를 Greedy로 해결하거나, $X$ 에서 도달 가능한 집합을 고정한 후 Tree DP로 $Y$ 에서 도달 가능한 집합을 구하는 식으로 해결 가능하다.

서브태스크 8 (83점)

트리 상에서 $X, Y$ 를 잇는 경로와 $X, Y$ 에 모두 도달 가능한 정점의 교집합을 모두 고정하자. 서브태스크 4의 원리로 경로 안에서의 비용은 모두 결정된다.

경로 밖에서는, $X, Y$에 모두 도달하거나 아니면 둘 중 하나에만 도달하게 설정할 수 있다. 위에서 사용한 것과 동일한 논리로, 어떠한 노드가 둘 모두에 도달할 수 있는데 그 부모가 둘 중 하나에만 도달할 수 있다면, 부모에 공을 넘김으로서 더 적은 비용으로 같은 효과를 낼 수 있다. 또한, 경로 밖에 어떠한 노드가 $X$ 에 도달하는 것이 $Y$ 에 도달하는 것보다 쉽다면, 그 부모 역시 그러하다.

이러한 식으로 경로 밖에 있는 노드들에 대해서는, 부모 자식 관계 와도 아예 독립적으로, 문제가 해결된다. 각각의 노드에 대해서, 둘 중 하나에만 도달하는 비용 $a_i$ 와 둘 다에 도달하는 비용 $b_i$ 를 계산하자. 첫 번째 비용은 편의성에 1을 기여하고, 두 번째 비용은 편의성에 2를 기여한다. 이제 Knapsack DP 로, $i$ 의 편의성을 얻기 위한 최소 비용을 $O(n^2)$ 에 구할 수 있다.

경로 안과 밖의 편의성을 모두 계산하면, 이제 two pointers 를 사용하여 비용 $K$ 로 얻는 최대 편의성을 구할 수 있다. 시간 복잡도는 $O(n^2)$ 이다.

만점 풀이

경로 안에 있는 노드들에서 $a$ 만큼의 편의성을 얻는 최소 비용을 $F[a]$, 경로 밖에 있는 노드들에서 $b$ 만큼의 편의성을 얻는 최소 비용을 $G[b]$ 라고 하자. $F, G$ 배열을 모두 구할 수 있으면 위에서 언급한 대로 two pointers 를 사용하여 비용 $K$ 로 얻는 최대 편의성을 구할 수 있다. 서브태스크 8에서는 위 두 배열을 $O(n^2)$ 에 구하여 합쳤으나, 만점 풀이에서는 이를 $O(n \log n)$ 으로 구하여 합치는 것을 목표로 해 보자.

경로 안의 문제 해결

경로 안의 문제를 해결하는 과정을 구체적으로 보면 다음과 같다. 어떠한 경로 $p = [p_0 = X, p_1, p_2, \ldots, p_m = Y]$ 에 대해, 우리가 $0 \le l \le r \le m$ 을 잡으면 아래와 같은 비용으로 $m+1+(r-l+1)$ 의 편의성을 얻을 수 있다:

• $\sum_{i < l} a_i + \sum_{i \in [l, r]} \max(a_i, b_i) + \sum_{i > r} b_i$

이 때 $a_i = dist(X, p_i), b_i = dist(Y, p_i)$ 이다. 이는 다시 말해, 겹치지 않는 prefix와 suffix를 잡아, prefix에서 $\max(a_i, b_i) - a_i$ 를 빼고, suffix에서 $\max(a_i, b_i) - b_i$ 를 빼어 합을 최소화해야 함과 동일하다.

$a_i$ 는 증가 수열이고, $b_i$ 는 감소 수열임을 관찰하자. 고로, $\max(a_i, b_i) - a_i$ 는 감소하고, $\max(a_i, b_i) - b_i$ 는 $i$ 가 줄어드는 순으로 봤을 때 감소 (정방향에서 증가) 한다. 다음과 같은 문제를 생각해 보자:

• 두 개의 감소하는 수열이 있다. 수열의 모든 원소는 음이 아니다. 이 수열의 앞에서 최대 $k$ 번 숫자를 뽑아서, 뽑은 숫자의 합을 최대화하는 방법은 무엇인가?

이 문제를 해결하기 위해서, 단순히 매번 뽑을 수 있는 가장 큰 원소를 뽑는 것으로 충분함을 쉽게 볼 수 있다. 우리가 풀고자 하는 문제도 이것과 동일하니, 뺄 수 있는 원소 중 큰 원소를 반복적으로 제거해 주면 된다. 조금 복잡하게 보면 이는 convex function의 minkowski sum 을 구하는 것과도 동일한데, 아래에서 이러한 전략을 다시 쓸 것이니, 처음 듣는 단어라면 배워두면 좋다. 이제 경로 안의 문제를 $O(n)$ 에 해결할 수 있다.

경로 밖의 문제 해결

경로 밖의 문제는 다음과 같이 표현할 수 있다.

• 길이 $n$ 의 수열 $a, b$ 가 주어진다. 각 $1 \le i \le n$ 에 대해서, 당신은 $a_i$ 의 비용을 지불하고 $1$ 의 편의성을 얻거나, $b_i$ 의 비용을 지불하고 $2$ 의 편의성을 얻거나, 아무것도 하지 않을 수 있다. 모든 $0 \le k \le 2n$ 에 대해 $k$ 의 편의성을 얻는 최소 비용은 얼마인가? $a_i \le b_i$ 임이 보장된다.

이는 $O(n^2)$ 에 DP로 쉽게 해결할 수 있으며, $O(n \log n)$ 풀이도 존재한다. 만점 풀이에서 위 문제의 $O(n \log n)$ 풀이는 필요하지 않아서, 해당 풀이의 일부분만 설명한다.

각 원소들을 다음과 같은 두 종류로 분류하자:

• $2a_i \le b_i$
• $2 a_i \ge b_i$

만약에 모든 원소들이 다 첫 번째 종류에 속한다면, 이 문제는 위의 "감소하는 수열" 과 동일한 방식으로 해결할 수 있다. 매 번 뽑을 수 있는 것 중 가장 큰 원소를 뽑으면 되기 때문이다. Priority Queue 등으로 구현할 수도 있겠지만, 더 간단한 것은 단순히 $[a_i, b_i - a_i]$ 를 모아놓고 정렬한 후 이 중 가장 작은 $k$ 개의 합을 취하는 것이다. $b_i - a_i$ 를 먹지만 $a_i$ 를 먹지 않는 경우가 생기지 않기 때문이다.

모든 원소들이 다 두 번째 종류에 속한다면, 두 개 이상의 원소에 대해서 $a_i$ 를 취할 필요가 없다. 만약 $a_i$ 를 취한 원소가 두 개 있고 일반성을 잃지 않고 $a_i \le a_j$ 라고 하자. $a_j$ 를 먹지 않고, 대신 $a_i$ 를 $b_i$ 로 바꾸게 되면, $b_i \le 2 a_i \le a_i + a_j$ 라서 비용이 더 감소한다. 고로 짝수 $k$ 에 대해서는 $b_i$ 가 가장 작은 $k/2$ 개를 취하면 된다. 홀수 $k$ 에 대해서는, $b_i$ 가 가장 작은 $k/2$ 를 고르고, $a_i$ 를 그 $b_i$ 중에서 고르는 경우 / 그렇지 않은 경우로 나눠서 계산하면 Prefix min의 형태를 띄어 계산해 줄 수 있다.

결과 합치기

총 세 개의 수열을 $O(n \log n)$ 정도의 시간에 구하였다:

• 경로 안에서 $k$ 의 편의성을 얻는 최소 비용
• 경로 밖에서 $2 a_i \le b_i$ 인 원소들만 두었을 때 $k$ 의 편의성을 얻는 최소 비용
• 경로 밖에서 $2a_i > b_i$ 인 원소들만 두었을 때 $k$ 의 편의성을 얻는 최소 비용

이제 이 세 수열에서 $k_1, k_2, k_3$ 을 골라서, 각 수열에서 $k_i$ 의 편의성을 얻는 최소 비용의 합이 $K$ 이하고, $k_i$ 의 합을 최대화해야 한다. 두 수열일 때는 Two pointers 로 가능하였지만, 세 수열일 때는 어렵다.

하지만, 여기서 위에 있는 두 개의 수열에 대해서 최소 비용이 $k$ 에 대해서 convex 함을 관찰하자 - 즉, 맨 위에 있는 두 수열은 $a_{i+1} - a_{i} \leq a_{i+2} - a_{i+1}$ 을 만족하며, 두 수열이 구성된 방식을 생각해 보면 이는 자명하다. 고로, 두 수열을 합해서 얻는 편의성, 다시 말해 $C[i + j] = min(A[i] + B[j])$ 를 계산하는 것은:

• $C[0] = A[0] + B[0]$ 을 놓고
• 수열의 변홧값을 정렬한 후, 변홧값이 증가하는 순서대로 $C[i]$ 를 계산

하는 식으로 구할 수 있다. 이렇게 되면 두 수열이 하나로 합쳐지니, 필요한 수열도 하나이고, 전체 문제가 $O(n \log n)$ 에 해결된다.

여담으로, 내가 Github에 구현한 코드는 이런 식으로 작성되어 있지 않고 그냥 세 수열의 합을 계산하기 때문에, 여기서 설명한 것과는 다소 차이가 있다.

Problem 2. 가장 긴 여행

서브태스크 1 (5점)

그래프는 완전 그래프이기 때문에, $[0, 1, \ldots, N - 1]$ 혹은 이것의 아무 순열을 반환하면 된다.

서브태스크 2 (15점)

모든 $N(N-1)/2$ 개의 쌍에 대해서 두 쌍을 잇는 간선이 존재하는지를 단순하게 물어보면 그래프의 정보를 알 수 있다. $N = 256$ 일 때 이 값은 $32640$ 이다. 고로 서브태스크 2, 3 에서는 그래프의 정보를 알 수 있다고 가정해도 무방하다. 서브태스크 2에서 그래프에 존재하지 않는 간선은 같은 정점을 공유할 수 없다. 달리 말해, 그러한 간선들은 매칭을 이룬다.

초기에, $0$ 번 정점을 포함하는 길이 $1$ 의 경로 ($[0]$) 에서 시작해서, 다음과 같은 방법으로 경로를 확장시키자. 이 글에서는 이러한 경로를 Maximal path 라 부른다.

• 현재 경로의 마지막 점과 인접하며, 경로에 속하지 않은 정점을 고른다.
• 이를 경로의 마지막 점으로 추가한다.

서브태스크 2의 그래프에서는 Maximal path의 길이가 $N-1$ 미만일 수 없다. 이보다 작으면 무조건 속하지 않으며 인접한 정점이 존재하기 때문이다.

고로 Maximal path의 길이는 $N-1$ 이거나 $N$ 이다. $N$ 이면 문제는 이미 풀렸다. $N-1$ 일 경우, 경로에 속하지 않는 정점은 경로의 끝점과 인접하지 않으니, 시작점과 인접하고, 시작점 앞에 붙여주면 된다.

서브태스크 3 (40점)

서브태스크 2와 동일하게 Maximal path를 찾아주자. 만약 Maximal path $P = [v, \ldots, w]$ 에 더 이상 정점을 추가할 수 없다면, 현재 경로에 속하지 않은 정점들 ($V \setminus P$) 은 $w$ 와 인접하지 않다. $D = 1$ 이라는 성질을 생각해 보면, 경로에 속하지 않은 정점들의 쌍을 모두 고려했을 때, 이들 간에 간선이 항상 존재하고, 달리 말해 $V \setminus P$ 는 클리크를 이룬다는 것을 알 수 있다. 고로 그래프의 모든 정점은 찾은 Maximal path에 속하거나 아니면 클리크에 속한다. Path의 길이가 길면 Path를 반환하고, 아니면 클리크의 정점들을 아무 순서로 반환하면 된다.

60점

서브태스크 3과 동일하게 Maximal path $P$ 를 찾아주고, 이에 따른 클리크 $C = V \setminus P$ 역시 찾아주자. 만약 $C, P$ 사이를 잇는 간선이 없다면 둘 중 큰 쪽을 반환해 주면 된다.

그렇지 않다면 둘을 항상 이어줄 수 있다. 만약 $|P| \le 2$ 이면, 둘을 잇는 간선이 경로의 끝점을 이으니 그대로 이어주면 된다. $|P| \geq 3$ 이라고 하자. $C$ 의 임의의 정점과 $P$ 의 두 양 끝점을 보았을 때, 세 가지 경우 중 하나가 성립한다.

• $C$ 의 임의의 정점이 양 끝점 중 하나와 인접한다 - 그대로 이어붙이면 된다.
• 둘 다 아니다 - $P$ 의 양 끝점이 인접하기 때문에 $P$ 를 사이클로 볼 수 있다. $C$ 와 $P$ 사이를 잇는 간선이 있다면, 이 간선을 기준으로 $P$ 를 Cyclic shift하여 붙여주면 된다.

70점

Maximal path를 찾고, $C$ 와 $P$ 사이를 잇는 간선을 찾을 때 이분 탐색을 사용하여 최적화할 수 있다. 특정 정점과 인접한 정점 단 하나 를 찾는 것이기 때문에, 이 하나가 속하는 집합을 이분 탐색과 같이 찾아주는 것이다.

85점

60점 풀이의 요령으로 Maximal path를 찾을 때, 경로의 끝점과 인접하지 않은 정점을 순회하는 과정에서 많은 시간이 소모된다. 다음과 같이 알고리즘을 수정하면 이 부분을 최적화 할 수 있다. Maximal path 하나를 관리하는 것이 아니라, 최대 2개 의 Maximal path를 관리하자. 초기 상태는 0번 정점을 포함하는 길이 $1$ 의 경로가 하나 있는 상태이다. 만약 현재 경로가 1개라면:

• 경로의 끝점과 새 정점 $v$ 가 인접하면 이 경로에 추가한다.
• 그렇지 않다면 두 번째 경로를 길이 1의 경로 $[v]$ 로 initialize한다.

현재 경로가 2개라면:

• 둘 중 한 경로에 인접하다면 그 경로에 추가한다.
• 그렇지 않다면 두 경로의 끝점이 인접하다. 두 경로를 하나로 붙인 후, 두 번째 경로를 길이 1의 경로 $[v]$ 로 initialize한다.

여기까지 $2n$ 개의 쿼리를 사용하였다.

이제 전체 그래프를 두 개의 경로 $P_1, P_2$ 로 묶었다. 일반성을 잃지 않고 $|P_1| \geq |P_2|$ 라고 하자. 60점 풀이에서는 클리크라는 성질을 사용해서 두 경로를 묶었지만, 사실 그러한 성질이 없어도 두 경로를 묶을 수 있다.

• $P_1, P_2$ 를 잇는 간선이 없다 - 큰 쪽을 반환한다.
• $P_1$ 의 양 끝 정점이 $P_2$ 의 양 끝점 중 하나와 인접한다 - 그대로 이어붙이면 된다.
• $P_2$ 의 양 끝 정점이 $P_1$ 의 양 끝점 중 하나와 인접한다 - 그대로 이어붙이면 된다.
• 두 경우가 모두 아니라 하자. 만약 $|P_i| \geq 3$ 일 경우 경로를 사이클로 바꿀 수 있다. $2\log n$ 번의 쿼리를 사용하여 이분 탐색을 하면, 두 경로 사이를 잇는 간선 하나를 찾을 수 있다. 사이클이거나 길이 2인 경로들이기 때문에, 이 간선 앞 뒤로 경로가 붙어있게 조정할 수 있다.

총 $2n + 3 + 2 \log n$ 개의 쿼리를 사용하며, 85점을 받을 수 있다.

만점 풀이

제한을 통해서 만점 풀이가 대략 $3/2n + 2 \log n$ 개 정도의 쿼리를 사용한다고 짐작한다면, 시도해 볼만한 전략은 위 풀이에서 2개의 정점을 3번의 쿼리로 한 번에 넣는 것이 되겠다. Maximal path 최대 두 개를 관리하며, 여기에 Maximal path가 두 개일 경우 둘의 끝점이 인접하지 않다 라는 불변량을 추가로 설정하자. $(0, 1)$ 의 인접 여부에 따라서 초기 상태를 결정할 수 있다.

새로 넣는 정점의 번호를 $v, w$ 라고 하자. 만약 현재 경로가 1개라면, $v, w$ 와 경로의 끝점 $p$ 간 세 쌍에 대해서 쿼리를 하자. 쿼리 결과를 토대로 다음 상태는 아래와 같이 정해 준다.

• 만약 $(v, w)$ 가 인접한데 $(v, p)$ 나 $(w, p)$ 중 하나라도 인접한다면 경로의 뒤에 $v, w$ 나 $w, v$ 를 추가한다.
• 만약 $(v, w)$ 가 인접한데 $(v, p)$ 나 $(w, p)$ 가 모두 인접하지 않다면 $[v, w]$ 라는 경로를 추가한다.
• 만약 $(v, w)$ 가 인접하지 않다면 $(v, p)$ 나 $(w, p)$ 중 하나는 인접하다. 인접한 쪽을 $p$ 뒤에 붙이고, 선택되지 않은 쪽을 새 경로로 만든다.

현재 경로가 2개라면, $v, w, p_1, p_2$ 중 알아야 할 쌍의 개수가 총 5개이다. 그런데, $p_1, p_2$ 가 인접하지 않음이 보장되기 때문에, $p_1$ 이 $v$ 와 인접하지 않다면 자동으로 $p_2$ 와 인접해 지는 등의 성질이 보장된다. 이 점을 잘 사용하면 2개의 쿼리가 줄어들어 3개의 쿼리로 충분해진다. 먼저 $(v, w)$ 간의 인접성을 하나의 쿼리로 확인하자. 만약 $(v, w)$ 가 인접하다면:

• $(v, p_1)$ 간에 인접한지 확인하자. 일반성을 잃지 않고 $p_1$ 에 인접한 쪽을 $v$ 라고 하자.
• $(w, p_2)$ 간에 인접하다면, $p_1 - v - w - p_2$ 와 같이 경로를 붙여준다.
• 그렇지 않다면 $p_1$ 에 $v, w$ 를 붙이자.

만약 $(v, w)$ 가 인접하지 않다면:

• $(v, p_1)$ 간에 인접한지 확인하자. 일반성을 잃지 않고 $p_1$ 과 $v$ 가 인접하다고 하자.
• $(w, p_2)$ 간에 인접하다면, $p_1$ 에 $v$, $p_2$ 에 $w$ 를 붙여준다.
• 그렇지 않다면, 우리는 $(w, p_2)$ 및 $(p_1, p_2)$ 가 인접하지 않음을 알고 있으며, 고로 $(w, p_1)$ 이 인접함을 유추할 수 있다. 상술했듯이 $(v, p_2)$ 역시 인접하니, $p_1$ 에 $w$, $p_2$ 에 $v$ 를 붙여준다.

이후 이들을 이어주는 것은 85점과 동일한 이분 탐색으로 가능하다.

쿼리 개수가 최악의 경우에도 최대 400번 나오게 신중하게 구현해야 함에 유의하자. 본인은 402번의 쿼리를 사용하여 여러 번 틀렸고, 결국 2번의 쿼리를 줄여서 통과하였다. 95점 정도의 서브태스크가 있었으면 좋았을 것 같다.

Problem 3. 축구 경기장

서브태스크 2 (18점)

모든 부분집합을 시도해 보고 그것이 정상적인 경기장인지 파악하면 된다. 정상적인 경기장인지는 $O(n^5)$ 시간에 판별할 수 있다. 두 셀이 같은 행/열이면 직선으로 이어주고, 다른 행/열이면 두 가지 방법으로 이어준 후 정의를 만족하는지 보면 된다. 사실 Naive하게 정상적인 경기장의 형태를 파악하는 풀이이니, 서브태스크 3/4 에 대해서도 25% 의 점수를 받을 수 있는 풀이이다.

정상적인 경기장의 형태 파악하기 (35.5점)

정상적인 경기장의 최대 크기를 구하는 문제이니, 정상적인 경기장의 형태를 쉽게 표현하는 것이 문제의 시작점이 된다. 이 문제에서는, 정상적인 경기장의 형태를 판별하기만 해도 25점을 주니, 여기서 시작해 보자.

각 행 $r$ 에 대해서, $S_r$ 을 해당 행에서 경기장에 포함된 열들의 집합이라고 하자. 다음 조건이 성립해야 한다:

• $S_i$ 는 비어 있거나 구간 을 이룬다: 어떠한 $0 \le l \le r \le n-1$ 이 존재하여 $S_i = {l, l+1, \ldots, r}$ 이다.
• 어떠한 $i$ 가 있어, $S_0 \subseteq S_1 \subseteq \ldots \subseteq S_i \supseteq S_{i+1} \supseteq \ldots \supseteq S_{n-1}$
• 두 $S_i, S_j$ 는 서로 포함 관계여야 한다 - 즉, $S_i \subseteq S_j$ 혹은 $S_j \subseteq S_i$

다음 조건 중 하나라도 성립하지 않는다면 정상적인 경기장이 아니다:

• $S_i$ 가 구간을 이루지 않는다면, 연결되지 않은 부분을 직선 킥으로 오갈 수 없다.
• 위와 같은 $i$ 가 없다면 $S_{i-1} \supsetneq S_{i} \subsetneq S_{i+1}$ 을 만족하는 $i$ 가 존재하고, $i-1, i+1$ 에서 직선 킥으로 오갈 수 없는 셀 쌍이 존재한다.
• $S_i - S_j, S_j - S_i$ 가 모두 공집합이 아닐 경우 둘 사이를 직선 킥으로 오갈 수 없다.

한편으로, 다음 조건이 모두 성립하면 정상적인 경기장이다:

• 같은 행 간의 모든 셀은 직선 킥으로 오갈 수 있다.
• 다른 행 간의 임의의 셀 $(r_1, c_1), (r_2, c_2)$ 을 잡았을 때, 정의에 의해 $c_1 \in S_{r_1}$ 이거나 $c_2 \in S_{r_2}$ 이다. 일반성을 잃지 않고 $c_2 \in S_{r_2}$ 라면 $(r_1, c_2)$ 를 통해서 가면 되며, 두 번째 조건에 의해서 이것이 항상 가능하다.

고로 위 세 조건을 판별해야 하며, 이는 $O(n^2)$ 에 가능하다. 정상적인 경기장의 형태를 파악했으니 서브태스크 1 역시 쉽게 해결된다.

서브태스크 5 (77.5점)

$S$ 전체의 집합을 봤을 때 한 구간이 다른 구간에 계속 포함되기 때문에, 전체 집합에서 최대가 되는 구간이 왼쪽/오른쪽으로 줄어들고, 그 과정을 DP로 구한다고 생각할 수 있다. $i$ 번 행을 고정하고, 이 행의 $S_i$ 가 최대이며 그 때의 구간이 $[l, r]$ 이라고 하자. 이 구간의 크기를 왼쪽 / 오른쪽에서 줄이는데, 줄이는 과정에서 이 구간을 포함할 수 있는 위 / 아래 행이 늘어난다면 이들을 최대한 포함시키는 식으로 전이해 주자.

구체적으로, $i$ 를 고정한 후, $DP[l, r]$ 을:

• $[l, r] \subseteq S_u, S_{u+1}, \ldots, S_i, \ldots, S_{d-1}, S_d$ 를 만족시키는 최대 $u, d$ 에 대해서, 거기까지의 구간이 정해졌다면
• 이제 $[0, u-1]$, $[d+1, n-1]$ 에서 추가로 얻을 수 있는 최대 구간 길이 합

같은 식으로 정의하자. 모든 $[l, r]$ 에 대해서 얻을 수 있는 최대 $u, d$ 를 $O(n^2)$ 에 전처리하였다면, 위 DP를 $DP[l+1, r]$ 이나 $DP[l, r-1]$ 에서 가져오는 식으로 $O(n^2)$ 에 계산해 줄 수 있다. 이를 모든 행에 대해서 반복하니, 전체 시간 복잡도가 $O(n^3)$ 이다.

만점 풀이

서브태스크 5의 풀이를 고찰해 보면, 결국 풀이에서 사용하는 상태가 직사각형 에 대응됨을 알 수 있다. 구체적으로, 다음과 같은 직사각형의 수열을 구하는 것이라고 생각할 수 있다:

• 각 직사각형 안에는 나무가 없음
• $S_i$ 를 포함하는 가장 넓은 직사각형 에서 시작해서, 그 전 직사각형보다 좁지만 ($[l, r]$ 구간이 줄어들지만) 높은 (대응되는 $[u, d]$구간이 넓어지는) 직사각형이 나열됨
• 수열을 이루는 직사각형 넓이의 합집합이 최대

$[l, r]$ 을 고정하면 최대 $[u, d]$ 역시 고정되는 것에서 볼 수 있듯이, 우리가 구하는 수열을 이루는 직사각형도 maximal 한 것만 고려하면 된다: 다시 말해, 나무나 경계를 넘지 않고 상하좌우로 확장할 수 없는 직사각형들만 고려하면 된다. 이 부분이 시간 복잡도를 줄이는 데 굉장히 중요한데, 이러한 직사각형은 $O(n^2)$ 개 밖에 없기 때문이다: 상좌우로 확장할 수 없는 것만 생각하더라도, 위쪽 끝을 고정하면 좌우가 고정되기 때문이다 (히스토그램에서 최대 넓이 직사각형을 구하는 것을 생각하면 좋다). 고로 아래쪽 끝 하나에 대해서 최대 $n$ 개의 직사각형이 나오고, 이는 전체 maximal 직사각형이 $O(n^2)$ 개 이하라는 증명이 된다.

이로서 상태의 크기가 $O(n^2)$ DP를 얻었으나, 여기서 단순히 위 정의대로 진행할 경우 시간 복잡도가 $O(n^4)$ 가 되어 별로 효율적이지 않다. 현재 직사각형이 $[r_1, r_2] \times [c_1, c_2]$ 일 때 다음 상태로 들어갈 직사각형은 위쪽 / 아래쪽 중 한 방향으로 넓어질 것이다. 일반성을 잃지 않고 이 중 위쪽 방향만 논의하자. $r_2+1$ 번째 행의 $c_1, c_1 + 1, \ldots, c_2$ 번째 수들을 구하고, 나무가 없는 최대 연속 구간을 구하자. 최대 연속 구간이 아닌 경우 해당 방향의 상태 전이를 굳이 시도해 볼 필요가 없으며, 최대 연속 구간인 경우 다음 상태 역시 maximal 직사각형을 이룬다. 이렇게 하면 각 직사각형 당 최대 $O(n)$ 개의 전이가 되는데, 사실 모든 직사각형에 대해서 이러한 전이 수의 합을 더하면 $O(n^2)$ 가 된다.

전이 수의 합이 $O(n^2)$ 인 것은 상태의 합이 $O(n^2)$ 인 것과 유사한 이유인데, 상좌우로 확장할 수 없는 직사각형에서, 위쪽 끝을 기준으로 직사각형을 라벨링했을 때, 이 위쪽 끝을 얻는 직사각형을 호출하는, 부모 상태 가 최대 하나라는 것이 그 이유이다. 어려운 용어를 써서 짧게 설명하면, 그냥 각 상태 전이가 Cartesian tree의 간선에 대응되기 때문이다.

이제 각 maximal 직사각형을 상태로 하여, std::map 등을 사용하여 메모이제이션하고, 다음으로 가능한 상태 전이를 적절한 전처리와 이분 탐색을 사용하여 구하면, 각 상태와 상태 전이에 $O(\log n)$ 시간이 걸려 $O(n^2 \log n)$ 에 전체 문제를 해결할 수 있다.