IOI 2020 Day 1

IOI 2020 Day 1 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다.

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

• 최은수, 100 / 100 / 100, 300점, 1등 - 7등
• 송준혁, 75 / 100 / 100, 275점, 8등 - 13등
• 반딧불, 32 / 100 / 53, 185점, 61등 - 63등
• 임성재, 44 / 100 / 41, 185점, 61등 - 63등

특기할 점은 한국 학생들의 성적이 상당히 우수하다는 것이다. 최은수 학생은 300점 만점이라는 아주 훌륭한 성적으로 대회를 마무리하였고, 송준혁 학생 역시 275점으로 그에 버금가는 수준이다. 반딧불, 임성재 학생 역시 60등으로 준수한 성적이며, Day 2 때 성적이 좋으면 금메달을 따는 데도 지장이 없을 것 같다. 한국 팀이 이만큼 우수한 성적을 받은 적은 최근 거의 없었다 (2015년 정도). Day 2 대회도 무탈하게 마무리한다면 기록적인 결과를 낼 수 있는 해가 될 것 같다.

이번 IOI에는 만점을 받은 학생이 총 7명으로, 예년에 비해서는 약간 쉬운 편에 속하는 것으로 보인다. Day 1 만점자는 중국 4명, 한국 1명, 미국 1명, 홍콩 1명으로, 중국 팀의 성적이 아주 많이 우수해 보인다. 이 중 가장 빠르게 만점을 얻은 참가자는 중국의 Zhou Yuyang (Codeforces: WZYYN) 으로, 문제를 전부 해결하는데 2시간 20분이 걸렸다. 한국의 최은수 학생도 문제를 전부 해결하는데 4시간 6분이 걸려서, 상당히 빠른 편이다. 축하합니다!

Day 1 Problems PDF

day1-notice-ISC.pdf

0.14MB

day1-plants-ISC.pdf

0.36MB

day1-supertrees-ISC.pdf

0.38MB

day1-tickets-ISC.pdf

0.43MB

day1-notice-ko_KR.pdf

0.18MB

day1-plants-ko_KR.pdf

0.39MB

day1-supertrees-ko_KR.pdf

0.42MB

day1-tickets-ko_KR.pdf

0.47MB

구현한 코드는 (만약 존재한다면) https://github.com/koosaga/olympiad/tree/master/IOI 에 모두 올라와 있다.

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)$ 에도 해결할 수 있다. 그다지 흥미로운 최적화는 아니다.