IOI 2018 Day 2

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

• 노영훈, 100 / 37 / 49 / 100 / 51 / 36, Day2 13등, 종합 12등. 금메달.
• 강태규, 100 / 25 / 49 / 100 / 69 / 19, Day2 11등, 종합 17등. 금메달.
• 김세빈, 100 / 37 / 49 / 63 / 51 / 60, Day2 20등, 종합 18등. 금메달.
• 윤교준, 100 / 5 / 49 / 86 / 51 / 4, Day2 38등, 종합 59등. 은메달.

IOI Statistics를 보았을 때, 평균 성적과 만점자를 통틀어 봐도 최근 10년 대회 중에서 이보다 어려운 하루가 없었다. Doll이 가장 쉬운 문제로 제안되었으나, 함정에 빠지기도 쉽고, 좋은 아이디어를 생각해야만 풀 수 있는 문제라는 것이 나의 생각이다. Highway는 답이 간단하지만 여러 관찰을 성공적으로 해야 하는 아이디어성 문제고 (IOI 2012 Supper와 유사), Meetings는 생각과 구현 모두 힘들어 아이디어 뿐만 아니라 시간까지 필요한 문제이다.

이러한 점을 감안했을 때 학생들의 Day 2 성적은 거의 흠잡을 것이 없는 수준이다. 개인적으로는 학생들의 meetings 성적이 조금 아쉬우나 대회를 치는 입장에서는  이해가 된다.

Day 2는 번역하면서 남는 시간이 없어서 따로 문제를 풀어보았고, 고로 풀이 업로드가 늦었다. 늦게나마 문제의 요약과, 해당 문제들의 풀이를 써 보려고 한다.

Problem 4. 기계 인형

Problem

방향 그래프의 일종으로 모델링 할 수 있는 기계 인형이 있다. 기계 인형은 세 가지 종류의 정점을 가진다.

• 시작 정점. 번호는 0번이다. Outdegree가 1이다. (간선으로 연결된 정점을 $C_0$ 이라 표현한다. )
• 트리거 정점. 번호는 $1, 2 \cdots M$ 이다. Outdegree가 1이다. (간선으로 연결된 정점을 $C_i$ 라 표현한다)
• 스위치 정점. 번호는 $-1, -2, \cdots, -S$ 이다. Outdegree가 2이다. (두 간선으로 연결된 정점을 각각 $X_{-i}, Y_{-i}$ 라 표현한다.)

기계 인형의 동작을 만들기 위해서는, 시작 정점에 구슬을 넣어야 한다. 구슬은 시작 정점에서 출발하여 다음과 같은 행동을 한다.

• 시작 정점에서는 아무 것도 하지 않고, $C_0$으로 출발한다.
• $i$번 트리거 정점에 들어오면, 기계 인형은 $i$번 춤을 춘다. 이후 $C_i$로 출발한다.
• $-i$ 번 스위치 정점에 들어오면, 기계 인형은 맨 처음 $X_i$로 출발하며, 그 다음 도착했을 때는, $Y_i$ 로 출발하며, 그 다음 도착했을 때는, $X_i$ 로 출발하고... 이를 반복한다.

기계 인형이 출 수 있는 춤의 리스트는 정해져 있다. 즉, 숫자 $M$은 고정이다. 하지만 스위치 정점의 개수 $S$, 그리고 모든 정점에 대해서, 나가는 간선이 향하는 정점 번호는 당신이 설정할 수 있다. 당신은 $S$, 그리고 모든 정점에 대해서, 나가는 간선이 향하는 정점 번호를 적절히 설정하여야 하고, 설정한 후에 다음 조건을 만족시켜야 한다.

• 길이 $N$의 수열 $A$가 주어진다. $1 \leq A_i \leq M$ 이다. 이 수열은 당신의 원하는 기계 인형의 춤 동작 순서이다. 기계 인형의 시작 정점에 구슬을 넣고, 구슬이 처음으로 다시 시작 정점에 돌아오기까지 추는 춤의 순서는, 위 수열과 정확히 일치해야 한다.
• 모든 스위치 정점을 짝수 번 방문해야 한다.
• 스위치 정점의 개수를 최대한 작게 사용해야 한다. $S \leq 400000$ 을 만족하지 못하면 Wrong Answer를 받는다. $S \leq N + log_{2}(N)$ 을 만족하지 못하면 100점을 받지 못한다.

Solution

결국 주어지는 sequence를 순서대로 방문하게 하는 회로를 구성하는 건데, 문제의 상황이 간단하지 않다.. 이럴 때는 간단한 서브태스크부터 풀어 나가면서, 문제와 친해지는 것이 도움이 된다. 문제가 쉽지는 않지만, 서브태스크만 따라가도 문제의 접근 방법에 대해서 아주 큰 힌트들을 얻을 수 있다.

Subtask 1 (2점)

방문하는 트리거 순서가 서로 다르다면 각각의 트리거에 대해서 다음으로 가야 할 트리거가 정해진다. 그 값을 그냥 적어주면 0개의 스위치 정점으로 쉽게 문제를 풀 수 있다. 이 때 $S = 0$. 문제를 이해했다면 거저 주는 subtask.

Subtask 2 (6점)

이제는 서로 다른 수가 2개이니, 각각의 트리거에 대해서 다음으로 가야 할 트리거가 많아야 2개이다... 고로 트리거만으로는 되지 않고 스위치를 도입해야 한다. 다음으로 가야 할 정점이 1개 이하이면 원래대로 하고, 다음으로 가야 할 정점이 2개면, 스위치를 하나 달아준다. 예를 들어 $P A \cdots P B$ 와 같은 형태로 방문하도록 회로를 구성하고 싶다면, $P$에 대한 스위치를 $(X, Y) = (A, B)$로 설정해 놓는다. 이렇게 해 놓으면 처음에는 $A$로 나가고 그 다음에는 $B$로 나간다. 고로 문제가 해결. 이 때 $S \leq \frac{N}{2}$

Subtask 3 (53점)

이제는 각 트리거에 대해서 다음으로 가야 할 트리거가 4개이다... 2개까지는 잘 했으니, 3개 / 4개를 어떻게 해야 할 지 알아보자.

하나의 스위치는 2개의 분기를 만드니, 4개의 분기를 만들기 위해서는 스위치의 스위치를 만드는 것을 생각해 볼 수 있다. 스위치의 스위치는 홀수 번째의 방문에는 왼쪽 스위치로, 짝수 번째의 방문에는 오른쪽 스위치로 공을 움직이며, 이 아래에 있는 왼쪽 / 오른쪽 스위치에 적절한 트리거를 달아준다. 이렇게 했을 때 모든 스위치는 여전히 짝수 번 방문되며, 모든 동작도 순서대로 작동되게 할 수 있다. 동작이 3개라면, 순서 맨 앞에 "스위치의 스위치" 를 방문하게 하자, 의미 없는 동작이 하나 생겨 4개의 동작으로 만들 수 있다.

이렇게 구성하면 각각의 트리거에 대해서 다음으로 가야 할 트리거보다 작은 개수의 스위치를 쓴다. 서브태스크 3에 대해서 만점을 받을 수 있다. 이 때의 점수는 16점.

위의 전략을 일반화하면, 결국 어떠한 트리거에 대해서 완전 이진 트리의 형태로 그래프를 만드는 해결책에 도달한다. 해당 트리거의 outdegree보다 크거나 같은 $2^K$를 찾아준 후, $2^K$ 크기의 이진 트리를 구성하자. 이진 트리의 뒤쪽에는 동작의 수열을 적어놓고, 앞 쪽에는 이진 트리의 루트를 방문시켜서 돌게 하면, 수열의 길이가 $2^K$로 맞춰지고 모든 조건이 만족된다. 이렇게 하면 일반적인 케이스에 대해서 $S \leq 2N$ 를 만족시켜서 37점을 추가로 받는다.

Subtask 4 (63점)

사실 트리를 각 트리거마다 따로 만들 필요는 전혀 없다. 그냥 전체 배열에 대한 큰 트리를 만들어 놓고, 모든 스위치들을 이 트리에 몰아넣으면 된다. 이러면 $N = 16$일 때 $15$ 개의 스위치만을 사용하고 10점을 추가로 받는다. 또한 문제에 대한 접근도 훨씬 간단해진다.

100점

$2N$ 개의 노드를 사용한다고 하지만 사실 이미 $N = 2^K$ 꼴일 때는 $N - 1$개의 노드만을 사용한다. 문제가 되는 시점은 $N = 2^K + 1$과 같이 루트로 돌려보내는, 쓸모 없는 노드들이 과하게 많이 생기는 경우이다.

일단 현재의 상황에서는 문제의 구조 때문에 쓸모 없는 노드들이 위 아래 서브트리에 고르게 퍼져 있다. 하지만, 쓸모 없는 노드를 꼭 처음에 돌면서 방문할 필요는 없다. 그냥 마지막만 아니면 된다. 고로 왼쪽 서브트리에 쓸모 없는 노드들을 모아놓고, 남은 위치에 쓸모 있는 노드들을 순서대로 잘 배치해 주는 것이 좋다.

쓸모 없는 노드들이 모여 있을 경우, 다음 Lemma를 사용하면 이들을 한꺼번에 제거할 수 있다.

Lemma. 어떠한 노드의 왼쪽 자식과 오른쪽 자식이 모두 루트라면, 이 노드를 제거하고 루트로 대체해도 된다.

위 조건들과 함께 따져보면 Lemma의 증명은 자명하다. 이렇게 쓸모 없는 노드들을 전부 날려버리면, 트리는 $\log N$ 개의 완전 이진 트리가 하나의 path에 매달려 있는 모습을 띄게 된다. 세그먼트 트리와 비슷한 논리로 $N + \log N$ 개의 스위치가 필요함을 보일 수 있다.

나의 소스 코드

Problem 5. 통행료

Problem

Simple connected undirected graph $G$와 이미 정해진 숫자 $A, B$ 가 당신에게 주어진다. 그리고, 당신은 다음 동작을 하는 기계를 가지고 있다.

• 당신이 $G$의 모든 간선에 $A$ 혹은 $B$ 의 가중치를 적어 주면, 이 기계는 $S$에서 $T$로 가는 최단 경로의 길이를 반환한다.

$S, T$ 는 $G$ 상의 정점이다. 기계는 $S, T$가 무엇인지 알지만 당신은 $S, T$가 무엇인지 모른다. 당신은 가능한 적은 동작으로 $S, T$를 알아내고 싶다. 60번 이하로 기계를 사용하지 않으면 0점을 받는다. 50번 이하로 기계를 사용하지 않으면 100점을 받지 못한다.

Solution

$D(s, t)$ 를, 모든 가중치가 1일 때 $s$와 $t$ 간의 최단 경로로 정의한다.

Subtask 1 / 2. $S = 0$, $G$ is a tree

Method 1. $N$ queries (5점)

모든 가중치를 $A$로 설정하면 $0$에서 해당 정점과의 거리 $D(0, T)$를 알 수 있다. $0$에서의 거리가 $D(0, T)$ 인 모든 정점에 대해서, 해당 정점과 해당 정점의 부모를 잇는 간선에 $B$를 한 번씩 칠해보고 거리가 $A \times D(0, T) + (B - A)$ 인지 확인해 본다. 최악의 경우 $1 + (N - 1)$ 개의 쿼리를 사용하여 제한 안에 문제를 해결할 수 있다.

Method 2. $\lceil \log N \rceil + 1$ queries (12점)

이 방법을 이분 탐색의 요령으로 최적화하면 된다. 후보 정점 set을 반으로 나눈 후 한 쪽에 $B$를 칠해 보고, 길이가 늘어나는 지 안 늘어나는 지 확인한다. 길이가 늘어나면 그 안에 $T$가 있고, 그렇지 않다면 그 밖에 있다. 최악의 경우 $\lceil \log N \rceil + 1 = 17 + 1 = 18$개의 쿼리를 사용하여 제한 안에 문제를 해결할 수 있다.

Subtask 4. $G$ is a tree (51점)

$S$와 $T$를 잇는 path 상에 있는 임의의 간선 $e$를 찾았다고 해 보자. $e$를 기준으로 한 쪽 서브트리에는 $S$가, 다른 한 쪽에는 $T$가 있다. $S$와 $T$를 잇는 경로가 두 서브트리의 루트를 지나니, 이러한 $e$를 찾기만 하면, Subtask 2의 문제를 $S, T$에 대해서 각각 두 번 해결하면 된다.

이러한 $e$는 어떻게 찾아야 할까? 위에서 했던 이분 탐색과 비슷한 방법을 사용할 수 있다. 먼저 한 번의 쿼리로 두 정점의 거리를 알아내자. 어떠한 간선들을 $B$로 칠했을 때 최단 경로가 늘어났다는 것은, $B$로 칠한 간선들과 $S, T$를 잇는 경로를 이루는 간선들에 교집합이 있다는 것이다. 위와 똑같이 이분 탐색을 할 수 있다. 후보 간선 set을 반으로 나눈 후, 교집합이 있는 쪽으로 크기를 줄여 나가면 된다.

이 방법이 사용하는 쿼리 수는 $1 + 17 + 17 + 1 + 17 + 1 = 54$ 개 정도이다. 하지만 잘 계산해 보면 실제로 사용하는 쿼리는 52개이다. 이유는 $N \leq 90000$ 이라는 꽤 이상한 입력 범위 때문이다. $e$를 찾은 후 $36$개의 쿼리를 사용하기 위해서는 $N \geq 2^{17} + 2$ 여야 하고, $35$개의 쿼리를 사용하기 위해서는 $N \geq 2^{16} + 2^{15} + 2 > 90000$ 여야 하기 때문이다. 어렵지 않으니 자세한 건 손으로 해 보길 권한다. 이렇게 되면 52번의 쿼리로 제한 안에 문제를 해결할 수 있다.

100점

$G$가 그래프가 됐고, 위에서 했던 모든 가정이 깨진다. 하지만 위와 같은 방향으로 문제를 푸는 것이 여전히 옳다. 믿고 계속 진행해보자. 

$S$와 $T$를 잇는 shortest path 중 하나에 속하는 간선이 존재하니, 그 간선을 $e$라고 부르자. 이러한 $e$를 이진 탐색으로 찾을 수 있다. $S$와 $T$의 최단 경로의 길이가 $D(S, T) \times A$ 초과라는 것은, $S$와 $T$를 잇는 모든 최단 경로에 $B$ 길이의 간선이 있음을 뜻한다. 처음에 모든 간선의 길이를 $A$로 해 놓은 후, 아무 간선이나 잡고 $B$로 길이를 늘려주는 것을 반복해 보자. 어느 순간에는 간선을 추가했을 때 길이가 $D(S, T) \times A$를 초과하게 될 것이고, 이 때 이 간선을 지움으로써 최단 경로가 사라졌으니, 이 순간에 추가한 간선은 최단 경로 중 하나에 속한다. 이 과정은 이분 탐색으로 빠르게 시뮬레이션 할 수 있다. 입력에서 간선이 $0 \cdots M - 1$ 까지 번호가 붙어 있으니, 최단 경로의 길이가 $D(S, T) \times A$로 유지되는 최대 길이의 prefix를 이분 탐색으로 찾으면 된다. 그렇다면 그 prefix의 뒤에 있는 간선이 $e$가 된다.

$e = (u, v)$를 찾았다고 하자. 일반성을 잃지 않고 최단 경로가 $S - u - v - T$의 형태라고 하자. $S$와 $T$를 구분하기 위해서는 $(u, v)$와의 거리를 비교하면 된다. $D(S, u) = D(S, v) - 1$이고, $D(v, T) = D(u, T) - 1$이 성립함을 어렵지 않게 알 수 있기 때문에, $S$의 후보는 $u$와 가까운 쪽에 있고, $T$의 후보는 그렇지 않은 쪽에 있다. 이렇게 BFS로 정점 집합을 나누면 $S$와 $T$를 서로 다른 집합 안에 넣을 수 있다.

또한, 어떠한 정점에서 시작하는 BFS 과정을 스패닝 트리로 나타낼 수 있는데 (최단 경로 트리), 이 과정을 그려보면 $S$는 $u$를 루트로 한 BFS 스패닝 트리 안에 있고, $T$는 $v$를 루트로 한 BFS 스패닝 트리 안에 있다. 어디서 많이 본 모습인데..??? 그렇다. 트리에서 본 그 서브태스크이다. 하지만 위에서 사용한 풀이를 그대로 적용하기는 약간 곤란해 보인다. 일단 쿼리 제한이 50번이기 때문에 호출 횟수도 과도하게 많고, 처음에 거리를 찾아내는 과정이 그래프에서 일반화되는 지도 확실치 않다. 여기서 서브태스크 2를 더 깔끔하고 적은 쿼리로 해결하는, Method 3을 생각해 보자.

Method 3. $\lceil \log N \rceil + 1$ queries

루트에서 시작해서 모든 정점을 거리 순으로 정렬한다. 정렬된 정점 집합의 prefix를 취하면, 이 정점들은 연결된 서브트리를 이룬다. 이 서브트리의 안과 밖을 잇는 모든 간선에 대해서 $B$의 가중치를 칠해 주자. 만약에 $T$가 서브트리 밖에 있다면 최단 경로가 바뀌고 그렇지 않다면 최단 경로가 바뀌지 않는다. 이렇게 되면 해당 수열의 왼쪽에 $T$가 있는지, 오른쪽에 $T$가 있는 지 알 수 있다.

Method 3은 각 BFS 스패닝 트리에서 거의 똑같이 시뮬레이션할 수 있고, 이 경우에는 맨 처음에 구한 최단 경로를 그대로 쓸 수 있기 때문에 추가적인 쿼리 1개가 필요하지 않다. 고로 50번의 쿼리로 100점을 받을 수 있다.

나의 소스 코드

Problem 6. 모임들

Problem

길이 $N$의 양의 정수 배열 $A_0, A_1, \cdots A_{N-1}$ 이 있다. $0 \leq L \leq v \leq R < N$ 를 만족하는 세 정수 $L, R, v$에 대해서, 당신은 $ Cost(L, R, v)$ 를 다음과 같이 정의한다.

• $Cost(L, R, v) = \sum_{i = L}^{v-1}{(Max_{j=i}^{v}(A_j))} + \sum_{i = v}^{R}{(Max_{j=v}^{i}(A_j))}$

$Q$ 개의 질의가 주어진다. 질의로 $L, R$이 주어질 때, 당신은 $Min_{v=L}^{R}(Cost(L, R, v))$ 를 반환해야 한다. 질의는 하나의 함수로 각각 주어지는 것이 아니고, 한꺼번에 주어진다. 즉, 오프라인 풀이가 가능하다.

Solution

$O(QN^2)$ (4점)

$v$를 기준으로 왼쪽으로 가면서 지금까지 만난 최댓값을 기억해놓고, 오른쪽도 비슷하게 훑으면 $Cost(L, R, v)$ 를 $O(N)$에 계산할 수 있다. 이를 모든 $L \leq v \leq R$ 에 대해서 계산하면 쿼리당 $O(N^2)$ 이 된다.

$O(N^2 + NQ)$ (19점)

이거는 그 정도는 아니고... 약간의 아이디어가 필요하다. 쿼리 당 $O(N)$ 의 시간을 쓸 수 있으니 $v$를 다 순회할 수는 있다. 고로, 왼쪽 / 오른쪽의 Max 합들을 $O(1)$ 정도에 알아내면 된다.

이는 간단한 전처리로 가능하다. $DL_{i, j} = (i$ 에서 $j$까지의 왼쪽으로 갔을 때의 Max 합) 이라고 정의하고, $DR_{i, j}$ 도 반대로 비슷하게 정의하자. 그렇다면, 답은 $DL_{v, L} + DR_{v, R}$ 의 최솟값이 될 것이다. $DL, DR$ 을 $N^2$ 에 계산하는 것은 쉽다. $i$가 되었을 때 단순 반복문으로 돌려주면 되기 때문이다. 시간 복잡도는 전처리 $O(N^2)$, 쿼리당 $O(N)$ 으로 $O(N^2 + NQ)$ 이다.

$H = 2$ (36점)

$H = 2$ 이기 때문에 특수한 케이스에 대해서만 효율적으로 처리해 주면 된다. 구간 $[L,R]$이 주어졌을 때, 어떠한 위치에 모임을 잡았을 때의 cost의 경우는 다음과 같이 나뉜다.

• Case 1. $A_i = 2$ 인 곳에서 만남: 답은 $2(R-L+1)$이다.
• Case 2. $A_i = 1$ 인 곳에서 만남: $i$를 포함하는, 1로만 이루어진 연속한 구간의 길이를 $X$라고 하자. 이 구간에 있는 위치만 비용 1로 움직일 수 있고 나머지는 전부 비용 2가 필요하다. 답은 $2(R-L+1) - X$이다.

최대 $X$를 알면 답을 알 수 있으니. 문제는 다음과 같은 구간 쿼리 문제로 환원된다.

구간 $[L, R]$이 주어졌을 때, 해당 구간 안에 포함되는 1로만 이루어진 연속한 구간의 최대 길이를 계산하라.

이는 Segment Tree로 해결할 수 있다. 각 노드에 대해서 다음 값을 저장하면 된다:

• 구간의 길이
• 1로만 이루어진 최대 길이 prefix
• 1로만 이루어진 최대 길이 suffix
• 해당 구간에 대한 답

시간 복잡도는 $O(N + Q\log N)$ 이다.

36점 초과의 풀이는 작성중이다.