APIO 2020 후기

내가 치르게 되는 마지막 APIO는 코로나19의 영향으로 인해 집에서 치르게 되었다. 이틀 동안 대회를 열어 두고, 각 나라의 참가자들이 자신이 원하는 시간에 참가 버튼을 누르면 5시간 타이머가 켜지고 5시간 동안 3문제를 푸는 대회를 치르는 timeframe 방식으로 진행되었다. 대회가 끝나도 각 문제에 대한 답안 제출 시각을 확인할 수 있어서, 이걸 보면서 타임라인별로 내 생각과 문제에 대한 내용을 정리해보려고 한다. 문제는 여기서 확인할 수 있다.

 

A. 벽 칠하기

B. 자매 도시

C. 즐거운 행로

~43:55

대회를 시작하기 전에, 나는 다음과 같은 전략들을 세우고 지키려고 노력했다.

 

1. 대회가 시작하면 모든 문제를 정독하기

2. 구현 시간을 제외했을 때, 모든 문제를 1시간 이상 고민하기

3. 부분점수라도 빨리 받아야 한다는 압박감에 시달리지 않고 문제 자체에 집중하는 시간을 늘리기

그래서 먼저 침착하게 모든 문제를 읽었다. A번 지문이 좀 이해하기 힘들게 적혀 있었고, 영어 버전을 봐도 마찬가지인 것 같았다. 그래서 가장 쉬워 보이는 서브태스크를 먼저 풀어서 문제에 대한 직관을 얻어 보기로 했다. 서브태스크 1을 ($f(k) \le 1$) 만족하는 예제가 문제에 주어져 있지 않아서, 예제를 하나 만들어서 종이에 끄적이면서 고민해 봤다. 지령의 파라미터인 x와 y를 축으로 잡아서 좌표평면을 만들고, x축의 끝을 원점으로 붙여서 좌표평면을 원통으로 만든 다음 i번째 구간을 칠할 수 있는 (x, y)를 원통에 표시해 보면 원통에 대각선 모양이 있는 형태가 나온다. 대각선이 겹치는 형태를 생각해 보면, 결국 대각선을 연장한 직선의 x절편을 기준으로 서로 독립임을 알 수 있다. 그래서 x절편을 각각 구하고, 각각의 x절편에서 문제를 따로 해결하고 답을 합치면 된다는 결론이 나왔다. 이걸 구현해서 제출했지만, 0점이 나왔다.

~1:25:14

A가 왜 틀리는지 잘 모르겠어서, 다른 문제를 좀 고민해보고 오기로 했다. 그래서 B번을 잡았다. 주어진 그래프 $G$에서 두 정점을 잇는 경로에 속한 간선의 가중치의 최댓값을 최소화하는 문제는 $G$의 Minimum Spanning Tree $T$를 구한 다음 $T$에서 문제를 해결해도 충분하다. $T$에 속하지 않는 간선 $E$를 사용한다고 가정하면, $T$ 상에서 $E$가 연결하는 두 정점을 잇는 $T$ 상의 유일한 경로를 $E$ 대신 이용하면 무조건 이득이 되기 때문이다. 다만 B에서는, 두 자동차가 만나지 않으면서 서로의 도시로 이동해야 하기 때문에, 두 정점을 잇는 경로를 제외하고도 추가적인 정점들을 방문해야 하기 때문에, 그 점에 대해서 고민해 봐야 한다.

그러면 어떤 정점들을 더 방문해야 할까? 몇 가지 케이스들을 생각해 보면, 다음의 두 가지 경우에 두 자동차가 위치를 교환할 수 있음을 알 수 있다.

 

1. degree가 3 이상인 정점 $x$를 방문한 뒤, 왔다갔다하면서 위치를 교환하기
2. $y$를 포함하는 사이클이 존재하는 정점 $y$를 방문한 뒤, 그 중 가중치의 최댓값이 가장 작은 사이클을 돌면서 위치를 교환하기

이 두 가지 케이스들을 처리하면서 문제를 해결하려면, 케이스를 엄청 많이 나누고 더러운 구현도 많이 해야 할 것 같았는데, 간단하게 문제를 해결할 수 있는 방법이 있었다. 가상의 정점 $V$를 만들어서, $V$에 도달하면 두 자동차가 위치를 교환할 수 있다는 의미가 되도록 새로운 그래프 $G\prime$을 만들면 될 것 같았다. 그러면 아직 $G\prime$을 어떻게 구축할지는 모르지만, $G\prime$ 상에서 쿼리로 주어진 정점 쌍 $u, v$와 가상의 정점 $V$를 연결하는 부분그래프의 가중치의 최댓값의 최솟값을 구하면 된다. 그러면 아까와 비슷한 논리를 사용하면 $G\prime$의 Minimum Spanning Tree $T\prime$ 상에서 문제를 해결해도 충분하다는 결론이 나온다. 트리에서 세 정점을 연결하는 부분그래프는 유일하게 정의되고, 이 부분그래프의 가중치의 최댓값을 구하는 것은 경로에 대한 문제로 환원할 수 있다. (그림을 그려보면 직관적이다)

그러면 $G\prime$을 어떻게 만들지가 문제다. 사실 문제를 해결하는 과정에서는 $T\prime$만 있으면 되니, $G\prime$은 굳이 만들지 말고 $T\prime$만 제대로 만들면 된다. 1번 케이스의 경우에는 가중치는 가장 작은 세 개만 중요하니, 그냥 Kruskal을 돌리는 과정에서 degree를 카운팅하다가, degree가 처음으로 3이 된 정점 $x$에 대해서 $x - V$ 간선을 Kruskal에 추가로 시도해주면 된다. 2번 케이스의 경우에는 사이클 중 최댓값을 가지는 간선만큼의 비용이 드는데, 이것도 Kruskal을 돌리다가 $p, q(\neq V)$가 이미 $T\prime$ 상에서 이어진 간선이면, $p-V$ 간선과 $q-V$ 간선을 Kruskal에서 추가로 시도해주면 된다.

이렇게 하면 $T\prime$을 구할 수 있고, 아까 말한 대로 했더니 예제가 나오길래 제출했더니 13점밖에 안 나왔다.

~1:47:56

왜 13점밖에 안 나오는지 고민해보다가, 생각해 보니 $T\prime$만 고려하면 문제가 생길 것 같았다. $T\prime$ 상에서 세 정점이 $u-V-v$ 형태로 연결되어 있으면, 답이 $T$ 상에서 $u-v$ 경로의 가중치의 최댓값보다 작게 나올 수 있을 것 같았다. 이 값은 답보다 무조건 작은데 말이다. 그래서 max(원래 답, $T$ 상에서 $u-v$ 경로의 가중치의 최댓값)으로 고치고 제출했더니, 100점이 나왔다.

~2:08:19

A로 돌아가면 또 말릴 것 같아서, 그냥 C로 바로 넘어갔다. 경로의 길이가 Non-increasing이려면 트리의 지름의 한쪽 끝을 지우고 답에 추가하는 식으로 하면 되겠다는 생각이 들었다. 가장 먼 정점을 $N$번 찾는, 즉 1번 쿼리를 $O(N^2)$번 사용하는 Naive한 풀이를 제출했고, 예상대로 26점을 받을 수 있었다.

~2:29:47

문제를 어떻게 접근할지 답이 잘 안 보여서, 3번 서브태스크부터 보기로 했다. 3번 서브태스크는 $1\le i\le N$을 만족하는 모든 $i$에 대해 놀이기구 $i$와 놀이기구 $\lfloor{i-1\over2}\rfloor$를 연결하는 도로가 있음이 보장되는 서브태스크였다. 즉, 트리의 모양이 고정되어 있어서 $N$을 알면 트리의 모양이 고정되는, 쿼리를 날릴 필요가 없는 서브태스크였다. 나는 처음엔 정점 번호가 섞인 줄 알고 쿼리를 날려야 하는 줄 알았는데, 알고 보니 아니었다. ㅋㅋ

그런데 이 문제는 BOJ 10014 Traveling Saga Problem의 하위호환 문제이고, 이 문제를 풀었다면 복붙으로 해결할 수 있다. 나는 저 문제에 증명을 하지 않은 풀이를 제출해서 Wrong Answer를 받은 기록이 있었는데, 바로 '업솔빙 좀 성실하게 할 걸...'이라는 후회가 밀려왔다. 하위호환 문제니까 틀린 풀이가 맞을 수도 있지 않을까?라는 희망을 가지고 복붙을 시도했지만, 당연하게도 0점을 받았다.

~3:35:03

BOJ 10014의 풀이를 구글링해 보았지만 아무것도 나오지 않았다. 예전 통신교육에 비슷한 문제가 있던 것 같아서 예전 통신교육을 뒤져보았지만 내가 못 찾은건지 원래 없었던 건지 나오지 않았다. 이대로 가면 죽도 밥도 안 될 것 같아서 다시 A로 돌아왔다.

하지만 A 역시 별로 답이 없는 상황이었는데, 처음에 제출해서 0점을 받았던 1번 서브태스크를 푸는 풀이가 아무리 봐도 맞는 풀이였다. Assert문 몇 개를 넣어서 제출을 해 봤지만, 별로 의미 있는 결과는 나오지 않았다. 정말 말도 안 되는 곳에서 실수해서 내가 버그를 못 찾은 걸 수도 있겠다 싶어서, 코드를 모두 지우고 처음부터 짜서 제출해봤지만, 역시 0점이 나왔다.

~4:02:55

알고리즘이 틀린 건가? 종이에 다시 내 풀이를 검토해 봤지만 아무리 봐도 맞는 풀이였다. 올해 선발고사에서도 이렇게 서브태스크를 알 수 없는 이유로 계속 틀려서 말렸었는데, APIO에서도 똑같은 상황이 반복되니 미칠 것 같았다. 1시간이 넘는 시간 동안 아무것도 못했다는 생각이 들어서 점점 압박감만 커졌다.

혹시 문제를 잘못 읽었나? 문제를 처음부터 다시 읽기 시작했다. 그런데... 정말 잘못 읽었었다. 다행이라는 생각이 들면서도 한편으로는 나 자신에게 짜증이 났다. 대회를 시작하기 전에 문제 정독하기 라는 전략을 1번으로 세워 놓고 문제를 제대로 안 읽었다. 알고 보니 한 곳이라도 벽을 못 칠하면 그곳만 무효화되는 게 아니라 지령 전체가 무효화되는 거였다. 에휴... 남은 시간을 보니 1시간 반 정도가 남아 있었다.

정말 다행인 것은 대회 초반에 했던 관찰이 아직 유효하다는 것이었다. '원통의 대각선이 M개 겹쳐 있으면 그 지점의 지령을 내릴 수 있다' 정도로 관찰을 조금 수정했고, 다시 문제를 해결하려고 보니 100점 풀이가 보였다. x절편별로 가능한 지령의 위치를 구하고, 지령을 내릴 수 있는 위치들을 모두 합친 다음, lower_bound로 적절히 풀어 주면 된다. 다행히도 바로 100점을 받았다.

이상한 점은 $\sum f(k)^2\le400,000$이라는 제한이 내 풀이의 시간복잡도랑 별 상관이 없다는 것이다. 내 풀이의 시간복잡도가 대충 $O(N\log N+N \max f(k))$인데, 저 제한 덕분에 $\sqrt{400000}N + N\log N$ 정도로 bound 되긴 한다.

+공식 풀이도 이 복잡도인 것 같다. 왜 제한을 이렇게 준 거지 ㅋㅋ

~4:48:20

다시 C번 서브태스크 3을 내 힘으로 풀어보기로 했다. 완전이진트리니까 센트로이드를 잡고 적당히 서브트리 사이를 왔다갔다하면 되지 않을까?라는 믿음을 가지고 코딩을 시작했다. 0점이 나왔다. 센트로이드가 2개면 두 센트로이드 모두 시도해보는 풀이로 수정했다. 0점이 나왔다. 그런데 로컬에서 grader.cpp로 실험해 보니 $N\le 17$일때까지는 잘 나왔다. 그런데 제출하니까 $N\le 17$일 때도 틀렸다고 나왔다. ???

알고 보니 내가 $\lfloor{i-1\over2}\rfloor$를 $\lfloor{i\over2}\rfloor$로 읽었던 거였다. 또 잘못 읽었다. ㅋㅋㅋ 에휴... 허겁지겁 고치고 제출했더니, 다행히도 점수를 받을 수 있었다. 아마 100점 풀이도 센트로이드를 잡고 적절히 순서를 정하는 방향으로 가면 될 것 같다.

~5:00:00

10분 동안 점수를 더 받을 수 있을지는 모르겠지만 일단 서브태스크 4번을 읽었다. 조건이 정말 복잡하게 쓰여 있었는데, 결론은 아마도 어떤 정점 T를 루트로 했을 때 트리의 높이가 30 이하이고 정점 번호를 중위 순회 순서로 매길 수 있는 정점 T가 존재한다는 것 같았다. 남은 시간이 5분밖에 안 돼서 멍때리다가 대회가 끝났다.

5:00:00~

100 / 100 / 47, 총 247점이라는 성적을 받았다. 뻘짓을 꽤 많이 했는데도 나쁘지 않은 성적을 받은 것 같아서 만족스럽다.

+전체 24등으로 은메달을 받았다. 와~