IOI 2020
IOI 2020
IOI 2020 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다.
- 최은수, 100 / 100 / 100 / 100 / 93.00 / 100, 593.00점, 2등 (금메달)
- 송준혁, 75 / 100 / 100 / 100 / 92.62 / 65.32, 532.94점, 12등 (금메달)
- 임성재, 44 / 100 / 41 / 100 / 92.24 / 100, 477.24점, 30등 (은메달)
- 반딧불, 32 / 100 / 53 / 21 / 80.14 / 100, 386.14점, 61등 (은메달)
올해 한국 학생들의 개인 성적이 매우 우수한 편이다. 특히, 최은수 학생은 만점에서 7점 차이밖에 나지 않는 593점의 성적으로 전체 2등을 하였다. 이는 2015년 이후 첫 Top 5 성적이기도 하다. 축하합니다! 송준혁 학생도 12등이라는 상당히 높은 성적으로 마무리하였다. 임성재 학생은 Day 2에 만점에 가까운 점수를 얻어 거의 금메달에 근접했으나, 정말 아쉽게도 30등으로 마무리하였다. 30등은 은메달 중 가장 높은 성적으로, 작년 이온조 학생의 비슷한 결과가 떠오른다. 올해 Day 2는 높은 점수를 얻기가 예년 비해 쉬운 편이라, 아주 좋은 성적을 내었음에도 크게 돋보이지 못한 것이 아쉽다.
송준혁 학생과 반딧불 학생의 경우 내년에도 IOI를 참가할 수 있는 기회가 있으며, 반딧불 학생의 경우 내후년도 가능하다. 향후 한국 팀의 성과가 기대된다. 한국 팀의 팀 성적은 2금 2은으로, 높은 개인 성적에 비하면 약간 아쉬운 감이 있지만, 여전히 좋은 결과다.
이번 IOI의 1등은 William Lin으로, 600점 만점으로 모든 문제를 해결하였다. 축하합니다! 오랜만에 만점으로 마무리 된 IOI라는 점에서 알 수 있듯이, 전반적으로 평년에 비해서 쉬운 느낌이 있다. 최상위권을 가르는 수단이 mushrooms의 10점 남짓한 부분점수 뿐이었다는 것은 아쉽다.
Problem 1. 식물 비교
Problem
한 식물원에 $N$ 개의 식물이 원형으로 나열되어 있다. 각 식물은 $1$ 이상 $N$ 이하의 서로 다른 높이를 가지는데, 이 높이가 무엇인지는 정해지지 않았고 여러분들이 알 수 없다. 다만 모든 식물에 대해서 식물의 랭크 $R[i]$ 가 주어진다. 이는 식물 $i$ 의 오른쪽에 있는 $K-1$ 개의 식물들 중, 식물 $i$ 보다 높이가 큰 식물의 개수를 뜻한다. 입력으로 주어지는 랭크를 만족하는 높이의 수열이 최소 하나 있음은 보장된다.
당신은 두 식물 $x, y$ 의 높이를 비교하려고 한다. 물론, 입력으로 주어지는 랭크를 만족할 수 있는 수열이 여러 개 있을 수 있으니, 높이 비교가 바로 정의되지는 않는다. 당신은 어떠한 식물 $x$ 가 $y$ 보다 크다는 것을, 모든 올바른 높이 배정에 대해서 $H[x] > H[y]$ 가 만족한다 로 정의한다. 이 때, 당신은
- $x$ 가 $y$ 보다 큰지
- $y$ 가 $x$ 보다 큰지
- 둘 다 아닌지
의 세 경우 중 무엇에 해당되는지를 판단해야 한다. 마지막으로, 높이 비교는 한 번만 하는 것이 아니고, $Q$ 번에 걸쳐서 해야 한다.
이 문제의 출제자는 IOI 2014/2015 한국 국가대표로 출전한 조승현(ainta) 이다. 내가 아는 바에 의하면, 2003년 이후 한국인이 IOI 문제를 출제한 경우는 이번이 처음이다. 특히 이번 경우에는 교수진이 아니라, IOI에 참여한 경험이 있는 젊은 출제자라는 데에서 그 의미가 더 크다. IOI 참가와 다양한 대회 출제를 해 본 입장에서, IOI에 문제를 출제하는 건 내 개인적으로도 큰 꿈 중 하나이다. 앞으로도 많은 능력있는 참가자들이 이런 식으로 커뮤니티에 기여하는 일이 많았으면 좋겠다.
Solution
최근 몇년 동안 IOI는 그날 가장 쉽다고 여겨지는 문제 (혹은 Nowruz와 같이, 만점은 아니더라도 점수를 얻기 쉬운 문제) 를 1번에 배정하는데, 이번에는 1번 문제가 이 날 나온 문제 중 가장 어려운 문제였다. 주최 측의 코드를 읽어보더라도, 1번 문제를 2번 문제보다 쉽다고 예상하고 1번에 배치했을 가능성은 없어 보인다. 향후 대회 준비에 참고할만한 사례로 보인다.
Subtask 1 (5점)
$k = 2$ 이면, 우리에게 주어진 정보는 “두 인접한 식물간의 대소 관계” 뿐이다. 고로, 랭크를 무시하고 원 상에 있는 두 인접한 식물 간에 대소 관계를 $>, <$ 로 적어두자. 이 때 두 식물의 높이가 비교 가능하다는 것은
- 둘 간에 $>$ 로만 이루어진 경로가 있거나 (시계 방향이나 반대 방향 모두)
- 둘 간에 $<$ 로만 이루어진 경로가 있거나 (시계 방향이나 반대 방향 모두)
라는 것과 동일하다. 그렇지 않으면, $H[x] > H[y]$, $H[x] < H[y]$ 인 경우를 모두 만들 수 있다. 증명은 생략한다 (이후 글에서 명확해질 것이다).
이제 두 식물 $x, y$ 간의 경로가 $>$ 로만 이루어져 있는지, $<$ 로만 이루어져 있는지를 시계/반시계 방향 모두에 대해서 봐야 한다. 원을 직선으로 펴면, 이는 배열의 어떤 구간에 있는 모든 원소가 $>$ 인지, $<$ 인지를 보는 것과 동일하다. 고로 부분합을 사용하여 해결할 수 있다.
Subtask 2/3 (32점)
전체 식물 중 최대 높이를 가진 식물을 찾아보자. 일단, 최대 높이를 가진 식물은 $R[i] = 0$ 을 만족한다. 또한, 최대 높이를 가진 식물의 왼쪽에 있는 $k - 1$ 개의 식물들은 $R[j] \geq 1$ 을 만족해야 한다. $i$ 가 최대이기 때문이다.
여기서 우리는 $2k > n$ 일 때 위 조건을 만족하는 식물은 유일하다는 것을 알 수 있다: 만약에 그러한 식물이 두 개 이상 있다고 하면, 두 식물이 각각 겹치지 않는 길이 $k$ 의 구간을 필요로 하기 때문이다. 고로, 이 서브태스크에서 위 조건을 만족하는 식물은 유일하고, 최대 높이를 가진 식물을 찾을 수 있다.
이제 이런 식으로 모든 식물의 높이를 찾아보자. 위와 같은 방식으로 최댓값 ($N$) 을 찾은 후, 우리는 이 최댓값을 $0$ 으로 바꿈으로써 최솟값으로 만들어 줄 수 있다. 자신의 랭크를 $k-1$ 으로 두고, 왼쪽에 있는 $k-1$ 개의 식물의 랭크를 감소시키면 되기 때문이다. 그렇다면 이제 전체 식물의 높이가 ${N, N - 1, \ldots, 1}$ 에서 ${N-1, N-2, \ldots, 0}$ 와 같이 바뀌니, 높이가 $N-1$ 이었던 식물이 최댓값이 된다. 이를 위에서 했던 식으로 찾고, 이 식물의 높이도 최소로 바꾼 후 $(-1)$, 이를 $N$ 번 반복해서, $N-2 \rightarrow -2, N-3 \rightarrow -3$ .. 과 같이 높이를 바꿔주면 모든 식물의 높이를 유일하게 결정할 수 있다. 높이를 전부 알았으니, 이를 토대로 쿼리를 처리하는 것은 간단하다. 최댓값을 $O(N)$ 에 찾을 수 있고, 랭크를 $O(N)$ 에 업데이트 할 수 있으니, 전체 알고리즘은 $O(N \log N)$ 에 가능하다.
서브태스크 3은 $R[i]$ 배열을 lazy propagation을 사용한 세그먼트 트리로 관리하면 필요한 연산을 모두 $O(\log N)$ 에 할 수 있다. 어차피 만점 풀이에서도 필요한 자료구조이니, 해당 단락에서 같이 설명하겠다.
Subtask 5 (43점)
$N$ 크기 외에는 제약 조건이 없다. 고로 효율적이지는 않아도 올바른 알고리즘을 고안해야 한다. 서브태스크 2/3에서 고안한 풀이가 이미 충분히 어렵기 때문에, 만점 풀이도 해당 틀에서 크게 벗어나지는 않을 것이라고 추측할 수 있다. 고로 위 풀이에 기반해서 일반화하려고 시도해 보자. (우리는 $k = 2$ 일 때의 알고리즘도 알고 있기 때문에, 두 경우 모두 말이 되는 방식으로 일반화해보는 접근이 유용하다.)
서브태스크 2/3과 다른 점은 최댓값이 될 수 있는 식물들이 유일하지 않다는 것이다. 또한, 이 최댓값들 간의 높이를 비교할 수 있는 방법은 존재하지 않는 것으로 보인다. 고로, 이들을 같은 “최댓값 그룹” 으로 묶은 후, 한번에 지워주고, 두 번째 “최댓값 그룹” 을 찾는 식으로 반복할 수 있다. 이런 식으로, 크기가 높은 순서에서 낮은 순서로 식물들을 “그룹” 으로 묶어주자. 이 과정에서 한번 최솟값으로 줄어든 식물이 다시 그룹에 들어갈 수 있는데, 이들은 무시해야 한다. 이런 식으로 각 식물들에 $Group[i]$ 라고 하는 값을 지정해 주자.
원 상에서 두 정점의 거리를 $dist(a, b) = min(a-b, n-a-b)$ 라고 정의하자. 이런 식으로 그룹을 지정해주면, 현재 식물에서 거리 $k$ 미만인 점들간의 대소관계는 모두 정해진다. 거리가 $k$ 이상인 점들간의 대소관계는, 이렇게 직접 정해진 대소관계를 타고 간접적으로 유추하는 것 외에는 방법이 없어 보인다. 결론적으로 다음과 같은 핵심 정리가 유도된다:
- Theorem. $n$ 개의 식물을 정점으로 하고, $dist(a, b) < k, Group[a] > Group[b]$ 인 쌍 $(a, b)$ 에 대해서 $a \rightarrow b$ 로 가는 방향 간선을 추가한 DAG를 그렸을 때, 두 정점이 비교 가능하다는 것은 이 DAG 상에서 경로가 있다는 것과 동일하다.
사실 왜 DAG가 가지고 있는 정보가 우리가 알 수 있는 모든 정보의 집합에 대응되는 지는 잘 모르겠지만, 직관적으로 어필할 만한 부분이 어느 정도 있으니 굳이 증명하지는 않겠다. 나의 경우, 저 알고리즘을 생각한 후, 빨리 구현하여 서브태스크 5 점수가 나오는 지 확인하고, “아 대충 맞는구나” 하고 넘어갔다.
이제 전체 문제는
- $Group[i]$ 를 구하고
- DAG를 구성한 후 Floyd-Warshall로 모든 쌍 간의 경로를 계산한 후
- 각 쿼리에서 계산한 값을 반환
하는 식으로 하면 된다. 첫 번째 과정은, 각 그룹에서 최댓값이 될 수 있는 원소를 전부 확인하는 데 $O(N^2)$ (빨리 하면 $O(N)$) 시간이 걸린다. 두 번째 과정은 $O(N^3)$ 이다. 세 번째 과정은 $O(1)$ 이니, 총 $O(N^3+Q)$ 시간에 전체 문제가 해결된다.
Subtask 4 (60점)
서브태스크 4에서는, $Group[i]$ 를 구하는 부분만 최적화하면 된다. 항상 답이 -1이거나 1이기 때문에, $Group[x] \neq Group[y]$ 가 항상 만족을 하고, 대소 관계만 보면 된다. 이는 다음과 같이 할 수 있다.
- 어떤 식물이 최댓값이 될 가능성이 있는지는, $R$ 에 대한 세그먼트 트리를 두면 된다. 구간 최솟값과, 구간 덧셈을 지원하는 세그먼트 트리를 사용하면, $R$ 에 필요한 모든 연산을 $O(\log N)$ 에 할 수 있다. 이를 사용해서 위 알고리즘을 그대로 구현하면 $O(N^2 \log N)$ 이 된다.
- 각 레벨마다 최댓값으로 가능한 원소가 뭔지 일일이 돌지 않고, 위상 정렬을 하듯이 큐를 사용하여 최적화한다. 처음에 최댓값으로 가능한 원소들을 큐에 넣자. 어떠한 원소 $i$가 최댓값에서 최솟값으로 바뀐다고 하자. $[i-k+1, i-1]$ 구간과 $[i+1, i+k-1]$ 구간에서 가장 왼쪽에 있는 0만이 새로운 최댓값의 후보가 될 수 있음을 관찰할 수 있다. 세그먼트 트리의 구간에서 가장 왼쪽에 있는 0을 찾는 연산을, 트리를 타고 내려가는 식으로 $O(\log N)$ 에 구현하면 이 두 원소를 알 수 있다. 이 두 원소만 큐에 넣어주고, 반복하면 된다.
$R$ 배열이 원형 배열이라는 것이 골치아프다. 직선으로 펴서 처리한다고 구현이 쉬워지지 않는다. 케이스를 나눠서 직접 처리하는 게 차라리 낫다. 사실 각 쿼리에 대한 wrapper를 잘 짜서 넣으면 많이 짜증나지는 않는다.
만점 풀이 (100점)
만점 풀이에서는, 위와 같이 만든 DAG에서 경로가 있는지 여부를 빠르게 해결해야 한다. 원을 무한히 긴 직선으로 펴고, $dist(a, b)$를 $a - b$ 로 대체해서 생각해 보자. 한 정점에서 도달 가능한 다른 정점의 집합은 여기서 일종의 “삼각형” 으로 된 닫힌 영역 형태로 나오고, $x \rightarrow y$ 경로가 있는가는 $x$ 가 이루는 삼각형 영역에 번호가 $y$ 인 식물이 들어가는가로 판별할 수 있다. 조금 더 formal하게 두자면, 다음과 같이 표현할 수 있다.
- Lemma. $y < z < x, Group[y] > Group[z]$ 이며, $x \rightarrow y$ 경로가 있다면, $x \rightarrow z$ 경로가 존재한다.
고로, 왼쪽으로 가면서 고를 수 있는 “가장 높은” 경로를 찾아가면, 그 “높은 경로” 가 이루는 영역에 점이 있는지를 통해서 경로의 존재 여부를 판별할 수 있다. 이를 계산하기 위해 다음과 같은 함수를 정의하자:
- $Left[i] = j \in [i - k + 1, i]$ 구간에서, $Group[j] < Group[i]$ 를 만족하며 $Group[j]$ 를 최대화하는 $j$ (여러 가지가 있으면 가장 왼쪽)
- $Right[i] = j \in [i + 1, i + k - 1]$ 구간에서, $Group[j] < Group[i]$ 를 만족하며 $Group[j]$ 를 최대화하는 $j$ (여러 가지가 있으면 가장 오른쪽)
만약 저러한 $j$ 가 없다면 $Left[i] = i, Right[i] = i$ 로 정의한다. 이러한 $Left[i], Right[i]$ 는 $Group[i]$ 가 증가하는 순으로 스위핑한 후 최댓값 세그먼트 트리를 관리하면 된다.
이렇게 되면, $x$ 에서 $y$ 로 가는 경로가 존재하는가 여부는, $Group[i] > Group[y]$ 를 만족할 때까지 계속 $Left[i], Right[i]$ 를 타고 내려간 후, 최종적으로 구한 구간 안에 $y$ 가 들어가는 지를 보면 된다. 여기서도, 원이 무한히 긴 직선으로 펴져 있다는 식으로 생각하자. 이렇게 하면 각 쿼리는 $O(N)$ 에 해결이 된다. (이를 조금 변형하면 75점 풀이도 가능한데, 75점은 이것보다 쉽게 받을 수 있는 방법이 존재하는 것 같다). 이를 최적화하는 것은, $Left[i], Right[i]$ 를 Sparse table로 관리하면 된다. 이 때 원 한 바퀴를 넘어가는 것은, $Dist[k][i]$ = ($i$ 번 점에서 $2^k$ 번 왼쪽으로 가면서 넘어간 거리) 같은 거를 저장하는 식으로 잘 처리해 주자.
Problem 2. 슈퍼트리 잇기
Problem
$N$ 개의 정점이 있는 무방향 단순 그래프가 있다. 그래프의 간선이 무엇인지는 정해져 있지 않고, 여러분이 정하게 될 것이다. 무방향 단순 그래프이기 때문에, 여러분이 추가한 간선들은 서로 다른 두 탑을 이어야 하며, 중복 간선을 만들 수 없고, 양방향 간선이어야 한다.
이렇게 그래프를 만들 때 지켜야 할 조건이 있다. 이는 $N \times N$ 크기의 2차원 정수 배열 $p$ 로 표현된다. 각 원소 $p[i][j]$ 는, $i$ 와 $j$ 를 잇는 단순 경로 (simple path) 의 개수가 $p[i][j]$ 개여야 한다는 것을 뜻한다. $0 \le p[i][j] \le 3$ 임이 보장되며, 추가로 $p[i][j] = p[j][i], p[i][i] = 1$ 임이 보장된다. 이 조건을 만족하게끔 하는 그래프를 만들거나, 만들 수 없음을 판정하라.
Solution
그래프의 성질에 대해 잘 이해하고 있으면, 케이스 분석으로 해결할 수 있는 문제이다. IOI 문제로서는 간단한 편에 속한다. 난이도와 별개로, 그다지 인상적인 문제는 아니라고 생각한다.
Subtask 1 (11점)
모든 두 정점을 잇는 단순 경로가 정확히 하나인 그래프는 트리 이다. 아무 트리나 출력하면 된다: $1 \le i \le n - 1$ 에 대해서 $0$ 번 정점과 $i$ 번 정점을 잇는 간선을 추가해, star graph를 만들어 주자.
Subtask 2 (21점)
모든 두 정점을 잇는 단순 경로가 최대 하나인 그래프는 포레스트 이다. 주어진 $p[i][j]$ 조건을 만족하는 포레스트를 아무거나 출력하면 된다.
이 때, $p[i][j] > 0$ 이라는 것은 두 정점 $i, j$ 가 연결되어 있다는 뜻이라는 것을 생각해 보자. 우리는 이 정보를 통해서 주어진 포레스트의 연결 컴포넌트를 모두 알 수 있다. 고로, 연결 컴포넌트를 모두 찾아준 후, 각 컴포넌트마다 서브태스크 1처럼 트리를 만들어 주자.
마지막으로, 입력 자체가 불가능한 입력일 수 있으니, 두 점 $i, j$ 가 같은 컴포넌트에 있음과 $p[i][j] = 1$ 임이 항상 동치인지를 한번 더 확인해 주자.
Subtask 3 (40점)
Subtask 2의 요령으로 연결 컴포넌트를 찾아줄 수 있으나, 이제는 연결 컴포넌트 안에 있는 서로 다른 정점간에 정확히 두 개의 경로가 있어야 한다: 컴포넌트 하나를 사이클로 이어주면 이 조건을 만족시킬 수 있다.
이 역시 입력 자체가 불가능한 입력일 수 있으니, 두 점 $i, j$ 가 같은 컴포넌트에 있음과 $p[i][j] = 2$ 임이 항상 동치인지를 한번 더 확인해 주자.
Subtask 5 (96점)
일반성을 잃지 않고, 각 연결 컴포넌트에 대해서 해결해 주자.
다음과 같은 성질이 성립한다. 증명은 케이스 분석이고, 생략한다.
- Lemma. 답이 있다면, $p[i][j] = 1, p[j][k] = 1$ 일때 $p[i][k] = 1$ 이 성립해야 한다.
이는, 경로가 유일한 쌍 ($p[i][j] = 1$인 쌍) 들이 일종의 연결 컴포넌트와 같은 것을 이룬다는 것을 뜻한다. (수학적으로는 이를 equivalence class 라고 한다.) 고로 이들을 모두 컴포넌트로 분리해 주자.
각 컴포넌트를 트리 형태로 연결시켜 준 후, 하나의 정점으로 압축 시켜준 후, 문제를 계속 해결해 나가자. 인접 행렬 상에서는, 이제 $p[i][j] = 1$ 인 경우 둘은 하나의 정점으로 압축되어 있으니, $i = j$ 인 경우에만 $p[i][j] = 1$ 이 성립하고, 그 외에는 항상 $p[i][j] = 2$ 가 성립한다. 고로 이제 압축된 정점은 하나의 사이클로 연결해 주면 된다. 최종적인 그래프의 형태는, 사이클에 가지들이 달린 형태의 모양이 되겠다. 이 과정에서, 불가능한 경우에 0을 반환하도록 신경 써서 구현하자. 서브태스크가 나뉘어져 있지만, 불가능한 경우를 구분하는 것은 알고리즘적으로 어렵지는 않다. 구현은 Union-find를 사용하면 편하다.
만점 풀이 (100점)
한 연결 컴포넌트 안에 두 개의 사이클이 있으면 항상 두 정점 간을 잇는 경로가 4개 이상인 정점 쌍을 찾을 수 있다. 증명은 케이스 분석이니, 생략한다. 고로, 한 연결 컴포넌트 안에는 최대 하나의 사이클이 있으며, 그렇다면 두 정점 간을 잇는 경로는 최대 2개이다. 고로, 문제 제약 조건 상 $p[i][j] = 3$ 이면 답이 존재하지 않고, 0을 반환해 주면 된다.
Problem 3. 카니발 티켓
Problem
당신은 $nm$ 개의 티켓을 가지고 있다. 각 티켓에는 음이 아닌 정수가 적혀 있다. 각 티켓은 $n$ 가지 종류의 색으로 칠해져 있고, 각 색을 가진 티켓은 $m$ 개가 존재한다. 이 때 $n$ 은 짝수이다.
당신은 마스터와 함께 다음과 같은 게임을 총 $k$ 번 한다. ($k \le m$)
- $n$ 개의 티켓을 뽑는다. 이 때 뽑는 티켓의 색은 서로 달라야 한다.
- 각 티켓에 인쇄된 정수를 $a_0, a_1, \ldots, a_{n - 1}$ 이라고 하자. 마스터는 $f(b) = \sum_{i = 0}^{n - 1} a_i - b$ 를 최소화하는 $b_{min}$ 를 고른다.
- 마스터는 $f(b_{min})$ 만큼의 돈을 당신에게 주고, 뽑은 카드를 모두 버린다.
당신은 받은 돈의 합을 최대화해야 한다.
Solution
Subtask 1 (11점)
$m = 1$인 경우 $k = 1$이다. 고정된 수열에서 단 한번 게임을 하면 된다. 즉, 마스터의 입장에서 $f(b)$ 를 최소화하는 것이 우리의 목적이다.
이 때 $b = a_{n / 2}$ 로 정할 경우 $f(b)$ 가 최소화됨이 잘 알려져 있다. $f(b)$ 를 수직선 상에서 $b$ 와 $a_0, a_1, \ldots, a_{n-1}$ 과의 거리의 합이라고 생각해 보자. $b = a_{n / 2}$ 로 정했을 때, $b$를 증가시키면 $a_0, a_1, \ldots, a_{n-1}$ 과의 거리가 가까워지는 점들의 개수보다, 멀어지는 점의 개수가 크거나 같다. 감소시켜도 상황은 동일하다. 고로 $f(b)$ 가 더 작은 점은 $b$ 오른쪽에도, 왼쪽에도 존재하지 않는다.
이제 수열을 정렬하면 $f(b)$ 를 $O(n \log n)$ 에 구할 수 있다.
이 정도로만으로도 서브태스크 1은 충분하지만, 위 문제를 조금 더 간단하게 해 보자. 마스터 같은 복잡한 이야기는 집어치우고, 내가 $a = [a_0, a_1, \ldots, a_{n-1}]$ 을 골랐을 때 받을 돈의 양을 $game(a)$ 라고 정의하자. $a$ 가 정렬되어 있을 때:
$game(a) = \sum_{i = 0}^{n - 1} a_i - a_{n / 2} \ = \sum_{i = 0}^{n/2 - 1} (a_{n / 2} - a_i) +\sum_{i = n/2}^{n - 1} (a_i - a_{n / 2}) \ = \sum_{i = n/2}^{n - 1} a_i -\sum_{i = 0}^{n / 2 - 1} a_i + (n/2) a_{n/2} - (n/2) a_{n/2} \ = \sum_{i = n/2}^{n - 1} a_i -\sum_{i = 0}^{n / 2 - 1} a_i$
복잡도는 똑같지만, 이런 식으로 분석하는 것이 이후 접근에 훨씬 유용하다.
Subtask 4 (25점)
$k = m$ 인 경우 우리는 모든 티켓을 전부 사용한다.
위에서 관찰했듯이, $game(a)$ 는 전체 수열에서 가장 큰 $n/2$ 개를 더하고, 작은 $n/2$ 개를 빼는 함수이다. 우리는 티켓을 적당히 나누어서 이 $game(a)$ 의 호출 값의 합을 최대화해야 한다. 만약 우리가 적당히 티켓을 나눠서, 값이 큰 $nm/2$ 개의 티켓은 전부 더하고, 작은 $nm/2$ 개는 전부 빼게끔 할 수 있다면 문제가 간단할 것이다. 저렇게 적당히 티켓을 나눌 수만 있다면, 그것이 무조건 최적해가 될 것이기 때문이다.
다행이도 이러한 분할 방법이 존재한다. 우리가 “큰 값” 으로 가져갈 것을 $+$, 우리가 “작은 값” 으로 가져갈 것을 $-$ 라고 적어주자. 다음과 같은 정리가 성립한다.
-
Theorem. $n \times m$ 격자에 $\frac{nm}{2}$ 개의 $+$, $\frac{nm}{2}$ 개의 $-$ 가 적혀있다고 하자. 우리는 격자의 셀을 다음 조건을 만족하는 $m$ 개의 부분집합으로 분할할 수 있다:
- 각 부분집합의 크기는 $n$ 이고, 모든 셀은 서로 다른 행에 속한다.
- 부분집합에 $\frac{n}{2}$ 개의 $+$, $\frac{n}{2}$ 개의 $-$ 가 적혀 있다.
-
Proof. 다음과 같은 알고리즘을 사용하여 격자를 위 조건에 맞게 분할할 수 있음을 주장한다:
- 각 행의 번호를 $+$ 의 개수가 증가하는 순으로 $r_1, r_2, \ldots, r_n$ 이라고 하자.
- $r_1 \ldots r_{n/2}$ 에서 $-$ 를 아무거나 뽑는다.
- $r_{n/2+1} \ldots r_n$ 에서 $+$ 를 아무거나 뽑는다.
- 이를 $k$ 번 반복한다.
이 알고리즘은, 매 순간 $-$ 과 $+$ 를 뽑을 수 있다면 자명히 올바르다. 이제 그것이 가능함을 $m$ 에 대한 수학적 귀납법으로 보인다.
- $m = 0$ 일 경우 자명하다.
- $m > 0$ 일 경우, 만약 $r_1, \ldots, r_{n/2}$ 중에서 $-$ 가 없다고 하면, $r_{n/2}$ 에 $+$ 가 $m$ 개 있었으니 $+$ 가 최소 $(n/2+1)m$ 개 있으니 가정에 모순이다. 같은 이유로 $r_{n/2+1}$ 에 $+$ 가 없다고 하면 $-$ 가 최소 $(n/2+1)m$ 개 있으니 가정에 모순이다. 이제 이들을 뽑아서 제거해 주면, Theorem의 조건을 $m - 1$ 에 대해서 만족하는 격자를 새로 만들 수 있고, 고로 귀납 가정에 의해 성립한다.
고로 저렇게 분할한 부분 집합에 대해서 게임을 해 주면 자연스럽게 큰 값은 더해주고 작은 값은 빼지게 된다.
최댓값을 구하는 것은 정렬만으로도 가능하다. 하지만 이 문제에서는 각 티켓을 어떠한 라운드에서 썼는지도 출력해야 한다. Theorem의 증명에서 사용한 알고리즘을 그대로 구현하고, 분할한 부분집합에 적당한 인덱스를 매겨주면 된다. 정렬을 한 후, 각 행에 대한 $+$, $-$ 셀의 리스트를 적당한 자료 구조 (배열이나 큐) 로 구현하면 $O(nm \log (nm))$ 에 위 알고리즘을 구현할 수 있다.
Subtask 2/5 (53점)
위 관찰에 Dynamic Programming을 결합하면 $O((nk)^2)$ 시간에 동작하는 알고리즘을 유도할 수 있다. 이를 통해 서브태스크 2와 5가 해결 가능하다.
우리가 해결해야 하는 문제는, $n \times m$ 격자가 주어질 때, 각 행에서 $k$ 개의 원소를 적절히 골라서, 고른 원소들만 남기고 Subtask 4의 알고리즘을 적용한 값을 최대화해야 한다. Subtask 4의 알고리즘의 반환값은 가장 큰 $nk/2$ 개의 값을 더한 것에 가장 작은 $nk/2$ 개의 값을 뺀 것과 동일하다. 이런 식으로 두면 DP 등을 정의하기가 골치아프다.
하지만, 각 셀에 대해서 굳이 우리가 중간값보다 큰 지 작은 지를 따질 필요가 없다. 그냥 빼고 싶은 원소 $nk/2$ 개와 넣고 싶은 원소 $nk/2$ 개를 고르는 모든 경우를 다 시도해 보면 되기 때문이다. 이렇게 하면 어떤 값은 실제로 큼에도 불구하고 빼주게 되고, 어떤 값은 실제로 작음에도 불구하고 더해주는 식으로 원하지 않는 상태들도 계산이 된다. 하지만 이러한 원하지 않는 상태들은 어차피 답이 최적이 아니기 때문에, 고려된다 하더라도 실제 구하는 답이 바뀌지는 않는다.
고로 우리는 $n \times m$ 크기의 격자에서
- $nk/2$ 개의 셀을 골라 그들의 값을 더하고
- $nk/2$ 개의 셀을 골라 그들의 값을 빼며
- 각 행에 대해서, 위 두 과정에서 더하거나 뺀 셀의 개수가 정확히 $k$ 개가 되도록
해야 한다.
여기서 두 번째 관찰을 할 수가 있는데, 각 행에서 더하게 되는 셀은 가장 큰 셀들이고, 빼게 될 셀들은 가장 작은 셀들이라는 것이다. 모든 행의 티켓이 정렬되어서 주어지니, 고로 우리가 각 행에서 고를 수 있는 경우는
- 모든 $0 \le x \le k$ 에 대해, 왼쪽에 있는 $x$ 개를 빼고, 오른쪽에 있는 $k - x$ 개를 더하는
위와 같은 $k+1$개의 경우 뿐이다.
이제 이를 사용해서 Knapsack DP를 구성할 수 있다. $DP[i][j]$ 를, $i$ 번 행까지를 처리했으며, $j$ 개의 원소를 더했을 때의 최적해라고 정의하자. $DP[i][j]$ 를 계산할 때, 더한 원소의 개수를 $0 \ldots k$ 까지 전부 시도해 보면서 최적해를 구하면 된다. 어떤 원소를 빼고 더했는지는 일반적인 역추적 기법을 사용하면 된다. DP 테이블의 크기는 $n \times (kn)$ 이고, 한 엔트리를 구하는 데 $O(k)$ 의 시간이 걸리니, 시간 복잡도는 $O((nk)^2)$ 이다.
Subtask 3 (66점)
수열의 원소가 모두 0과 1로만 이루어져 있다면, $game(a)$ 의 반환값은 0과 1의 개수가 최대한 비슷할수록 증가한다. 즉, 우리는 $n \times m$ 크기의 격자에서 $nk$ 개의 셀을 골라서 0의 개수와 1의 개수를 최대한 비슷하게 맞춰야 한다. 이는 1의 개수를 $nk/2$ 에 근접하게 맞추는 것이라고 생각할 수 있다.
각 $n$ 개의 행에 대해서, $k$ 개의 원소를 골라서 얻을 수 있는 1의 최소 개수와 최대 개수를 쉽게 계산할 수 있다. 최소 개수를 $min_i$, 최대 개수를 $max_i$ 라고 하면, 그 사이에 있는 개수는 최소 집합에서 0을 빼고 1을 넣는 식으로 모두 얻을 수 있다. 고로 얻을 수 있는 1의 개수는 $[min_i, max_i]$ 와 같이 구간의 형태로 예쁘게 표현된다. 이제
- $\sum max_i < nk/2$ 면 1을 최대한 가져가고
- $\sum min_i > nk/2$ 면 0을 최대한 가져가고
- 아니면 1을 최대한 가져간 다음에 적당히 0으로 대체해서 $nk/2$ 개로 만들어주면
된다.
만점 풀이
53점 풀이에서 사용한 점화식을 써보면 다음과 같다.
$dp[i][j] = max(dp[i-1][j-x] - \sum_{j=1}^{k-x} a[i][j] + \sum_{j=m-x+1}^{m} a[i][j])$
이 때, 모든 셀에 대해서 가장 작은 $nk$ 개를 이미 가져갔다고 하면, 어떠한 셀을 가져가지 않았을 때 돈을 주는 게 아니라, 어떠한 셀을 가져갔을 때 돈을 준다고 생각할 수 있다. 그래서 DP를 한다면
$dp[i][j] = max(dp[i-1][j-x] + \sum_{j=k-x+1}^{k} a[i][j] + \sum_{j=m-x+1}^{m} a[i][j])$
를 구하고 $\sum_{i = 1}^{n} \sum_{j = 1}^{k} a[i][j]$ 를 $dp[n][nk/2]$ 에서 빼 주면 된다. 식을 약간 더 이쁘게 쓰면
$dp[i][j] = max(dp[i-1][j-x] + \sum_{j=1}^{x} (a[i][k+1-j] + a[i][m+1-j]))$
$f(i, j) = a[i][k+1][j] + a[i][m+1-j]$ 라고 정의하자. $f(i, j) \geq f(i, j + 1)$ 을 만족한다. 우리의 문제는 $Q[i] = {f(i, 1), f(i, 2), \ldots, f(i, m)}$ 와 같이 정의되는 큐(queue) $Q[1], Q[2], \ldots, Q[n]$ 이 있을 때, 정확히 $nk/2$ 개의 원소를 pop해서 합을 최대화하는 것이다.
여기서 결론부터 말하자면, 뽑을 수 있는 가장 큰 원소를 그리디하게 $nk/2$ 번 뽑으면 된다. 그 이유를 보이는 것은 크게 두 가지 방법으로 해석이 가능하다. 이를 모두 설명해 보겠다.
- Greedy 관점의 접근: 앞에서 뽑는다는 제약 조건을 제거하면, 우리는 이상적으로는 전체 집합에서 $nk/2$ 개의 최댓값을 뽑고 싶을 것이다. 하지만, 큐의 내부 원소가 내림차순으로 정렬되어 있기 때문에, 우리가 뽑고 싶은 원소들을 큐에서 체크하면 이들은 모두 큐의 앞에 체크되어 있을 것이다. 고로 우리가 원하는 상황을 실제로 이룰 수 있다.
- DP 관점의 접근: $f(i, j)$ 의 부분합은 위로 볼록하다. Slope trick을 사용하자. $dp[i]$ 배열은 $dp[i-1]$ 함수과 $f(i, *)$ 의 부분합 함수의 max-plus이다. 고로 $dp[n]$ 배열은 $f(1, *), f(2, *), \ldots f(n, *)$ 함수 각각의 부분합의 max-plus이다. 이는 Minkowski sum을 취하는 것과 동일하니, 모든 가능한 $f(i, j)$ 값을 모은 후, 크기가 감소하는 순으로 정렬하고, 맨 앞 $i$ 개를 고르는 것으로 $dp[n][i]$ 배열을 계산할 수 있다.
이렇게 전체 문제가 $O(nm \log (nm))$ 에 해결이 된다. 여담으로 정렬을 카운팅 소트로 대체하고 quick-select를 쓰는 식으로 이 문제는 $O(nm)$ 에도 해결할 수 있다. 그다지 흥미로운 최적화는 아니다.
Problem 4. 비스킷 담기
Problem
안티 콩에게는 $k$ 종류의 비스킷이 있다. 이 중 $i$ 번 종류 ($0 \le i \le k - 1$) 의 비스킷은 맛이 $2^i$ 이고, 그 개수가 $A[i]$ 개 이다. ($0 \le A[i] \le 10^{18}$).
안티 콩은 $x$ 명이 참가하는 대회에 이 비스킷들을 나눠주려고 한다. 이 때 $x$ 명이 먹는 비스킷의 맛의 합은 동일해야 한다. 모든 비스킷을 사용할 필요는 없으며, 비스킷을 아예 안 줘도 된다. 맛의 합을 $y$ 라고 했을 때, 가능한 서로 다른 $y$ 의 개수를 세어라. 모든 비스킷의 맛의 합은 $10^{18}$ 을 넘지 않는다.
Solution
일반적인 OI-style과는 약간 거리가 있는 수학 문제 타입의 문제이다. 사실 $2^i$ 의 맛을 가진 비스킷으로 냅색을 하는 문제는 몇 번 대회에 나온 적이 있기 때문에 (NEERC 2012 Exact Measurement) , 상당히 전형적인 스타일의 문제로 보인다. 이런 점을 빼면 문제 자체로는 흥미로운 편이다.
Subtask 1 (9점)
총 맛의 합이 $10^5$ 를 넘지 않기 때문에, 모든 가능한 $y$ 에 대해 Brute-force를 시도해 볼 수 있다. 고로 $x$ 명의 사람에게 $y$ 만큼의 비스킷을 나눠주는 packing이 가능한 지를 살펴야한다. 어떠한 값 $2^i$ 를 큰 비스킷 하나를 사용해서 채운 경우와, 작은 비스킷 여러개를 사용해서 채운 경우를 비교해 보자. 큰 비스킷을 사용해서 채우는 것은 작은 것으로 대체할 수 있으나, 작은 비스킷이 여러 사람을 채우고 있으면 이를 큰 비스킷으로 대체하는 것은 불가능하다. 고로 그리디하게, 큰 비스킷부터 채우는 것이 이득이다.
결론적으로, 큰 비스킷부터 서대로 $x$ 명의 사람들에게 최대한 많이 나눠주고, 이후 모두 $y$ 를 채웠는지 보면 된다. 한 종류의 비스킷을 나눠줄 때, 누구한테 몰아서 나눠주던 최대한 공평하게 나눠주던 상관이 없으니, 정말 아무렇게나 나눠줘도 된다. 그리디의 시간 복잡도는 $O(kx)$ 정도일 것이고, 가능한 $y$ 의 개수가 $\frac{10^5}{x}$ 이니, 곱하면 $O(10^5 \times k)$ 가 된다. 이는 10번 실행해도 시간 제한에 문제가 없다.
Subtask 2 (21점)
이제 편의상 $N = 60$ 이라고 표현한다. ($k$ 라고 쓰지 않는 이유는, 둘이 조금 다르기 때문이다. 정확히는 $\log (\sum_{i=0}^{k-1} 2^i \times A[i]))$ 이다.)
$x = 1$ 인 경우로, 여러 명에게 나눠주는 것을 생각할 필요 없이 특정한 맛의 합을 이룰 수 있는 지만 보면 된다.
핵심적인 아이디어는 다음과 같다. 모든 비스킷의 맛이 $2^i$ 꼴이니, $y$ 를 작은 비트부터 차례로 맞춰나가보자. $y$ 의 0번째 비트를 0/1로 채우고, 그에 따라 0번 비스킷을 사용하자. 그 이후 1번째 비트 이상을 채울 때, 0번 종류 비스킷은 항상 2개, 4개, 6개 묶음으로 필요하게 된다. 이것은 1번 종류 비스킷을 1개, 2개, 3개 쓰는 것과 차이가 없고, 고로 0번 종류 비스킷 $X$ 개가 있으면 1번 종류 비스킷 $\lfloor \frac{X}{2} \rfloor$ 개로 바꿔서 생각할 수 있다. 이 논리는 1번 비스킷, 2번 비스킷에도 순서대로 적용할 수 있다.
이를 활용해서 재귀적으로 문제를 해결하자. $f(i, j)$ = ($y$ 의 $i \ldots 59$ 번 비트를 채우는 중이고, 전 단계에서 끌어온 $i$ 번 비스킷이 $j$ 개 있을 때 가능한 $y$ 의 경우의 수) 라고 하자. $i$ 번 비트를 0으로 두면 다음 상태는 $f(i + 1, \lfloor \frac{j + A[i]}{2} \rfloor)$ 이 되고, 1으로 두면 다음 상태는 $f(i + 1, \lfloor \frac{j + A[i] - 1}{2} \rfloor)$ 이 된다 (이 때 물론 $j + A[i] > 0$ 이어야 한다). 고로 간단한 재귀식을 유도할 수 있다.
이를 단순히 재귀함수로 구현하면 각 쿼리당 $O(2^{60})$ 이 소모된다. 하지만 각 상태마다 서로 다른 $j$ 가 많아야 2개 밖에 없음을 보일 수 있다. 자세히 말해서, $i$ 에 대응되는 $j$ 가 두 개일 경우 이는 항상 ${k, k + 1}$ 꼴을 이룬다. 이 경우, 다음 상태에서 가능한 수는 ${\frac{k-1+A[i]]}{2}, \frac{k+A[i]}{2}, \frac{k+1+A[i]}{2}}$ 뿐이고, $\frac{k-1+A[i]}{2} +1 = \frac{k+1+A[i]}{2}$ 이니, 계속 해당 꼴이 유지됨을 알 수 있다. 고로 메모이제이션을 추가해 주면, 상태의 개수가 $O(N)$ 정도가 된다. 고로 문제가 $O(N \log N)$ 에 해결된다.
Subtask 3 (42점)
$x > 1$ 이어도 사실 거의 동일한 풀이가 된다. 여기서는, $i$ 번 비트를 1으로 두면 다음 상태는 $f(i + 1, \lfloor \frac{j + A[i] - x}{2} \rfloor)$ 이 된다 (단 $j + A[i] \geq x$).
이렇게 했을 때 상태의 개수는 $O(Nx)$ 정도가 된다. 현재 상태에서 가능한 $j$ 의 최소와 최대의 차이가 최대 $x$ 로 유지되기 때문이다. 이유는 아까와 동일한 방식으로 보일 수 있는데, $f(i, *)$ 에서 가능한 $j$ 의 최소와 최대의 차이가 $x$ 이하이면, 최소에서 $x$ 를 빼면 차이가 $2x$ 가 되고, 다시 이를 2로 나누면 차이가 $x$ 가 되기 때문이다. 고로 메모이제이션을 하면 된다. 다만 이 경우 약간 효율적으로 구현해야 하는데, $(j, dp(i, j))$ 의 pair를 중복을 감안하여 관리하는 식으로 비재귀적으로 구현하거나, unordered_map 을 사용하는 정도면 괜찮을 것 같다.
만점 풀이
만점 풀이를 얻기 위해서는 위 서브태스크의 관찰을 발전시킨 후 완전히 다른 풀이를 유도해야 한다. 우리가 DP를 계산할 때 $j$에 하는 것은, 무언가를 더하고 2로 나누는 연산의 반복이다. 이 과정에서, $j$ 는 0 이상이 항상 유지되어야 한다. 우리는 이 조건을 만족하는 $y$ 의 개수를 세는 것이니, 이 조건을 다른 식으로 해석해 보자.
$x$ 를 빼는 상황을 고려하지 않았을 때, 위 연산이 음수에 도달하지 않을 조건은, 모든 $0 \le i \le k - 1$ 에 대해 $\sum_{j = 0}^{i}{2^j \times A[j]} \geq 0$ 이다. 이유는, 사실 수학적으로는 다음 상태를 $\lfloor \frac{j + A[i]}{2} \rfloor$ 와 같이 내림해서 구할 필요가 없이 그냥 $\frac{j + A[i]}{2}$ 로 그대로 써도 아무 차이가 없기 때문이다. 이렇게 되면 양변에 $2^{i}$ 를 곱하면 위와 같은 식을 유도할 수 있다.
우리는 각 $A[i]$ 항에서 $x$ 를 빼거나 안 뺄 수 있다. $A[i]$ 에 $x$ 를 빼었다면 $B[i] = 1$, 아니면 $B[i] = 0$ 이라고 하자. 이 경우 $B$ 는 그냥 $y$ 의 이진수 표현이다. 이렇게 하면:
$\sum_{j = 0}^{i} 2^j \times (A[j] - x B[j]) \geq 0$
$\frac{\sum_{j = 0}^{i} (2^j \times A[j])}{x} \geq \sum_{j = 0}^{i} (2^j \times B[j])$
$F[i] = \frac{\sum_{j = 0}^{i} (2^j \times A[j])}{x}$ 라고 정의하면, 우리의 조건은 $\sum_{j = 0}^{i} (2^j \times B[j]) \le F[i]$ 이다. 즉, $y$ 를 이진전개했을 때 suffix가 특정 수 이하여야 한다는 조건들이 있는 것이다.
이제 $y$ 를 큰 자리부터 맞춰 나가자 (작은 자리부터 맞춰 나가던 아까의 접근과 반대이다). $DP[i][j] = i+1$ 번 자리 이후를 모두 맞췄으며, $i$ 번 자리까지의 prefix가 $j$ 이하여야 할 때 올바른 $y$ 의 개수라고 하자. 답은 $DP[N-1][2^N - 1]$ 이 된다. 이 경우, $B[i] = 0$ 일 때 다음 상태 전이는 $DP[i-1][min({j, 2^i - 1, F[i]})]$ 가 되고, $B[i] = 1$ 일 때는 $DP[i-1][min({j - 2^i, 2^i - 1, F[i] - 2^i})] $ 와 같이 된다.
이렇게 될 경우 가능한 상태가 $O(2^N)$ 이 될 것이라고 생각할 수 있지만, 사실은 이보다 많이 작다. 한 $i$ 에 올 수 있는 $j$ 는, $2^{i+1} - 1$ 이거나, 어떠한 $F[j]$ ($j \geq i$) 의 길이 $i+1$ 의 suffix 뿐이다. 고로, 각 $i$ 에 대해서 가능한 $j$ 가 $O(N)$ 개고, 총 상태는 $O(N^2)$ 가 된다. 이제 이 DP를 메모이제이션을 사용한 백트래킹으로 구현하면 unordered_map 을 사용하여 $O(N^2)$ 정도의 시간 복잡도에 구현할 수 있다.
Problem 5. 버섯 세기
Problem
$n$ 개의 버섯이 있다. 각 버섯은 A 종류 거나 B 종류 이며 $0 \ldots n -1$ 까지 순서대로 번호가 붙어 있다. 0번 버섯은 A번 종류임이 보장된다.
당신은 이 $n$ 개의 버섯 중 몇 개의 버섯이 A 종류인지 세어야 한다. 하지만 당신은 버섯의 종류를 직접 알 수 없고, 기계를 사용해서 간접적으로 알아내야 한다. 기계에 당신은 $2$ 개 이상 $n$ 개 이하의 서로 다른 버섯들을 차례대로 넣어야 한다. 기계는 이들을 분석해서, 인접한 버섯 중 종류가 다른 버섯의 개수를 반환한다. 예를 들어, 넣은 버섯의 종류가 $[A, B, B, A]$ 라면, $A-B$ 는 다르고, $B-B$는 같고, $B - A$ 는 다르니, 2가 반환된다. 기계에 넣은 버섯 개수의 총 합은 10만개 이하여야 한다.
기계 사용 횟수 $Q$를 최소화하면서 버섯의 개수를 세자. 모든 서브태스크에 대해 $n \le 20000$이고, 만점을 받기 위해서는 $Q \le 226$ 이어야 한다.
Solution
원래 92.62점이 만점이었다가 대회 전날에 급하게 $Q = 226$ 풀이를 찾고 문제가 바뀌었다고 들었다. :)
$Q = 19999$ (10점)
0번 버섯이 A 종류이니, 기계에 $[0, i]$ 를 넣으면 $i$ 번 버섯의 종류를 바로 알 수 있다. 이를 $1 \ldots n - 1$ 에 대해 반복하면 된다.
$Q = 10000$ (25점)
위 방법을 약간만 개선하면 된다. 기계에 $[i, 0, i + 1]$ 을 넣으면, $i$ 번 버섯과 $i+1$ 버섯 중 B번 버섯인 것의 개수가 반환된다. 이를 $(1, 2), (3, 4), \ldots$ 에 대해서 다 해주자. $n$ 이 짝수면 마지막 원소는 따로 물어봐야 한다.
$Q = 282$ (80.14점)
226이라는 제한을 보면 sqrt decomposition 류의 풀이가 될 것이라고 예상하기 쉽다. 실제로도 $\log $ 근처의 쿼리로 이 문제를 푸는 것은 매우 어려워 보이니, sqrt decomposition에 기반한 풀이를 생각해 보자.
핵심 아이디어는, $A$ 가 $x$ 개 있으면, $x$ 개의 버섯 중 $A$ 종류 버섯의 개수를 알 수 있다는 것이다. 다음과 같은 식으로 배치하면 된다:
AXAXAXAXAXAXAXAY
이 때 $A$ 는 우리가 A 종류임을 확실히 아는 버섯들이고, $X, Y$ 는 우리가 알고 싶은 버섯들이다. 이렇게 되면, 기계의 반환 결과는 2 * ($X$ 에 있는 B 종류 버섯) + ($Y$ 에 있는 B 종류 버섯) 이 된다. 이 결과를 통해서, 우리는 XXXXXY 형태로 넣은 버섯 중 A 종류 버섯의 개수를 계산할 수 있다. 같은 이유로, $B$ 가 $x$ 개 있어도 $x$ 개의 버섯 중 $A$ 종류 버섯의 개수를 알 수 있다. 고로 필요한 것은
- A와 B를 합해서 $2X$ 개 쌓는 것
- $X$ 개 이상인 A 혹은 B를 사용해서, $\frac{N}{X}$ 번 만에 나머지 원소들의 개수를 세는 것
첫 번째 작업은 $X$ 번의 연산으로 가능하다. 2번의 쿼리로 ${0, 1, 2}$ 번 원소 중 무엇이 A이고 무엇이 B인지를 확인하자. 특정 종류의 원소가 2개 이상, 예를 들어 A가 2개 이상 있다면, AxAy 의 형태로 질문을 한다면 결과가 ${0, 1, 2, 3}$ 으로 나오고, 그 결과에 따라서 $x, y$ 의 종류를 알 수 있다. 이러한 방법으로 2개의 원소의 종류를 알 수 있다.
결론적으로 $X + \frac{N}{X}$ 번의 연산이 필요하며, $X = \sqrt N$ 으로 잡으면 282번 정도의 연산이 필요하다. 이 때, $N \le 400$ 이라면 edge case가 발생할 수 있으니, 25점 서브태스크의 방법을 따로 구현하여 쓰는 것이 편하다.
$Q = 245$ (92.62점)
AXAXAXAXAXAXAXAY 와 같은 배치를 쿼리했을 때 개수 말고 얻을 수 있는 정보가 딱 하나 더 있는데, 바로 맨 뒤에 있는 $Y$ 버섯의 종류이다. 고로, $N/X$ 번의 연산 과정에서 A 종류 버섯의 개수를 셀 뿐만 아니라, 세는 틀의 길이를 조금씩 늘려나갈 수 있다.
이렇게 하면 $X$ 를 어떻게 설정해야지 최소 횟수의 쿼리를 얻을 수 있을까? 수식으로도 계산이 가능할 지 모르겠지만, 본인의 경우에는 $N = 20000$ 일 때, 각 $X$ 의 선택마다 필요한 연산의 횟수를 계산하는 프로그램을 따로 작성하고, 횟수를 최소화하는 $X$ 를 구했다. 이 때, $X = 79$ 로 설정하면, $Q = 245$ 가 나온다는 것을 알 수 있다. 이를 구현하면 92.62점이 나온다.
Problem 6. 기지국
Problem
이 문제는 Two steps 타입으로, 기존 IOI에 나왔던 Saveit이나 Last Supper와 유사한 형태의 문제이다.
트리 $T$ 가 있고, 다음과 같은 쿼리를 지원해야 한다.
- 서로 다른 두 정점 $s, t$ 가 주어질 때, $s$ 에서 인접한 정점 중 $t$에 더 가까워지는 정점은 유일하다. 이 정점을 반환하라.
당신은 이 쿼리를 지원하기 위해서 다음과 같은 두 프로그램을 작성해야 한다.
- label 프로그램에는 입력으로 트리 $T$ 가 주어진다. label 프로그램은 $T$ 에 있는 모든 정점들에 대해서 서로 다른 라벨 을 배정해야 한다. 라벨은 $[0, k]$ 사이에 속하는 정수여야 하고, $k$ 는 입력으로 주어진다: 만점을 받기 위해서는 라벨로 적힌 정수의 최댓값을 최소화해야 한다.
- station 프로그램에는 입력으로 두 정점 $s, t$ 의 라벨, 그리고 $s$ 에 인접한 정점들의 라벨이 주어진다. 두 정점의 절대 번호가 아니라, label 프로그램에서 당신이 배정한 라벨이 주어지는 것이다. 이 때 라벨은 모두 오름차순으로 주어진다. 당신은 $t$ 에 더 가까워지는 유일한 정점의 라벨을 반환해야 한다.
Solution
잡다한 서브태스크 (39점)
서브태스크 1-4는 만점 풀이에 도움이 전혀 안 되는 것 같다. 고로 짧게만 언급한다.
- Subtask 1: 선을 따라서 $0, 1, \ldots, n-1$ 을 순서대로 붙여주면, $s < t$ 일 경우 $s+1$, 아니면 $s-1$ 을 반환하면 된다.
- Subtask 2: 트리 형태가 고정되어 있으니, 그냥 $label[i] = i$ 로 두고 station 프로그램에서는 직접 찾아보면 된다.
- Subtask 3: 최대 차수의 정점을 루트로 잡자. (깊이, 루트에서 무슨 서브트리에 속하는지) 쌍을 보내주면 된다. 정수 하나가 아니라 pair를 라벨링하는 것은, 1000*(깊이) + (서브트리 인덱스) 를 적어주면 된다. $k \geq n^2$ 라 괜찮다.
- Subtask 4: 해당 정점의 라벨과, 해당 정점에 인접한 모든 정점과의 거리 리스트를 보내주면 된다. 정점 $v$ 면, $(v, dist(v, 0), dist(v, 1), \ldots, dist(v, n-1))$ 과 같이 보내주면 된다. 적당히 십진수로 인코딩하면 된다.
$k = n^2$ (65.32점)
Interactive 형태가 아니라, 일반적인 상황에서 위 문제를 해결한다고 하자. $s$ 가 $t$ 의 조상 중 하나라면, 결국 $t$ 가 속한 서브트리가 무엇인지를 찾는 문제가 된다. 서브트리에 대한 질문이니, DFS ordering을 동반하면 좋을 것이다. 특히 DFS ordering은 각 정점에 들어간 시간, 그리고 나간 시간만 기록해도 서브트리에 속하는지 여부를 판별할 수 있다. 한정된 정보량을 가진 우리의 상황에 매우 적합하다. 이 글에서는 DFS preorder, DFS ordering에 대해서는 설명하지 않으니 궁금하다면 따로 찾아보자.
label 함수에서는, 트리의 0번 정점을 루트로 한 후, 각 노드에 대해서 $(din[v], dout[v])$ 를 배정해서 주자. ($din[v] \times 1000 + dout[v]$ 를 저장하면 된다.) 이때 $din[v]$ 는 해당 정점에 DFS preorder로 들어간 시간, $dout[v]$ 는 해당 정점에 DFS preorder로 나간 시간이다. 이제 $w$ 가 $v$ 의 서브트리라는 것은 $din[v] \le din[w]$, $dout[w] \le dout[v]$ 라는 두 조건이 성립한다는 것과 동치이다.
이제 각 쿼리에 대해서 $s, t$, 그리고 $s$ 에 인접한 정점의 $(din[v], dout[v])$ 정보를 알 수 있다. 이제 이 정점들에 대해서, 누가 누구의 서브트리에 속하는지를 알 수 있다. 고로
- $s$ 의 서브트리에 $t$ 가 없다면, $s$ 를 서브트리로 가지는 부모 정점을 반환.
- 있다면, $t$ 를 서브트리로 가지는 자식 정점을 찾아 반환.
이렇게 하면 65점을 받는다. $din[v] \le dout[v]$ 라는 점을 활용해 $k = n(n+1)/2$ 로 줄이는 등의 더러운 최적화가 가능하긴 할 텐데 의미가 있는 지는 모르겠다.
$k = n$ (100점)
사실 많은 경우에는 $din[v]$ 나 $dout[v]$ 중 하나만 필요하다. 예를 들어서, $s$ 의 서브트리에 $t$ 가 있어서, 이것이 어느 쪽 서브트리인지를 확인해야 한다고 하자. 이 때 자식에 있는 노드들이 $v_1, v_2, \ldots, v_k$ 라고 할 때, $dout[v_i] + 1 = din[v_{i + 1}]$ 이 만족된다. 즉 시작점만 알아도 보통 끝 점을 알 수 있다는 것이다. 또한, $dout[v_k] = dout[s]$ 이다. 고로 자식 노드들에 대해서 $din[v]$ 를 알고, 자신에 대해서는 $dout[v]$ 만 알면 웬만하면 파악이 된다는 것이다. 대략 비슷한 이유도 반대도 성립한다.
트리는 이분 그래프이다. 트리의 노드들 중에서 짝수 깊이에 있는 노드들에는 $din[v]$, 홀수 깊이에 있는 노드들에게는 $dout[v]$ 를 매겨주자. 이 때 서로 같은 값이 배정될 수 있기 때문에, $dout[v]$를 구해줄 때도 인덱스를 늘려주는 식으로 구현하자. 이렇게 되면 $din[v], dout[v]$ 에 $[0, 2n-1]$ 사이의 서로 다른 값이 배정된다.
이제 이것만으로도 문제에서 물어보는 쿼리에 대답하기 충분함을 보인다. $s$ 의 깊이에 따라서 케이스를 나누자. 편의상, $s$ 의 차수가 2 이상이라고 가정하고 (1이면 그냥 $c[0]$ 을 반환하면 되니 자명하다), $s$ 가 루트가 아니라고 가정하자 (적절한 예외처리를 하면 되고, 사실 위 알고리즘 특성상 딱히 예외처리를 안 하더라도 잘 된다).
- $s$ 가 짝수 깊이에 있다면, 모든 인접한 노드들의 라벨은 $s$ 보다 크다. 또한 라벨이 가장 큰 노드는 부모 노드이다. 각 서브트리의 구간은 $[label[s] + 1, label[c_0]], [label[c_0] + 1, label[c_1]], \ldots$ 와 같다. 이 중 속하는 게 있으면 대응되는 라벨을 반환하고, 아니면 최댓값 (부모) 를 반환한다.
- $s$ 가 홀수 깊이에 있다면, 모든 인접한 노드들의 라벨은 $s$ 보다 작다. 또한 라벨이 가장 작은 노드는 부모 노드이다. 각 서브트리의 구간은 $[label[c_1], label[c_2] - 1], [label[c_2], label[c_3] - 1], \ldots, [label[c_{k-1}], label[s] - 1]$ 와 같다. 이 중 속하는 게 있으면 대응되는 라벨을 반환하고, 아니면 최솟값 (부모) 를 반환한다.
마지막으로, 홀수 깊이에 있는 노드들의 $din[v]$ 나 짝수 깊이에 있는 노드들의 $dout[v]$ 는 아무도 신경쓰지 않기 때문에 방문하면서 기록할 필요도 없고, 인덱스를 늘려줄 필요도 없다. 고로 이 값들을 단순히 무시해주면 $[0, n - 1]$ 사이의 서로 다른 값을 배정하고 문제를 해결할 수 있다.