koosaga's profile image

koosaga

August 18, 2019 00:00

IOI 2019 Day 1

IOI 2019 Day 1 대회가 종료되었다.

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

• 김세빈, 100 / 40 / 100, 240점, 8등 - 25등
• 윤교준, 100 / 40 / 72, 212점, 26등 - 59등
• 임유진, 100 / 40 / 72, 212점, 26등 - 59등
• 이온조, 100 / 64 / 38, 202점, 60등

올해도 미국의 Benjamin Qi가 만점인 300점을 3시간 30분만에 얻었다. 문제가 쉽지 않았음에도 불구하고 빠른 시간 안에 300점을 얻은 것이 놀라울 따름이다. 단순히 Day1에서 큰 점수차를 보여줬을 뿐만 아니라 실질적으로 다른 학생들과 실력 격차가 크다는 것을 증명했다고 생각한다. 2019년 2연속 우승이 기대된다.

한국은 상당히 좋은 성적을 얻었던 작년의 Day1 결과와 비교하면 훨씬 더 좋은 성적이 나왔음을 알 수 있다. 항상 Day1 문제에 약하다는 징크스(인지 과학인지..) 가 반영된 결과라고도 생각하지만, 대다수의 학생들이 받아야 할 점수 그 이상을 받아주었다는 사실은 부정할 수 없다. Day 2에도 동요하지 않고 좋은 결과를 유지할 수 있었으면 좋겠다.

Day 1 Notice

Problem 1. Arranging Shoes

Problem

크기 $2N$ 의 정수 배열 $X[0], X[1], \cdots, X[2N-1]$ 이 주어진다. 이 정수들은 0보다 작을 수 있으나 0인 경우는 없다. 정수 배열이 유효하다 는 것은 다음과 같다.

• 모든 $0 \le i < N$ 에 대해, $X[2i] < 0, X[2i+1] > 0, X[2i] + X[2i+1] = 0 $

당신은 주어진 배열에 인접한 쌍을 교환(swap) 하는 연산을 최소 횟수로 해서 이 배열을 유효하게 만들고 싶다. 필요한 연산의 최소 횟수는 얼마인가? (유효하게 만드는 것이 가능한 것은 보장된다.)

Solution

만점 풀이가 잘 안 보일 수 있으나, 생각보다 간단하게 고득점을 받을 수 있어서 만점을 받는 것도 쉽다고 예상할 수 있다. 절반 가량의 참가자들이 풀었지만 실제로 그렇게 쉬운 문제는 아니라고 생각한다. 이러한 류의 그리디 문제가 well-known이기도 하고, 또한 정해의 접근법을 시도해 볼 여지가 충분히 있는 문제라서 많이 풀렸다고 생각한다.

Subtask 1 (10점)

return (s[0] > 0 ? 1 : 0)

Subtask 3 (30점)

모든 신발의 크기가 같은 경우, 결국 숫자를 적당히 재배열해서 $-x, x, -x, x, \cdots$ 와 같은 수열을 만드는 것이 목표가 된다. 0번 위치부터 순서대로 이 수열을 만들어나가자. 각 위치에 수를 배정할 때, 해당 위치에 이미 원하는 숫자 ($x$ 내지는 $-x$) 가 존재한다면 문제가 해결된다. 그렇지 않다면, 오른쪽으로 가면서 가장 가까운 필요한 숫자를 찾아서 나의 위치로 당겨주면 된다.

위와 같은 것을 그대로 구현하면 $O(N^2)$ 인데, 이는 몇 가지 방법으로 최적화 할 수 있다. 가장 직관적인 방법은 std::set 을 사용하는 것이다. 현재 수열이 $x, x, x, x, -x, \cdots$ 라고 하고, 현재 위치에 $-x$ 가 필요하다고 하자. $x, x, x, x, -x, \cdots$ 를 오른쪽에서 왼쪽으로 순서대로 바꿔준다면, 그 결과는 $-x, x, x, x, x, \cdots$ 과 같이 될 것이다. 즉, 원래 $-x$ 가 있던 위치와 현재 위치 말고는 값이 변하지 않는다. 고로 set에 $x$ 와 $-x$ 의 위치들을 각각 저장한 후, 현재 찾은 가장 가까운 $-x$ 의 위치를 찾고, 두 인접하지 않은 위치 사이에 swap을 해준 후, 실제로는 위치를 하나 하나 옮겨줬다고 생각해서 두 위치의 차를 답에 더해주는 방식을 사용할 수 있다. 이렇게 하면 $O(N\log N)$ 알고리즘이 유도된다.

비직관적이지만 간단한 방법은 다음과 같다. $P_0, P_1, \cdots, P_{n-1}$ 을 각 $-x$ 의 위치를 저장하는 정렬된 배열이라고 하자. 정답은 $\sum_{i = 0}^{n-1} abs(P_i - 2i)$ 이다. 위 방법을 사용하면 이 값이 절대 늘어나는 일이 없고 무조건 1씩 줄기 때문이다.

이 입력이 사실 Subtask 1을 포함하기 때문에, 이를 구현하면 30점을 얻는다.

Subtask 4 (45점)

Subtask 4는 Subtask 3과 똑같은 방식으로 풀린다. 왜냐하면 여기서도 크기를 무시해도 되기 때문이다 (…) 모든 신발의 크기가 같다고 생각하고 Subtask 3의 전략을 그대로 사용하면, 실제로 $X[0], X[n], X[1], X[n+1], \cdots$ 와 같이 매칭이 된다. 고로 입력 상에서 같은 크기인 신발이 인접하게 된다.

Subtask 4만 풀기 위해서는 이것도 가능하다: return (long long)n*(n-1)/2

Subtask 5 (85점)

위 서브태스크들을 풀다 보면 매칭 가능한 가장 가까운 짝신발을 이어주는 전략이 유효함을 알 수 있다. 고로 다음과 같은 알고리즘을 생각할 수 있다:

• 해당 신발과 짝이 맞는 가장 가까운 신발을 반복적으로 매칭 ($O(n^2)$)
• 매칭 이후 오른쪽 신발이 왼쪽 신발 앞에 있다면 교환 (답 1 증가)

짜면 맞기 때문에 별로 증명할 필요는 없고 여기서도 증명을 생략한다… 아무튼 서브태스크 3에서의 “그대로 $O(n^2)$ 구현” 을 사용하면, 일반적인 케이스에서 문제를 해결할 수 있다. 총 85점을 받을 수 있다.

만점 풀이 (100점)

해당 신발과 짝이 맞는 가장 가까운 신발들을 매칭”만” 해 주자. 즉, 왼쪽에서 오른쪽으로 가면서 해당 신발과 짝이 맞는 가장 가까운 신발을 찾아주고, 실제로 교환은 하지 않는 것이다. 실제로 교환을 하지 않는다고 가정하면 이 과정은 $O(N)$ 에 가능하다. 각 크기의 신발에 대해서 따로 따로 매칭을 해 주는데, 단순히 정렬된 순서대로 음수 크기 신발과 짝수 크기 신발 사이에 매칭을 해 주면 되기 때문이다.

이제 매칭을 왼쪽 끝 순서대로 정렬하고 실제로 두 수를 모아주자. 어떠한 두 수를 모은다는 것은 이 두 수를 배열에서 지운다는 것과 유사하다고 생각할 수 있다. 고로, 우리가 실제로 두 수를 모으기 위해 하게 될 일은:

• 두 수 사이에 있는 지워지지 않은 수의 개수를 세고 (이것이 실제로 필요한 swap 횟수가 된다.)
• 오른쪽 신발이 왼쪽 신발 전에 있으면 바꿔준 후
• 두 수를 지우는

이 세가지 연산이 된다. 2번째 연산은 단순하게 하면 되고, 1번째 / 3번째 연산은 크기 $2N$ 크기의 Fenwick tree를 만들어서 할 수 있다. $Alive[x] = (x$ 가 지워지지 않은 원소면 1, 아니면 0) 이라고 정의했을 때, 초기 $Alive[x] = 1$ 이고, 두 수 사이에 있는 지워지지 않은 수의 개수는 $Alive$ 배열의 구간 합으로 표현 가능하고, 두 수를 지우는 것은 어떠한 원소에 대해 $Alive[x] = 0$ 을 설정해 주는 것이기 때문이다. 총 시간 복잡도는 $O(n \log n)$ 이 된다.

Problem 2. Split the Attractions

Problem

$n$ 개의 정점과 $m$ 개의 간선을 가진 무방향 연결 그래프 $G$ 가 주어졌을 때, 모든 정점 집합을 3개의 집합 $A, B, C$ 로 분할해야 한다. 이 때 이 집합은 다음과 같은 조건을 만족해야 한다:

• $A$의 크기는 $a$, $B$ 의 크기는 $b$, $C$ 의 크기는 $c$ . “분할”(partition) 이기 때문에 모든 정점이 $A, B, C$ 중 정확히 하나에만 속해야 한다. 고로 $a + b + c = n$ 을 만족한다.
• $A, B, C$ 중 2개 이상은 연결되어 있어야 한다: 정점 부분집합 $S$가 연결되어 있다는 것은, $S$ 에 속하지 않은 정점과 양 끝점중 하나 이상이 $S$ 에 속하지 않는 간선을 지웠을 때, 그래프가 연결되어 있다는 것을 뜻한다. (간단히 말해서 Induced subgraph $G[S]$ 가 연결 그래프이다.)

이것이 가능한지 판별하고, 가능하다면 그 집합을 반환하라.

Solution

Subtask 1 (7점)

각 관광지의 차수가 최대 2라는 것은, 관광지들이 단순 사이클($m = n$) 이나 직선($m = n-1$) 을 이룬다는 것이다. 단순 사이클을 이루는 경우, 그래프에서 아무 간선이나 지워주면 선이 되니, 일반성을 잃지 않고 입력이 직선이라고 가정하자. 이 경우, 단순히 직선을 $a, b, c$ 크기로 쪼개주면 항상 문제를 해결할 수 있다. 구현은 degree 1인 점을 잡고 깊이 우선 탐색을 통해서 직선을 찾는 것이 가장 간단하다.

Subtask 2 (18점)

먼저 다음과 같은 Lemma를 제시한다:

• Lemma 1. 일반성을 잃지 않고 $A, B$ 가 연결된 컴포넌트를 이루도록 정한다고 하자. 이 경우, 그래프의 정점 집합을 연결된 두 집합 $A^\prime, B^\prime$ 로 분할해서, $ A^\prime \cup B^\prime = V(G), A^\prime \cap B^\prime= \emptyset, A^\prime \geq a, B^\prime \geq b$ 를 만족하게끔 할 수 있는 것과, 문제의 정답이 존재하는 것이 동치이다.
• 증명.
  • $\rightarrow$. $A^\prime$ 에서 DFS를 한 후, DFS preorder를 구한다. 이 때 맨 앞 $a$개의 정점은 연결 컴포넌트이므로 $A$ 를 이것으로 둔다. $B$ 에 대해서도 동일한 것이 가능하다. $C = V(G) \setminus A \setminus B$ 라 두면 문제가 해결된다.
  • $\leftarrow$. 그래프가 연결이기 때문에, $C$ 에 있는 어떠한 정점을 $A$나 $B$ 한 쪽에 붙이는 것을 반복하여 전부 지워버릴 수 있다. 남은 $A, B$ 는 문제의 조건을 만족한다.
• Lemma 2. 일반성을 잃지 않고 $a \le b \le c$ 라고 하면, $A, B$ 에 대해서만 해 보아도 된다.
• 증명. $A, B$ 에 대해서 하지 못하면서 $A, C$ 나 $B, C$ 에 대해서 할 수 없다.

아무튼, 이제 문제를 3개의 분할이 아니라 하나의 부분 집합 $S$ 를 찾는 것이라고 볼 수 있다. $S$ 는 연결되어야 하고, $V(G) \setminus S$ 역시 연결되어야 하고, $a \le S \le n - b$ 를 만족해야 한다. 이 집합을 주면 위의 Lemma를 증명할 때 썼던 프로시저를 그대로 써서 답을 반환할 수 있으니, 그 프로시저를 $answer(S)$ 라고 구현하고 문제를 해결하자.

이 문제에서는 $S$ 의 사이즈에 대한 제약이 없이 위 조건을 만족하는 아무 부분집합이나 잡으면 된다. 여러 선택지가 있겠지만 서브태스크가 $a = 1$ 의 형태이니 $S = 1$ 을 시도해 보자. 이 경우, $S$ 의 여집합이 연결되도록 해야 하는데, 이는 Lemma 1의 증명과 똑같이 할 수 있다: 스패닝 트리를 잡은 후, 가장 마지막에 방문한 정점 하나를 $S$ 라고 하면, 이 외 나머지 $n-1$ 개의 정점은 연결되어 있으니 문제의 조건을 만족한다.

Subtask 3 (40점)

그래프가 트리의 형태일 경우, 트리를 두 연결된 컴포넌트로 나누는 방법은 간선 하나를 자르는 방법밖에 없다: 0번 정점을 루트라고 하고, $A$ 가 0번 정점을 포함한다고 하였을 때, $B$ 에 포함되면서 0번 정점과 가장 가까운 점을 생각해 보았을 때, 이 정점 아래 서브트리에 있는 정점은 모두 $B$ 에 포함되고, 그러한 정점만 $B$ 에 포함될 수 있다. 고로 트리 상에서 두 연결된 컴포넌트는 간선 하나로 분리할 수 있다.

이제 문제를 해결하는 것은 그다지 어렵지 않다. 간선 하나를 제거했을 때 각 컴포넌트의 크기를 알 수 있다면 문제를 바로 해결할 수 있기 때문이다. 아무 정점을 루트로 잡은 후 트리를 깊이 우선 탐색으로 탐색하면서, 해당 정점의 서브트리 안에 있는 정점의 개수를 관리하자. 이 값을 안다면, $parent(v) - v$ 간선을 지웠을 때 각 컴포넌트의 사이즈는 $v$ 의 서브트리 사이즈를 통해서 유추할 수 있다. 이것이 $a, b$ 혹은 $b, a$ 보다 크다면 $answer$ 함수에 서브트리 정점들을 모아서 호출해 주면 되고, 아닐 경우 위 관찰에 의해서 답이 존재하지 않는다.

만점 풀이

64점 풀이는 정말 잘 모르기 때문에 만점 풀이로 넘어간다. 의도된 만점 풀이는 전혀 직관적이지 않지만 매우 아름답다. 출제자에게 경의를 표한다.

일단 한동안은 그래프가 트리라는 가정을 그대로 유지하자. 가장 먼저 관찰해야 할 것은 $a \le n / 3, b \le (n - a)/ 2$ 라는 사실이다. 이 두 사실은 $a \le b \le c$ 라는 부등식과 $a + b + c = n$ 이라는 성질에서 바로 유도할 수 있다. 또한 이 사실을 통해서 다음과 같은 Lemma를 유도할 수 있다.

Lemma 3. 트리의 Centroid를 잡고, Centroid에 인접한 간선들만 끊어 봐도 문제를 해결하는 데 충분하다.

Proof. 끊은 간선이 Centroid에 인접하지 않다고 하자. Centroid를 포함하는 쪽을 $B$, 아닌 쪽을 $A$ 라고 생각할 수 있다. 이 때 끊은 간선을 Centroid에 가까워지는 방향으로 계속 옮겨 주면, $A$ 의 크기는 계속 증가하고, $B$ 의 크기는 계속 $n/2$ 이상으로 유지된다.

많이 갑작스럽지만, 그래프에서 아무 스패닝 트리나 잡고 비슷하게 문제가 해결되기를 기도해 보자. 아무 스패닝 트리를 잡은 후 이 스패닝 트리의 Centroid를 중심으로 잡고 문제를 해결해 보자. 확실하게 알 수 있는 사실은, Centroid를 트리에서 지웠을 때 $a$ 이상의 크기를 가지는 서브트리가 존재한다면, 트리 케이스와 동일하게 해당 서브트리를 잘라서 문제를 바로 해결할 수 있다는 것이다.

이제 문제가 해결되지 않은 경우는, Centroid를 지웠을 때 모든 서브트리의 크기가 $a$ 미만인 경우이다. 앞선 경우와 다르게 이번에는 이러한 상황에서도 문제가 해결될 수 있는 여지가 있다. 이유는 스패닝 트리에 포함되지 않은 간선들이 이 서브트리들을 연결시킬 수 있기 때문이다.

해당 Centroid를 지운 후 남은 서브트리들을 모두 하나의 정점으로 묶어서 생각하자. 각 정점에는 해당 서브트리에 원래 있던 정점의 개수를 가중치로 설정한다. 고로 우리는 모든 정점의 가중치가 $a$ 미만인 어떤 그래프를 만들 수 있다. 이렇게 만든 그래프가 연결되어 있을 이유는 없다는 데에 유의하라 (예를 들어 centroid가 절점일 경우 확실히 연결이 아니다).

이 그래프에 대해서도 앞과 비슷한 것을 알아낼 수 있는데, 바로 그래프의 연결 컴포넌트의 크기가 모두 $a$ 미만일 경우 답이 존재하지 않는다는 것이다. 이유는 다음과 같다. 두 연결 컴포넌트 중 하나는 Centroid를 포함하지 않는데, Centroid를 포함하지 않는 컴포넌트는 그래프에 주어진 연결 컴포넌트 중 단 하나만을 고를 수 있다. 고로 어떻게 골라도 컴포넌트의 크기가 $a$ 미만일 경우 문제의 답이 존재하지 않는다.

이제 그렇지 않은 경우 항상 답이 있음 을 보인다. 그래프의 연결 컴포넌트의 크기가 $a$ 이상인 것을 아무거나 하나 고른다. 어떠한 정점을 잡고 깊이 우선 탐색을 한 후, DFS preorder 상에서 가중치 합이 $a$ 이상인 가장 짧은 prefix를 아무거나 택해서 그것을 $A$ 라고 하고 나머지를 $B$ 라고 하자. 확실하게 $A$ 는 연결되어 있고, $B$ 는 centroid를 포함하기 때문에 역시 연결되어 있다. 이제 우리는 $a \le A \le 2a - 2$ 임을 알 수 있는데, 해당 prefix의 마지막 원소를 제외한 것의 크기가 $a - 1$ 이하이고, 그리고 마지막 원소의 크기 역시 $a - 1$ 이하이기 때문이다. $B$ 의 크기는 $n - 2a + 2$ 이상인데, $n - 2a + 2 \geq b$ 가 무조건 만족된다. $a \le c$ 이기 때문에, $2a + b \le a + b + c \le n + 2$ 가 성립하기 때문이다. 고로 원하는 모든 조건이 만족되었고, 이를 구현하면 100점을 받을 수 있다.

Problem 3. Rectangles

Problem

$N \times M$ 크기의 2차원 배열 $H$가 주어진다 ($0 \le H[i][j] \le 7\,000\,000$. 0-based). 직사각형 영역 은 4개의 정수 $x_1, x_2, y_1, y_2$ 로 정의되며, $x_1 \le i \le x_2, y_1 \le j \le y_2$ 를 만족하는 모든 셀 $(i, j)$ 를 포함한다. 이 때 $1 \le x_1 \le x_2 \le N-2, 1 \le y_1 \le y_2 \le M-2$ 이기 때문에 외곽에 있는 셀은 포함할 수 없다.

유효한 직사각형 영역 은, 직사각형 영역 내 모든 셀 $(i, j)$ 에 대해, $min(H[x_1 - 1][j], H[x_2 + 1][j], H[i][y_1 - 1], H[i][y_2 + 1]) > H[i][j]$ 을 만족하는 직사각형 영역을 뜻한다. 모든 가능한 유효한 직사각형 영역의 개수를 반환하라.

Solution

Subtask 1 (7점)

직사각형 영역으로 가능한 모든 $x_1, x_2, y_1, y_2$ 을 나열한 후, 유효한 직사각형 영역의 정의를 만족하는지 단순하게 판별한다. 직사각형 영역으로 가능한 셀의 개수는 $O(n^2m^2)$ 이고 정의를 만족하는지는 문제 지문을 따라하면 $O(nm)$ 에 확인 가능하기 때문에, 전체 문제가 $O(n^3m^3)$ 에 해결된다.

Subtask 2 (15점)

유효한 직사각형 영역을 찾는 조건은 다음과 같이 쓸 수 있다.

• $min(H[x_1 - 1][j], H[x_2 + 1][j]) > H[i][j]$
• $min(H[i][y_1 - 1], H[i][y_2 + 1]) > H[i][j]$

이렇게 되면 각 행과 열에 대해서 문제가 분리된다. $j$ 가 고정되었을 경우 $H[x][j]$ 의 구간 최댓값을 구해서 그것만 비교해도 되고, $i$ 가 고정되었을 경우 마찬가지로 $H[i][x]$ 의 구간 최댓값을 구하면 된다. $RM[i][j][k] = Max_{x = j}^{k} H[i][x] $ 라고 정의하자. 비슷한 방법으로 $CM[i][j][k] = Max_{x=j}^{k}H[x][j]$ 라고도 정의하자. 이 값은 단순한 방법으로 $O(nm(n^2+m^2))$ 에 구할 수 있다. 이제 유효한 직사각형인지 조건을 모든 $i$ 에 대해서 따로, $j$ 에 대해서 따로 판별하면 되니 $O(n+m)$ 에 조건이 확인된다. 전체 문제가 $O(n^2m^2(n+m))$ 에 해결된다.

Subtask 6 (28점)

모든 입력이 0과 1뿐이니 직사각형 경계 밖에 있는 셀은 모두 1이고 안에 있는 셀은 모두 0이어야 한다. 그림으로 그리면 대충 이렇다:

?????????

??11111??

?1000001?

?1000001?

??11111??

?????????

여러가지 방법이 있는데, 가장 간단한 방법은 DFS를 사용하는 것이다. 0으로 이루어진 컴포넌트에 대해서 flood-fill을 한 후, Flood fill된 영역이 유효한 직사각형인지를 판별하는 식의 풀이가 가능하다. 유효한 직사각형인지를 판별하는 것은, 방문한 영역의 행/열 최대/최솟값, 그리고 방문한 영역의 개수를 세어주면 가능하다.

Subtask 3/5 (50점)

Subtask 2의 방법을 최적화하자. 각 행과 열에 대해서 분리해서 생각하는 전략은 그대로 사용한다. 다음과 같이 $LowR[i][j][k]$ 를 전처리하자:

• $LowR[i][j][k] = k$ 행에서 시작하여, $Max_{x = i}^{j}H[k][x] < min(H[k][i-1], H[k][j+1])$ 을 만족할 때까지 계속 $k$ 를 증가시켰을 때 그 결과

열에 대해서도 똑같은 방법으로 $LowC[i][j][k]$ 를 전처리 가능하고, 이에 $O(n^2m^2)$ 의 시간이 소요된다. 이제 한 직사각형이 유효한지를 $O(1)$ 에 판별할 수 있다. $LowR[y_1][y_2][x_1]$ 과 $x_2$ 의 값을 비교하면 모든 행에 대해서 조건이 만족하는 지를 알 수 있다. 반대 방향으로 열에 대해서도 할 수 있다. 고로 시간 복잡도는 $O(n^2m^2)$ 정도이다 (또한 Subtask 5가 자동적으로 해결된다.)

Subtask 4 (72점)

이미 필요로 하는 정보가 너무 많기 때문에 이를 줄여야지 더 큰 입력을 해결할 수 있다는 것을 눈치챌 수 있다. 다행스럽게도 다음과 같은 좋은 성질이 Subtask 4를 해결하는 데 큰 도움이 된다.

행열에 대해서 똑같은 조건을 판단해야 하니, 일단 문제를 간략화하기 위해 행에 대해서만 조건을 고려하고, 그것도 하나의 행에 대해서만 조건을 고려해 보자. 이 행을 $H[0], H[1], \cdots, H[n-1]$ 이라고 하면, 우리가 원하는 것은 $Max_{x=i}^{j} H[x] < min(H[i-1], H[j+1])$ 을 만족하는 쌍 $1 \le i \le j \le n - 2$ 에 대해 관심이 있다.

여기서 중요한 관찰이 있는데, 위 조건을 만족하는 쌍은 $n$ 개를 넘지 않는다. 가장 간단한 설명은 $Max_{x = i}^{j} H[x]$ 의 최댓값을 이루는 $x$ 를 고정시키는 것이다. $x$ 를 고정시켰을 경우, $x$ 왼쪽에 있는 숫자 중 $H[x]$ 초과인 가장 가까운 수, 오른쪽에서 $H[x]$ 초과인 가장 가까운 수를 두개 찾자. 이 두 수가 $i-1, j+1$ 으로 가능한 유일한 후보인 것이, 구간은 이 두 수를 넘어갈 수 없고 (넘어갈 경우 최댓값 조건이 깨짐) 구간은 이 두 수에 무조건 걸쳐야 하기 때문 ($min(H[i-1], H[j+1])$ 이 $H[x]$ 보다 커야 한다) 이기 때문이다. 고로, 각 $x$ 에 대해서 가능한 $i, j$ 는 (만약 존재한다면) 유일하게 결정 가능하며, 이는 stack을 사용하여 $O(n)$ 시간에 찾을 수 있다.

이제 조건을 만족하는 쌍을 각 행과 열에 대해서 선형 시간에 계산해 놓으면, 우리가 고려해야 할 쌍이 모두 $O(nm)$ 개라는 것을 알 수 있다. 숫자가 유의미하게 작아졌기 때문에 이러한 쌍들을 기준으로 생각해 줄 수 있다. 또한, 위에서 사용한 $LowR[i][j][k], LowC[i][j][k]$ 의 정의를 그대로 사용할 수 있는데, 조건을 만족하는 쌍의 개수가 많아야 $O(nm)$ 개이기 때문에, 이들에 대해서만 값을 계산해 주면 나머지의 값은 자명하기 때문이다. 각각의 올바른 $(i, j, k)$ 쌍에 대해서 $(i+1, j, k)$ 쌍이 올바른지는 이분 탐색이나 $N \times N, M\times M$ 버킷을 만드는 식으로 $O(\log NM)$ 내지는 $O(1)$ 에 가능하다.

이제 실제 답을 찾는 것에 주목하자. Subtask 4까지는 이 처리를 상대적으로 단순하게 해도 문제를 해결할 수 있다. 예를 들어, 직사각형의 왼쪽 변 ($r_1, r_2, c_1$) 을 고정시키고 생각해 보자. 왼쪽 변을 고정시키기 위해서는 $c_1$ 열에서 $(r_1, r_2)$ 가 조건을 만족하는 쌍이어야 하기 때문에, 왼쪽 변으로 가능한 후보는 많아야 $O(nm)$ 개이다. 이들에 대해서 이제 $c_2$ 를 증가시키면 되는데, 각 $c_2$ 에 대해서 $LowR[c_1][c_2][r_1]$ 이 $r_2$ 인지를 확인하고 그렇다면 답을 증가시키는 식으로 문제를 해결할 수 있다. 이 때 $c_2$ 로 가능한 경우의 수는 $O(m)$ 이므로 대략 $O(nm(n+m))$ 정도의 시간 복잡도에 풀린다. 이 때, $LowR[c_1][c_2][r_1]$ 값 하나를 $log$ 시간이 아니라 $O(1)$ 시간에 찾도록 잘 조정해야 함에 유의하라. 정렬과 같은 적절한 전처리로 $O(1)$ 시간에 하게끔 할 수 있다.

100점 풀이

두 가지 종류의 풀이를 알고 있다. 하나는 김세빈 학생과 내가 생각한 복잡한 풀이이고, 하나는 임유진 학생과 윤지학 조교가 생각한 상대적으로 간단한 풀이이다 (임유진 학생은 애석하게도 구현 후 TLE를 받았다고 한다. ㅠㅠ..) 두 풀이를 모두 소개한다.

복잡한 풀이 직사각형의 왼쪽 위 모서리 $r_1, c_1$ 을 고정시키자. 모서리를 고정시키면 왼쪽 변으로 올 수 있는 후보와 위쪽 변으로 올 수 있는 후보들의 집합을 알 수 있다. 전자는 $r_2$ 를 고정시키며 후자는 $c_2$ 를 고정시킨다. 첫번째 후보의 개수를 $L$, 두번째 후보의 개수를 $R$ 이라고 하면, 모든 $(r_1, c_1)$ 에 대해서 $L+R$ 의 합은 $O(nm)$ 이니, 적당히 이에 비례하는 시간 복잡도로 문제를 해결하면 된다는 것을 알 수 있다.

각 왼쪽 변 후보, 위쪽 변 후보에 대해서, 해당 위치에서 직사각형이 얼마나 멀리 갈 수 있는지를 위의 $LowR[i][j][k], LowC[i][j][k]$ 전처리를 통해서 바로 계산할 수 있다. 대충 $(r_1, c_1, r_2)$ 에서 가능한 직사각형의 최대 $c_2$ 를 $f(r_2)$, $(r_1, c_1, c_2)$ 에서의 최대 $r_2$ 를 $g(c_2)$ 라고 하자. 어떠한 직사각형이 유효하기 위해서는, $c_2 \leq f(r_2), r_2 \leq g(c_2)$ 가 만족해야 한다. 이는 사실 다음과 같은 기하 문제로 해석할 수 있다: $(r_2, c_1) - (r_2, f(r_2))$ 을 잇는 가로 선분과, $(c_2, r_1) - (c_2, f(c_2))$ 를 잇는 세로 선분이 존재할 때, 가로 선분과 세로 선분이 교차할 경우 올바른 직사각형을 이룰 수 있으니, 이러한 선분의 교차점의 수를 세는 것이다. 이는 Plane sweeping으로 풀 수 있음이 잘 알려져 있으며, 세로 선분을 $f(c_2)$ 순으로 정렬한 후 행에 대한 fenwick tree를 관리하면 해결할 수 있다.

간단한 풀이 사실 조건을 만족하는 직사각형은 $nm$ 개를 넘지 않는다. 72점 풀이에서 설명한 것과 똑같은 논리가 통하는데, 직사각형 영역 내의 최댓값을 이루는 $(i, j)$ 를 고정시키면, $(i, j)$ 왼쪽, 오른쪽, 위쪽, 아래쪽에 있는 숫자 중 $H[i][j]$ 초과인 가장 가까운 수가 직사각형을 고정한다. 이 네 경계를 넘어가면 최댓값 조건이 깨지고, 이 네 경계에 미치지 못하면 유효한 직사각형이 안 되기 때문이다. 고로, 이러한 최대 $nm$ 개의 직사각형에 대해서 실제 문제의 조건이 만족하는 지를 판별하면 되고, 이는 Subtask 4에서 사용한 방법을 그대로 사용하면 된다 (이 경우에는 이분 탐색을 그대로 사용해도 문제가 없다). 시간 복잡도는 $O(nm \log nm)$ 이다.

IOI 2019 Day 2

IOI 2019 Day 2 대회가 종료되었다. 한국 학생들의 성적은 다음과 같다.

• 김세빈, 100 / 100 / 40 / 72.30 / 66 / 57, 435.30점, Day2 27등, 전체 18등, 금메달.
• 윤교준, 72 / 100 / 40 / 90.97 / 66 / 57, 425.97점, Day2 16등, 전체 22등, 금메달.
• 임유진, 72 / 100 / 40 / 61.41 / 66 / 57, 396.41점, Day2 40등, 전체 37등, 은메달.
• 이온조, 38 / 100 / 64 / 50.61 / 52 / 24, 328.61점, Day2 120등, 전체 83등, 동메달.

미국의 Benjamin Qi는 작년과 같이 이번에도 Day 2에서 조금 노는 (?) 모습을 보였고 1등 성적을 받지 못하였으나, 이미 Day 1에서 상당한 차이를 벌려놓은 이후이기에 안전하게 트로피를 얻었다. 이 외 러시아의 Ildar Gainulin, 캐나다의 Zixiang Zhou이 뒤를 이었다. Ildar Gainulin은 1번의 기회가 남았고, Zixiang Zhou는 3번의 기회가 남았다. 향후 성적이 상당히 주목된다.

한국은 총 금메달 2개, 은메달 1개, 동메달 1개로 국가순위 4등의 성적을 얻었다. 성적은 2013년 이후 한국 팀이 평균적으로 받는 수준과 유사하다. 더 잘할 수 있었던 팀인 것 같아서 아쉽지만 (특히 동메달 1등을 한 이온조 학생이 많이 안타까울 것 같다. 유감을…) 만족스러운 결과를 얻은 한국 팀 축하합니다!

Day 2 Notice

Problem 4. Broken Line

2차원 평면 상에 $N$ 개의 점이 주어진다. 각 점은 양의 정수인 $x, y$ 좌표를 가지고 있으며, 임의의 서로 다른 두 점이 같은 $x$ 좌표를 공유하지 않고, 임의의 서로 다른 두 점이 같은 $y$ 좌표를 공유하지 않는다. 당신은 (0, 0)에서 시작하는 꺾인 선 (Broken Line)을 그을 것이다. 꺾인 선은 항상 $X$ 축 혹은 $Y$ 축에 평행해야 하며, 그 외 다른 조건은 없다 (자신과 겹치거나 교차해도 된다). 당신은 하나의 꺾인 선 을 그어서 모든 점을 꺾인 선과 닿게끔 하고 싶으며 (끝점에 닿아도 닿는 것으로 간주한다) 이 과정에서 선이 꺾이는 횟수를 가능한 작게 유지하려고 한다.

이 문제는 Output Only 문제로, 오직 10개의 테스트 데이터에 대해서만 채점되며 이 테스트 데이터는 모두 사전공개되어 있다. (IOI 2017 Nowruz와 다르게 테스트 데이터의 실제 구성이 크게 중요하지는 않기 때문에 이에 대해서는 서술하지 않는다. 다만 영국 국기 모양 등 특수한 테스트 데이터들이 존재했다고 들었다.) 채점 기준은 복잡하니 실제 PDF를 확인하는 것을 추천한다.

Solution

Broken Line은 Output-only 문제이지만, 2010년 Maze, 2017년 Nowruz와는 상황이 다른 면이 있다. 이전의 경우에는 주최 측에서도 주어진 문제를 제대로 풀지 못하여서, 단순히 모범 코드가 풀 수 있는 테스트 데이터만을 제공하거나 (Nowruz) 아예 그 조차도 아닌 (Maze), 과학 올림피아드 대회에 적절하지 않은 문제들이었다.

이번 Broken Line은 주최에서 모든 입력에 대해서 100점을 받을 수 있는 풀이를 가지고 있음에도 불구하고, Output-only로 문제가 제시되었다. 다른 기하 문제들과 비슷하게 문제가 테스트 데이터 없이는 상당히 까다롭고, 또한 Visualizer를 주는 것이 도움이 된다고 판단했던 것 같다. 하지만 Output-only 문제의 고질적인 맹점인 휴리스틱의 통과는 막지 못하였던 것 같다. 이러한 점에서 이 문제는 2010 maze / 2017 nowruz보다는 2015 scales와 더 유사한 면이 있다 (적절한 휴리스틱을 사용하였을 때 점수를 더 얻을 수 있음). 물론, 2015 scales의 경우는 휴리스틱을 사용해서 점수를 많이 받기는 어려운 문제였음을 고려해야 한다.

Output-only 형태로 문제를 제시하는 것이 주는 이점이 존재하고 고려할 만하다고 보지만, 비과학적인 풀이가 통과하는 상황을 막지 못한 것은 아쉽다. 이것으로 대회 결과에 유의미한 영향이 있었다고 생각하지는 않지만, 주최 측에서 부분 점수 풀이를 가를 수 있는 과학적인 기준을 제시하는 데 실패한 것은 유감이다.

10점 전략

가장 단순한 10점 전략은 앞에서부터 순서대로 점을 덮는 것이다. (0, 0)에서 $X$ 좌표가 증가하는 방향으로 잇는데, 해당 $x$ 좌표에 점이 존재한다면 위로 올라가서 해당 점을 덮은 후 $(x, 10^9)$ 에서 다시 오른쪽 방향으로 이어준다. 이후 또 점이 존재한다면 아래로 내려가서 다시 $(x, 0)$ 에서 오른쪽으로 가며, 이렇게 위쪽과 아래쪽을 오가는 것을 반복한다. 이렇게 할 경우 각 점이 유도하는 꺾인 점의 개수가 정확히 2개이기 때문에, $2n$ 개의 선분을 사용하여 대략 10점 정도의 점수를 얻을 수 있다.

50점 전략

위 전략은 한 점에서 다른 점으로 움직이는 과정에서 하나의 선분을 낭비한다. 어차피 각 선분에 2개 이상의 점이 포함될 수 없으니 ($x, y$ 좌표가 모두 다 다름) 결국 대부분의 선분이 하나의 점을 가지고 있는 상황이 이상적일 것이다. 이를 위해서는 선분을 다른 방향으로 돌릴 때도 점을 낭비하지 않도록 신중하게 판단해야 한다.

다음과 같은 “나선” 을 그리는 아이디어를 생각할 수 있다: 초기 (0, 0)에서 시작해서, $x$ 좌표가 최대인 점을 세로로 지나고, $y$ 좌표가 최대인 점을 가로로 지나고, $x$ 좌표가 최소인 점을 세로로 지나고, $y$ 좌표가 최소인 점을 가로로 지나고.. 를 반복하여서 결국 시계 반대방향으로 돌면서 하나의 선분에 하나의 점이 배정되게끔 하는 것이다.

이렇게 하면 항상 점 하나를 제거할 수 있으니 $N+3$ 개 정도의 선분으로 모든 점을 쉽게 덮을 수 있다고 생각할 수 있다. 하지만 이는 사실이 아니다. 다음과 같은 입력을 생각해 보자: $(1, 1), (2, 2), \cdots, (n, n)$ . 이 경우 위와 같은 전략을 사용하면 꼭지점에서만 점을 포함하고 대부분의 선분이 낭비됨을 알 수 있다. 더 자세히 실패 원인을 분석하면, $x$좌표 최대인 점을 방문하면서 이미 $y$ 좌표가 너무 높아진 경우가 존재하여, 이후 남은 점중 $y$ 좌표가 최대인 점을 지날 경우 이것이 예상보다 뒤에 있기 때문에 한번 돌아가야만 이 점을 방문할 수 있기 때문이다.

나선 전략에는 이와 같은 문제가 있으나, 실제 단조성이 없는 대부분의 입력 데이터에서는 이러한 것이 큰 문제가 되지 않는다. 단조성이 필요한 입력 데이터가 공식 데이터에는 많은 편이지만, 아무튼 이 때의 낭비를 무시하고 구현할 경우 50점 정도를 받는다.

100점 전략

이 문제는 $N+3$ 개의 선분을 사용해서 항상 해결할 수 있으며, 이 전략은 $O(N\log N)$ 에 구현할 수 있다.

모든 점이 $(1, 1), (2, 2), \ldots, (n, n)$ 의 형태인 경우에는 항상 문제를 해결할 수 있다. 홀수번째 점은 가로 선분으로, 짝수번째 점은 세로 선분으로 덮는 것을 반복하면, 하나의 선분에 하나의 점이 대응되기 때문이다. 고로 우리는 총 두 가지 전략을 가지고 있다:

• 최대인 점이 겹치지 않는 인스턴스에서만 해결할 수 있는 나선 전략 (50점 풀이)
• 최대인 점이 언제나 겹치는 인스턴스에서만 해결할 수 있는 대각선 전략 (위에서 설명한 것)

정확히 두 극단에 있는 인스턴스에 대해서 문제를 해결할 수 있으나, 실제 문제에서 주어지는 입력들은 이 두 인스턴스가 복잡하게 섞여 있는 경우가 많다. 만약 다음과 같은 형태로 입력을 분할하는 것이 가능하다면 참 좋을 것이다.

• 오른쪽 위를 향하는 대각선으로 구성된 점들 (우상단 / 좌하단 점이 겹치는 케이스에 대응)
• 왼쪽 위를 향하는 대각선으로 구성된 점들 (우하단 / 좌상단 점이 겹치는 케이스에 대응)
• 나선 (그 외 모든 케이스에 대응)

이제 모든 점 집합에 대해서 위 세 집합으로 분할하는 것이 가능함을 보인다. 이에 대해서 여러 설명을 들었는데, 내가 들은 설명 중 가장 깔끔하고 구현이 간단한 것은 김홍녕 학생의 아이디어였다. 이를 설명한다.

기본적인 틀은 나선을 긋는 아이디어에 기반한다. 우리는 점 집합에 창문 치기 라는 작업을 반복한다: 점 집합이 주어졌을 때, 이 점 집합을 덮는 최소의 축 평행 직사각형을 찾는 것이다. 이렇게 되면 이 “창문” 에 걸친 점은 $x$ 좌표 최소 / 최대, $y$ 좌표 최소 / 최대가 되는 점들일 것이다. 창문에는 최대 4개의 점이 들어감을 알 수 있다. 이제, 창문에 들어간 점의 개수에 따라서, 창문에서 몇 개의 점을 뺄 것이다.

• 창문에 1개의 점이 걸쳐 있다면, 아무 대각선에나 넣어준다.
• 창문에 2개의 점이 걸쳐 있다면, 두 점 모두 창문의 꼭지점에 있으며, 서로 대각선에 반대되는 위치에 있다. 위치 구성에 따라서 두 대각선 중 하나에 넣는다.
• 창문에 3개의 점이 걸쳐 있다면, 정확히 하나의 점만이 창문의 꼭지점에 있다. 이 하나의 점을 두 대각선 중 하나에 적당히 넣고 제거한 후 계속한다.
• 창문에 4개의 점이 걸쳐 있다면, 이 4개의 점을 전부 제거해 준다. 이들은 나중에 나선을 덮는 데 사용할 것이다.

이 과정에서 계속 $x, y$ 좌표가 최대/최소인 점들이 사라지기 때문에, 창문의 크기는 줄어들며, 또한 계속 안쪽으로 수렴한다 는 사실을 알 수 있다. 즉, 창문 치기를 반복했을 때, 다음에 치게 되는 창문은 그 전에 치게 된 창문에 포함되는 위치에 생성된다.

이제 세 집합이 어떻게 생겼는지 확인하자:

• 대각선에 들어가는 점은 모두 각자의 방향으로 증가하는 쪽으로 향한다. 창문의 꼭지점의 위치가 계속 안쪽으로 줄어들기 때문에, 이들의 위치 역시 $x, y$ 좌표가 동시에 감소하거나 증가하는 쪽으로 나열되기 때문이다.
• 나선을 덮는 데 사용한 점들을 살펴보자. 이들은 서로 겹치지 않으며 안쪽으로 수렴하는 $K$ 개의 창문들로 구성되어 있다. 창문을 타고 나선을 돌면서 안에 있는 점들을 모두 이어주면 된다.

고로, 위 세 집합으로 분할하는 것이 가능하다. 이 알고리즘은 점을 $x$ 좌표 증가/감소, $y$ 좌표 증가/감소의 4개 순서로 정렬하고 앞에서부터 차례대로 scan하면 $O(N \log N)$ 에 구현할 수 있다. Output only라서 $O(N^2)$ 정도의 알고리즘을 구현해도 상관이 없지만, 이 풀이의 경우에는 $O(N^2)$ 에 구현하더라도 특별히 쉬워지는 부분은 없다.

각 세 집합을 덮는 방법을 알았으니, 이제 이들을 3개의 추가 선분만을 사용해서 덮는 것이 필요하다. 사실 이 부분이 귀찮다면 대회 시간에는 4개 이상의 추가 선분을 이용해서 덮어도 큰 상관이 없다고 생각한다. 3개의 추가 선분만을 사용해서 덮는 것은 여러 방법이 있을 것이라고 생각한다. 방법 중 하나는 달팽이 -> 증가 나선 -> 감소 나선 형태로 시작해서, 달팽이와 나선 간에 1개의 선분, 나선과 나선 간에 1개의 선분, 달팽이 앞에서 (0, 0)을 잇기 위한 낭비되는 선분 하나로, 총 3개를 사용하는 것이다. 각 선분을 어떠한 방향으로 이었는지가 매우 중요하고, 또한 각 나선이나 달팽이가 비어 있는 경우 등이 있으니 신중하게 구현하자.

Problem 5. Vision Program

$W \times H$ 격자가 있고, 각 격자에는 0 혹은 1이 적혀 있다. 이 격자에는 1이 정확히 2개 적혀 있는데, 당신은 두 1의 Manhattan distance가 정확히 $K$ 인지 아닌지를 판단하는 프로그램을 작성해야 한다.

물론 이렇게 하면 문제가 너무 쉬우니, 당신은 이 프로그램을 특정한 프로그래밍 언어를 사용해서 작성하여야 한다. 프로그래밍 언어는 초기 $W \times H$ 개의 Boolean constant에 접근할 수 있으며, 이들은 $0 \ldots WH-1$ 까지의 번호가 붙어 있다. 당신은 이 언어에서 4개의 구문을 사용할 수 있다:

• AND $X_1 \ldots X_k$ : 새로운 Boolean constant를 만드는데, 이 변수에는 $X_1 \ldots X_k$ 의 Boolean AND 값이 저장되어 있다.

• OR $X_1 \ldots X_k$ : 새로운 Boolean constant를 만드는데, 이 변수에는 $X_1 \ldots X_k$ 의 Boolean OR 값이 저장되어 있다.

• XOR $X_1 \ldots X_k$ : 새로운 Boolean constant를 만드는데, 이 변수에는 $X_1 \ldots X_k$ 의 Boolean XOR 값이 저장되어 있다.
• NOT $X_1$: 새로운 Boolean constant를 만드는데, 이 변수에는 $X_1$ 의 Boolean NOT 값이 저장되어 있다.

새로운 Boolean constant는 만들어진 순서대로 $WH \ldots$ 이상의 번호가 순서대로 붙으며, 그 다음 연산에서 접근 가능하다. 당신의 프로그램은 가장 마지막에 만들어진 Boolean constant에 답을 저장해야 하는데, 만약 거리가 $K$ 이면 답은 1, 아니면 답은 0이어야 한다. 또한, 새로 만든 Boolean constant는 최대 10000개 여야 하며, 각 Boolean constant가 참조한 constant의 개수의 합은 1000000개 이하여야 한다.

Solution

Subtask 1/2/5/6 (41점)

문제가 복잡하게 생겼고, 접근하기 조차도 어려울 것 같아서 겁을 먹기 쉽지만, 사실 단순한 알고리즘을 생각해보면 그렇게 어려운 문제가 아니라는 것을 알 수 있다. 각 점에 대해서 해당 점과 거리 $K$ 인 점들을 고려하고, 두 점 쌍이 모두 1 이면 답이 참이 되게끔 프로그램을 설계하자. 즉, 해당 점, 그리고 해당 점과 거리 $K$ 인 어떤 점의 값을 AND하였을 때 1인 것이 있다면 (OR) 답은 참이다. 이 전략은 (확인이 필요한 쌍의 개수) + 1 개의 상수를 새로 만들게 되는데:

• $max(W, H) \leq 10$ 인 경우에는 이 값이 2000개를 넘지 않는다.
• $min(W, H) = 1$ 인 경우에는 이 값이 400개를 넘지 않는다.
• 점 (0, 0) 이 1인 경우 그 “해당 점” 이 하나밖에 없으니, 그 점에 대해서만 쌍을 만들어주면 이 값이 400개를 넘지 않는다.

이 점을 감안하여 구현하면 41점을 받을 수 있다.

Subtask 3 (52점)

각 점 $p$ 에 대해서 해당 점과 거리 $K$ 인 점 $q_1, q_2, \ldots q_k$ 를 모두 고려해 준 수식의 결과는 다음과 같다.

$(p \land q_1) \lor (p \land q_2) \lor \ldots (p \land q_k)$

이것을 분배법칙으로 묶어주면:

$p \land (q_1 \lor q_2 \lor \ldots)$

이렇게 되면 새로 도입하는 식의 개수가 각 변수마다 겨우 2개밖에 되지 않아서 52점을 받을 수 있다.

100점 풀이

먼저 첫 번째로 맨하탄 거리계를 돌리는 아이디어를 생각할 수 있다. 맨하탄 거리 좌표계는 45도 회전하였을 때 쳬비셰프 거리 (Chebyshev distance) 가 됨이 잘 알려져 있다. 이 경우 같은 거리를 가지는 셀들의 집합이 다이아몬드에서 정사각형의 형태로 바뀐다. 일반적으로 다이아몬드보다는 정사각형의 형태가 직관적인 경우가 많고 이러한 식의 접근은 이 문제에서도 유리하다.

두 번째로, 맨하탄 거리가 정확히 $K$ 가 아니라, 맨하탄 거리가 $K$ 이상 인지를 판별하는 루틴을 구현하는 것을 생각해 볼 수 있다. 만약 우리가 맨하탄 거리가 $K$ 이상인지를 해결하는 루틴을 설계할 수 있다면, $K$ 에 대한 루틴과 $K+1$ 에 대한 루틴을 동시에 구현한 후, 두 루틴의 출력값이 다를 경우 답이 $K$ 이고, 같을 경우 답이 $K$ 가 아니라고 결론내릴 수 있다. 즉, 답이 $K$ 인지를 판별하기 위해서는, 답이 $K$ 이상인지, $K+1$ 이상인지를 판별한 후 이 두 값의 XOR을 취해주면 된다.

$K$ 이상으로 문제를 변환하였을 경우, 문제의 조건이 아주 예쁘게 분리되는 것을 확인할 수 있다. 앞서 소개한 축변환을 사용하면, 두 점의 맨하탄 거리가 $K$ 이상이라는 것은, 두 점의 $x - y$ 좌표 차이가 $K$ 이상이거나, $x+y$ 좌표 차이가 $K$ 이상임을 뜻한다. $x - y = p, x + y = q$ 라고 하면 이는 다음과 같이 쓸 수 있다.

$max(abs(p_1 - p_2), abS(q_1 - q_2)) \geq K$

이 때 max 항을 풀어보면:

$abs(p_1 - p_2) \geq K \lor abs(q_1 - q_2) \geq K$

고로, 우리는 $abs(p_1 - p_2) \geq K$ 인 점 쌍중 두 변수가 모두 1인 쌍이 존재하는지, $abs(q_1 - q_2) \geq K$ 인 점 쌍중 두 변수가 모두 1인 쌍이 존재하는 지를 또 개별적으로 판별한 후, 이 두 결과를 OR 로 합쳐주면 된다. 일반성을 잃지 않고 이를 $p (x - y)$ 에 대해서만 풀어주자. $q$ 에 대해서는 이와 똑같은 방식으로 해결하면 된다.

$-(m-1) \le i \le n - 1$ 에 대해서 변수 $P_i$ 를, $x - y = i$ 인 셀 중 1인 변수가 하나라도 존재하면 참, 아니면 거짓으로 정의하자. 이러한 변수를 구하는 건 단순히 $x - y = i$ 인 셀들에 대한 값을 OR로 구해주면 되기 때문에 단순하게 구성할 수 있다. 이제 인덱스의 차이가 $K$ 이상이며 모두 1인 두 셀 $P_i, P_j$ 가 존재하면 답이 참이 된다. 이는 모든 $i$ 에 대해서, $j \le i - K$ 인 모든 $j$ 에 대해 $P_i \land P_j$ 가 참이면 답을 1로 만들어 주면 된다. 이렇게 하면 $O((N+M)^2)$ 정도의 풀이를 유도할 수 있고, 상수가 크지만 대략 앞에서 유도한 풀이와 비슷한 점수를 받을 수 있다.

이를 $O(N+M)$ 개의 변수로 줄이는 것은 prefix/suffix OR을 관리하는 일반적인 테크닉으로 해결할 수 있다. 식을 다시 한번 정리해 보자:

$\bigvee_{-(m-1) \le i \le n-1, j \leq i - K}{(P_i \land P_j)}$

$\bigvee_{-(m-1) \le i \le n-1} \bigvee_{j \leq i - K}{(P_i \land P_j)}$

$\bigvee_{-(m-1) \le i \le n-1} P_i \land (\bigvee_{j \leq i - K}{P_j})$

$PFX_i = \bigvee_{j \le i}P_j$ 라고 추가적인 변수를 하나 더 정의하자.

$\bigvee_{-(m-1) \le i \le n-1} P_i \land PFX_i$

이렇게 할 경우 변수의 개수는 $O(N+M)$ 개, 상태 전이의 개수는 $O((N+M)^2)$ 라서 만점을 받을 수 있다.

첨언

모든 $i \geq -m+2$ 에 대해서, $PFX_i = PFX_{i-1} \lor P_i$ 라는 점화식이 만족하기 때문에 이렇게 할 경우 상태 전이의 개수는 $O((N+M)^2)$ 에서 $O(N+M)$ 으로 줄어든다. 이 문제에서는 제한이 널널하고, 어차피 셀의 개수가 $O(NM)$ 개이기 때문에 필요하지 않은 최적화이다.

이러한 식으로 변수의 개수와 상태 전이의 크기를 줄이는 테크닉은 이전에도 여러 프로그래밍 대회에 출제된 적이 있다. 주로 2-SAT과 연관된 문제의 변수의 개수를 줄이는 데 자주 사용되는데, 이 경우에는 단순히 Prefix의 변수 크기를 줄이는 것 뿐만 아니라, 위에서 언급한 점화식대로 상태 전이의 개수 역시 최적화해야 하는 경우가 많다. 이러한 테크닉을 사용하는 문제로는 다음과 같은 문제들이 있다:

• ARC 069 Flags
• PA 2010 Riddle
• Codeforces #326 Div1D. Duff in Mafia

Problem 6. Skywalking

평면 상에 $N$ 개의 가로 선분과 $M$ 개의 세로 선분이 다음과 같은 형태로 주어진다:

• 세로 선분들은 길이 $N$ 의 배열 $x, h$ 로 표현되며, $(x[i], 0)$ 과 $(x[i], h[i])$ 를 잇는다. 이 때 $h[i] > 0, x[i] < x[i+1]$ 을 만족한다.
• 가로 선분들은 길이 $M$ 의 배열 $l, r, y$ 로 표현되며, $(x[l[i]], y[i])$ 와 $(x[r[i]], y[i])$ 를 잇는다. 이 때 $0 \le l[i] < r[i] \le n - 1, 1 \le y[i] \le min(h[l[i]], h[r[i]])$ 를 만족한다. 두 세로 선분은 끝점에서 만날 수 있지만, 그 외 점에서 만날 수 없다.

선분을 벗어나지 않고 움직이면서 $(x[s], 0)$ 에서 $(x[t], 0)$ 으로 가는 최단 경로가 존재한다면 그 길이를 계산하고, 없다면 -1을 반환하라.

Solution

Subtask 1 (10점)

두 선분이 교차하는 위치에 일일이 점을 만들어줘도 그래프가 아주 크지 않다. 고로 $O(E \log E)$ 에 동작하는 Dijkstra’s algorithm 으로 최단 경로를 구하는 식의 풀이를 사용하면 된다. 교점들을 모두 $O(NM$) 시간에 일일이 계산하자. 가로 선분에 대해서 해당 선분이 포함하는 교점의 위치를 전부 나열한 후 (정렬 후 이진 탐색으로 가능) 이들 교점 간에 간선을 이어준다. 세로 선분에 대해서도 동일하게 진행한다. 이렇게 만든 그래프에서 최단 경로 알고리즘을 사용하면 된다. 중복된 교점이 만들어지지 않게 조심하라 (std::unique 를 사용)

Subtask 2 (24점)

교점을 $O(NM)$ 시간에 계산하지 않아야 하는데, 이는 Line sweeping을 사용하면 가능하다. $x$ 좌표가 증가하는 순으로 교점을 찾고, 현재 보고 있는 빌딩을 위 아래로 지나가는 모든 가로 선분을 std::set 과 같은 자료구조로 관리하자. 크게 3가지 이벤트를 처리해야 하는데, 가로 선분 추가, 가로 선분 제거, 그리고 현재 빌딩과 교차하는 가로 선분의 열거가 필요하다. 첫 두개는 자명하고, 마지막은 std::set이 y축으로 정렬되어 있다면 단순히 앞에서부터 순회하면서 교차하는 것에 대해서만 이어주고 나머지는 무시해 주면 된다.

Subtask 4 (57점)

Lemma가 직관적인 편이라 풀이를 짐작하는 것은 쉽지만, 이를 엄밀하게 증명하는 것은 해도 해도 문제가 생기는 기하의 묘미 상당히 까다롭다. 이 글에서는 완벽히 엄밀한 증명은 아니지만, 그래도 최대한 짧고 납득 가능한 증명을 시도한다.

$s = 0, t = n - 1$ 일 경우 첫번째로 관찰할 수 있는 것은 최단 경로의 $x$ 좌표가 감소하지 않는다는 ($x$-monotone) 것이다. 예제를 보면 알겠지만 이는 일반적인 경우 성립하는 명제가 아니고, $s = 0, t = n - 1$ 인 이 subtask에만 성립한다. 이를 증명하기 위해서는 다음과 같은 사실을 관찰해야 한다:

• 경로는 평면 상에서 교차하지 않는다. (최단 경로니 자명)
• 경로가 ㄹ자나 S자 형태로 굽어 있다면, 이를 $x$-monotone 하게 펼 수 있다.

두 번째 사실에 대해서 첨언하면, 대략 다음과 같이 펼 수 있다:

----*

....|

*---*

|....

*--->

와 같은 형태로, $x$ 축에서 거슬러 내려간 후 더 낮은 곳에서 시작하는 경로라면,

----*

....|

....|

....|

....>

와 같이, 모든 세로 선분이 $y = 0$ 에 닿아 있는 성질을 활용하면, 더 짧은 경로를 찾을 수 있다.

하지만 여기까지 관찰하여도 문제를 해결하기에는 충분치 않다. $x$-monotone한 상황에서 다른 알고리즘 (예를 들어 동적 계획법) 을 고안하더라도 여전히 간선과 정점이 많으며 이들을 효율적으로 처리하는 좋은 방법이 생기지 않기 때문이다. 이제는 다음과 같은 Lemma가 필요하다.

Lemma 1. 어떠한 가로 선분 $S$ 에서 세로 선분 하나를 이용하여 또 다른 가로 선분 $T$ 로 이동할 때, 이 세로 선분의 위치는 $S, T$ 의 양 끝점 중 하나라고 가정할 수 있다.

• Proof. 어떠한 최단 경로에서 사용하는 가로 선분의 수열을 $[H_1, H_2, \ldots, H_k]$ 라고 하자. 이 때 가로 선분의 수열에 저장된 선분들은, 만약 최단 경로가 원래 가로 선분을 전부 사용하지 않는다면, 원래 주어진 가로 선분들의 부분일 것이다. 가로 선분의 높이가 감소하는 순서대로 정렬하여서 수열을 처리하며, 각 단계에서 우리는 $H_i$ 가 $j < i$ 인 어떠한 다른 가로 선분 $H_j$ 의 양 끝점에서 끝나거나, 아니면 자신의 원래 양 끝점에서 끝나게 변형한다.

  $H_1$ 부터 고려하자. 만약 $H_1$ 의 시작/끝점이 원래 $H_1$ 의 시작점과 끝점이 아니라면, 이를 단순히 양 옆으로 늘려주고, 해당 끝에서 아래로 세로 선분을 타고 내려가게 변형해도 거리가 줄어들지 않는다 (어떠한 경로를 최단 경로로 변형했기 때문). 이렇게 되면 $H_1$ 이 사용되는 구간은 전체 구간이 되며, 다른 선분들은 원래 사용되던 구간들이 줄어들거나 아예 사라졌을 가능성이 존재한다. 이제 $H_2, \cdots, H_i$ 에 대해서 다음과 같은 알고리즘을 적용한다:

  • $H_i$ 전부가 다른 $H_j$ 들에 의해서 덮여 사라졌거나, 양 끝점이 다른 $H_j (j < i) $ 에 의해 모두 좁아졌다면 증명 종료.
  • 일반성을 잃지 않고 $H_i$ 의 현재 시작점이 원래 시작점과 다르며, 시작점이 다른 $H_j (j < i)$ 에 의해 좁혀지지 않았다고 하자. 시작점을 원래 시작점 방향으로 계속 왼쪽으로 밀어준다. 이 과정에서 다른 $H_j (j < i)$ 를 만났다면 그 위치에서 정지하고 최단 경로를 늘려준 구간으로 변형한다. 그렇지 않고 시작점까지 갔다면 시작점에서 정지한후 앞과 같이 시작점에 닿는 세로 선분을 타고 내려가도록 한다. 이 과정에서 중간 경로는 모두 최단 경로로 대체되었으니 길이가 줄지 않았다.

이제 동적 계획법을 사용할 수 있다. 일반성을 잃지 않고 가로 선분은 길이가 0이라고 하자 (나중에 답에 $X[n-1] - X[0]$ 을 더해주면 된다). $DP[i][j]$ = $(x[i], j)$ 위치로 오는 최단 경로 라고 정의하자. 이 때 $j$ 의 범위가 너무 클 수 있으니, 의미있는 위치에 대해서만 (어떠한 선분의 높이 $y[i]$ 와 일치하는 $j$ 에 대해서만) 상태를 관리해 줘야 한다.

이제 상태전이는 다음과 같다.

• 만약 $(x[i], j)$ 가 어떠한 가로 선분의 시작점이면, $DP[i][j] = min_{0 \le k \le y[i]}(DP[i-1][k] + abs(j-k))$ (시작점에 값 지정)
• 만약 $(x[i], j)$ 가 어떠한 가로 선분의 끝점이면, 모든 $0 \le k \le y[i]$ 에 대해 $DP[i][k] \leftarrow min(DP[i][k], DP[i-1][j] + abs(j-k))$ (끝점에서 나오는 값 뿌려주기)
• 그 외 모든 경우에 대해 $DP[i][k] = DP[i-1][k]$

이러한 연산을 단순하게 하면 $O(NM)$ 시간이 들지만, Lazy propagation을 동반한 Segment Tree를 사용하여 $DP[i][j] - j, DP[i][j] + j$ 의 최솟값을 관리하면 각 시작점과 끝점에 대해서 $O(\log M)$ 에 모든 처리가 되기 때문에 $O((N + M) \log M)$ 시간에 문제가 해결된다.

이 풀이를 훨씬 더 간단하게 변형할 수도 있는데, 이에는 다음과 같은 Lemma가 필요하다.

Definition. 어떠한 끝점 $(x[i], j)$ 에 아래로 인접한 선분을, $l[k] \le x[i] \le r[k]$ 를 만족하며, $y[k] < j$ 를 만족하는 선분 중 $y[k]$ 가 가장 큰 것으로 정의하고, 위로 인접 한 선분은 $y[k] > j$ 에 대해 동일하게 정의하며, 이 둘을 합쳐 인접 한 선분이라 하자.

Lemma 2. 시작점과 끝점에 대한 상태 전이를 할 때, 모든 선분에 대해서 할 필요가 없이, 인접한 두 선분에서만 값을 받고 뿌려주면 된다.

Proof. Lemma 1과 비슷한 증명법을 사용한다. 어떠한 최단 경로를 높이가 감소하는 순으로 처리하면서, 위 Lemma를 만족하게끔 변형할 것이다. 이는 다음과 같이 진행된다:

• 현재 높이에서 덮이지 않은 (이보다 더 높은 위치에서 통과하지 않은) $x$좌표 구간들을 고려하자. 각 처리 과정에서 이들 구간들을 최소한으로 좁혀준다 - 현재 높이에서, 해당 구간의 시작점이나 끝점을 지나는 가로 구간들이 있으면, 해당 구간을 타고 최대한 많은 $x$ 구간을 덮어주며, 전부 덮는 것에 실패하였다면 거기서 아래 방향으로 세로 선분을 타고 빠져나가게 하자. 이를 반복하면, 모든 이동이 아래로 인접 / 위로 인접한 선분을 타고 가는 것으로 표현된다.

이제 위 상태 전이에서 전체 구간을 고려할 필요가 없이 양 옆으로 인접한 구간만 고려하면 되기 때문에, Segment tree를 사용할 필요가 없고, Subtask 2와 거의 동일한 풀이를 사용할 수 있다. 똑같이 Line sweeping을 진행하는데, 각 가로 선분에 대해서, 해당 선분의 끝점, 그리고 끝점에 인접한 두 양 선분에 대해서만 교점을 만들어준다. 이렇게 할 경우 $N + 6M$ 개의 교점이 나오며, 이들을 Subtask 2와 동일하게 처리해 주면 문제를 해결할 수 있다.

100점 풀이

$s = 0, t = n - 1$ 조건이 없으면 온갖 못 생긴 상황을 다 감수해야 한다. 일반성을 잃지 않고 $s < t$ 라 하자. 예를 들어:

이 경우 $s$ 에서 $t$ 로 가는 유일한 경로가 저런 모양으로 생겼다. 이러한 상황이 생기는 이유는 기본적으로 앞의 ㄹ자 형태를 풀어주는 argument가 먹히지 않아서고, 먹히지 않는 이유는 세로 선분에 높이 제한이 있기 때문이다. 만약 Subtask 3과 같이 모든 세로 선분의 높이가 동일하다면 ㄹ자 argument가 통해서 단조성이 성립하기 때문에 $s, t$ 가 $0, n-1$ 이 아니어도 57점 풀이와 같은 방식으로 문제를 해결해 줄 수 있다. 단순히 $s, t$ 왼쪽에 있는 선분들을 모두 무시해주면 되기 때문이다.

한편 이 반례를 그려보면 상당히 그럴듯한 해결책을 찾을 수 있다. 경로는 어떠한 시작점 $s$ 에서 가장 왼쪽 세로 선분인 $l$ ($l \le s$)을 거치고, 그 이후 가장 오른쪽 세로 선분인 $r$ ($r \geq t$) 를 거친 후, 끝점 $t$ 로 갈 것이며, $l \rightarrow r$ 로 가는 경로 자체는 57점 풀이와 똑같은 이유로 단조성이 성립한다. 결국 $s, t$ 근처에서 $l \rightarrow r$ 로 가는 경로를 진입하기 위해서 위와 같은 형태로 올라가는 것인데, 그렇다면 각 가로 선분에 대해서 $s, t$ 에 가장 가까운 점을 각각 2개, 총 $4M$ 개의 점을 추가하고, 이 점에 대해서 위 아래로 인접 한 점을 만들어주면, 위로 올라가는 길이 뚫린다고 생각할 수 있다. $4M$ 개의 점을 찾는 것은, 높이 순으로 정렬한 후 $x$ 축으로 정렬된 세로 선분들의 std::set을 가지고 있다면 스위핑 과정에서 lower_bound 및 upper_bound 연산으로 간단하게 찾을 수 있다. 이렇게 되면 그래프에는 총 $N + 18M$ 개의 정점이 생기고, 이 그래프에서 실제로 최단 경로를 구해주면 정답을 받을 수 있다. 이 때의 시간 복잡도는 $O((N + M) \log (N + M))$ 이다. 이제 이를 증명하려고 시도한다.

Lemma 3. 어떠한 가로 선분 $S$ 에서 세로 선분 하나를 이용하여 또 다른 가로 선분 $T$ 로 이동할 때, 이 세로 선분의 위치는 $S, T$ 의 $s$ 에 가장 가까운 양 끝점 중 하나라고 가정할 수 있다.

Proof. 사용되는 모든 가로 선분을 방문 순서대로 나열하고, 수학적 귀납법을 사용하자. 맨 첫 원소는 자명하게도 한쪽 끝점이 가장 가까운 앙 끝점 중 하나에 있다. 이제 두번째 원소부터 시작하자. 6가지 케이스가 있다.

• $S$ 가 $s$ 를 관통하며, $T$ 가 $S$ 에서 움직이는 것과 같은 방향으로 움직임
• $S$ 가 $s$ 를 관통하며, $T$ 가 $S$ 에서 움직이는 것과 반대 방향으로 움직임
• $S$ 가 $s$ 를 관통하지 않고 $s$ 에서 멀어지는 방향이며, $T$ 가 $S$ 에서 움직이는 것과 같은 방향으로 움직임
• $S$ 가 $s$ 를 관통하지 않고 $s$ 에서 멀어지는 방향이며, $T$ 가 $S$ 에서 움직이는 것과 반대 방향으로 움직임
• $S$ 가 $s$ 를 관통하지 않고 $s$ 로 가까워지는 방향이며, $T$ 가 $S$ 에서 움직이는 것과 같은 방향으로 움직임
• $S$ 가 $s$ 를 관통하지 않고 $s$ 로 가까워지는 방향이며, $T$ 가 $S$ 에서 움직이는 것과 반대 방향으로 움직임

모든 케이스에서 다음과 같은 전략을 사용하자: 만약 모순이 생겼다면, 해당 $T$ 에서 $s$ 에 조금 더 가까운 교점을 기준으로 선을 잇는다. 이 경우 이렇게 이은 선은 기존 최단 경로와 교차하는 지점이 존재한다. 이 지점에서 최단 경로를 교체해 주면 거리가 줄어들고 모순을 해결할 수 있다. 실제 확인은 손으로 잘 해보길 바란다.

Lemma 4. $s \rightarrow l$ 로 가는 최단 경로에서 사용한 세로 선분의 $x$ 좌표 수열을 $[SQ_1, SQ_2, \cdots, SQ_k]$ 라고 하자. 모든 $i$ 에 대해서 $SQ_i$ 는 $[SQ_1, \cdots, SQ_i]$ 의 최댓값이거나, 최솟값이다.

Proof. 그렇지 않은 $i$ 가 존재하면 해당 시점에서 값을 줄일 수 있다.

Lemma 5. 상태 전이를 할 때 모든 선분에 대해서 할 필요가 없이, 인접한 두 선분에서만 값을 받고 뿌려주면 된다.

Proof outline. Lemma 4에서 사용한 $x$ 좌표 수열을 거꾸로 보면서 이를 “블록” 으로 분해한다. 각 블록은, $SQ_i > s$ 혹은 그 반대를 만족하는 maximal한 부분 수열이다. 이 부분 수열의 경로를 최대한 위쪽 으로 대체하자. 즉, 같은 거리를 유지하면서 위쪽으로 경로를 올릴 수 있다면 그렇게 하는 것이다. 이는 다음과 같이 할 수 있다. 경로를 아래로 타고 내려가면서 다음과 같은 대체 가 존재하는 지 확인하자:

• 현재 경로에서 $s$ 에 가까운 쪽으로 움직이고, $s$ 에 도달하기 직전에 세로 선분으로 탈출해서 다시 원래 최단 경로로 복귀 가능한 경로

이를 반복하다 보면 각 블록이 실제로 이루는 경로가 $s$ 에 가까워지는 방식으로 계속 좁아짐을 관찰할 수 있고, 이 과정에서 Lemma 4 역시 깨지지 않는다는 것을 알 수 있으며, 또한 모든 이동이 만들어 준 정점에서만 일어나도록 변형됨을 알 수 있다. 고로 주어진 $N + 18M$ 개의 정점에 대해서만 문제를 해결해주면 된다.

첨언

이 문제의 경우, 세로 선분에 대해서는 (일반성을 잃지 않고) 거의 제약 조건이 없으나, 가로 선분이 $y = 0$ 이라는 핵심적 제약 조건이 있어서 문제가 해결된다. 이 조건이 없더라도 $N$ 개의 축 평행 선분에 대해서 $(N + Q) poly(\log N)$ 에 문제를 해결할 수 있다고 들었다. 관심있는 독자는 시도해 보길.