티스토리 뷰

공부/Problem solving

IOI 2023 Day 1

구사과 2023. 8. 31. 06:01

(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)$ 에 전체 문제를 해결할 수 있다.

'공부 > Problem solving' 카테고리의 다른 글

2023.08.29 problem solving  (0) 2023.08.29
2023.08.13 problem solving  (0) 2023.08.13
구간 최장 증가 부분 수열 쿼리 (Part 2)  (0) 2023.02.11
구간 최장 증가 부분 수열 쿼리 (Part 1)  (0) 2023.01.27
Suffix Automaton  (0) 2023.01.08
댓글
공지사항
최근에 올라온 글
Total
Today
Yesterday