APIO 2017 후기

지금(13일 토요일 오후 9시 40분) 쓰고 비공개로 설정해놓았다가 내일 풀 예정! 이따가 오후 11시에 코드잼 round 2도 있는데.....ㅠㅠㅠ 피곤해...

대회 시작까지

전날에는 최근 코드포스 문제랑 앳코더 문제, 그리고 친구가 풀고 있던 APIO 2013 문제들 잠깐 보다가 잤다. 재작년에는 내가 APIO를 안 쳤고, 작년에는 아주대에서 봤고 boat에서 말려서 아주 망했던 아픈 기억이 있다. 올해는 국민대학교였다. 정보 관련해서 건국대 서강대 아주대 한림대는 가봤는데 국민대는 처음 가봤어..

APIO는 보통 쉬움-중간-어려움의 박자가 있었던 것 같았고, 그래서 일단 쉬운 문제가 하나 있을 걸로 생각했다. 예를 들면 2016년(한국)의 세트에서는 gap-boat-fireworks, 2012년(일본)의 세트에서는 dispatching-guard-kunai가 각각의 난이도에 해당하는 느낌이었다. 위에서 말한 APIO 2013의 경우에는 문제가 robots, toll, tasksauthor인데, 여기서는 tasks author가 난이도는 크게 어렵지 않은데 시간이 많이 걸리는 스타일이고, robots랑 toll은 둘 다 조금 어려운 편인 것 같다. 둘 다 안 풀어봐서 자세히는 모르겠다.

가상머신 느려

자리에 앉아 세팅을 하려는데 느낌이 좋지 않다. 2월에 있었던 2차 선발고사의 아주대학교 환경과 마찬가지로 이번 APIO 2017의 국민대학교 환경도 가상머신 우분투였던 것이다. 진짜 심각했다.... 속도가 너무 느려서 커서를 움직이는게 눈에 천천히 보이고 타이핑을 하면 0.5초 정도의 딜레이가 있었다. 코드블럭을 켜면 왼쪽 작업표시줄에 아이콘이 흔들리며 나타나는데 애니메이션이 뚝뚝 끊기는 걸 보고 소름이 돋았다. 창 전환, 컴파일, 디버깅... 지금이 2017년인데 이걸 대회 환경 컴퓨터라고 불러줘야 할지 고민이 되는, 모든 작업이 답답하기 그지없는 속도였다. 개인적으로는 4GB 혹은 8GB 정도의 USB를 대량으로 구매해서 다 Live CD로 만들고 USB 부팅을 하는게 오히려 더 빠르지 않을까 싶었다.

아무튼 느린 환경 속에서 대회를 시작하였다. 이 글을 공개로 만들었을 즈음에는 문제도 공개되었을 테니까 APIO 2017 홈페이지에서 직접 보자.

1. rainbow
2. merchant
3. koala

생각의 과정 (스포일러!)

rainbow 문제를 보았다. 영어 이름이 뭐더라... 꿈과 희망이 넘치는 느낌으로 쓰여있었다. 한글 제목도 '무지개나라'여서 번역 잘 했구나 싶었다. 문제 이해는 빠르게 되었다. 주어진 직사각형 영역이 잘리는 걸 관찰해야 하나? 각각의 조각은 영역의 테두리의 일부를 포함하는 것이거나, 테두리를 전혀 포함하지 않는 내륙 모양이겠지 싶었다. 테두리를 포함하는 조각들의 둘레를 보면, 영역의 테두리의 어떤 변으로 들어와서 다른 변으로 나가는 경로에 의해서 잘리는 것 같았다. 테두리에 접하는 점들이랑 그들 사이의 이어진 관계를 보면 되려나? 그러면 내륙쪽은 어떻게 세지? 테두리에 완전히 포함되는(min x, max x, min y, max y가 완전히 포함되는) 컴포넌트의 수를 세어주면 되겠다. 컴포넌트를 세는 건... dual graph로 복잡하게 할 수 있을 것 같다. 근데 그러면 4차원 공간에서의 영역을 세어야 하는거 아닌가? 잘 모르겠다, 다음 문제를 보자.

merchant. 물건을 사고 팔 수가 있고, 가방을 메고 다니는데 가방에는 최대 한 개의 물건만 들어간다. 장사를 잘 해보는 문제구나. 제한이 작은 편이네. 예제의 그림을 그려봐도 물건의 가격을 시각화하기는 불편해서 큰 도움이 되지 않는 것 같다. 사이클을 찾는 거지. 사이클은 굉장히 많이 있으니까 다 확인해 볼 수는 없고. 변을 공유하는 두 사이클을 합쳐서 크기를 키울 수가 있나 싶었지만 단방향이기 때문에 항상 원하는 대로 합쳐지지는 않는다. 혹시 구하게 될 사이클이 단순한가? (즉 같은 정점을 두 번 이상 들리지 않고 처음 점으로 되돌아오나?) 그와 동시에 이 질문도 떠올랐다. 사이클이 단순하지 않으면, 두 번 들르는 부분을 끊어서 사이클을 나누면 둘 중에 하나는 더 효율적일까? (이 질문이 맞다면 최적 사이클은 단순해야 한다) 이 또한 고민해 봤지만 그렇지 않은 경우가 있다. 세 개의 정점이 있을 때 1(A 구입)->2->3(A 판매, B 구입)->2->1(B 판매)라는 사이클이 있으면, 분명 2를 두번 들르고 있지만 이곳을 자르면 1->2->1이나 2->3->2 둘 다 물건 종류가 달라서 아무런 수익을 못 내게 될 수도 있다. 음... 일단 다음 문제로 넘어가자.

koala. 다섯 개의 서로 다른 문제가 있는데, 모두 똑같은 대화 방식(playRound)과 원리를 쓰는데다가 N=100으로 고정되어있네. 대화 방식을 익혀서 원하는 걸 할 수 있도록 해봐야겠다. 작년에 이 자리에 있었던 gap이 쉬웠던 걸 보면 이것도 쉽나보지..? 좀 풀어보자. minimum 구하는 건 이렇게 하면 되네. 근데 엄청 비직관적이다... 게다가 서브태스크 제한이 2회 이하 호출인데 한 번만 해도 되잖아ㅋㅋㅋ 이게 뭐지 maximum 구하는건... 이것저것 고민하면서 헤매었다. 결국 이렇게 했다. 1) 모든 i에 대해 b[i]=1를 적어서 보낸다. 가장 큰 50개에 대해서 r[i]=2가 돌아온다. 2) 가장 큰 50개에 대해서 b[i]=2를 적어서 보낸다. 가장 큰 25개에 대해서 r[i]>b[i]가 돌아온다. 3) 이제 가장 큰 25개(P값이 76부터 100까지), 그 다음으로 큰 25개(51부터 75까지), 나머지 50개(1부터 50까지)를 알고 있다. 가장 큰 25개에 b[i]=3, 그 다음으로 큰 25개에 b[i]=1을 적어서 보낸다. 가장 큰 6개에 대해서 r[i]>b[i]가 돌아온다. 4) 가장 큰 6개에 b[i]=16을 적어서 보내면 가장 큰 것만 r[i]>b[i]를 만족한다. 크기 비교하는거.... 일단 b[0]=b[1]=k, b[2]...b[n-1]=0을 채워서 보냈을 때 0과 1이 r[i]>b[i]의 여부가 다르면, 당연히 둘중에 큰걸 골랐을 테니까 바로 알 수 있겠다. b[0]과 b[1]의 값의 쌍들에 대해서, 각각 판별이 가능한 k를 찾아보았다. k=2, 4, 8을 시도해보면 값이 딱 1과 2일때만 판별이 불가능하다. k=1을 시도해보면 이것도 결국 판별 가능해지지만, 이러면 호출 횟수가 4번이다. k=1, 2, 4로는 값이 클 때가 처리가 안 된다. 적절하게 3개를 골라서 모든 경우를 처리할 수 있는지를 코딩으로 확인해봤으나, 그러한 쌍은 없었다. 어떤 k에 대해서 결과를 확인해보고, r값들을 통해서 더 많은 정보를 얻을 수 있지 않을까 싶었지만 그러면 너무 복잡해 보였다. b의 값을 비대칭적으로 준다든지, 뒤쪽 인덱스에도 값을 채운다든지 하는 생각 또한 해봤으나, 이것도 생각해야 하는 것들이 너무 많고, 위의 방법에 비해 나은 점이 없는 것 같았다. 결국 모르겠어서 다시 merchant로 갔다. 일단 여기까지 해서 부분점수를 받고, 조금 더 고민했다. 뒤의 allValues()도 꽤 어려워보였다.

merchant. 생각해보니까 사이클의 경로는 A->B의 경로와 B->A의 경로를 합친 것이다. 이것들 각각의 효율을 따질 수 있나? 최적의 경로를 찾을 수 있나? 일단 A->B의 경로 중에 가장 짧은 길은 Floyd를 통해서 알 수 있겠다. 그런데 약간 더 돌아가더라도 더 많은 이득을 볼 수 있는 길도 있겠지. 그런데 그러면, A->C->B가 최단경로는 아니지만 더 이득이라면, A->C와 C->B로 나눠서 구할 수 있는거 아니야? 각각의 최적을 구하면 A->B의 최적도 구할 수 있는 거 아니야? 그러면 뭔가 대충 최적의 사이클을 찾는 느낌? 접근?은 알 것 같다. 이제 이걸 답을 구하는 데에 어떻게 적용해야 하지? 약간 파라메트릭의 느낌이 난다. 그러고보니까 효율이 분수 꼴인게, 딱 파라메트릭 적용하기 좋게 생겼다. 효율이 $k$ 이상인 사이클이 있다면, 분모를 넘겨서 처리할 수가 있다. $E/l \ge k$이면 $E-lk \ge 0$이다. 앞서 말한 것처럼 사이클의 각각의 경로 조각들로 쪼개면, $\sum(E_{i}-kl_{i}) \ge 0$ 이다. 경로 조각들에 대해서 $E-kl$의 가중치를 줬을 때, 경로 조각들로 이루어진 양의 사이클이 있는지 확인하는 것이다. 좀 더 유명한 음의 사이클 찾기로 바꾸면, 각각의 경로 조각들에 대해서 $kl-E$의 가중치를 줬을 때, 음의 사이클이 있는지 확인하는 것이다. 그리고 가장 단순한 이득의 경로 '조각'은, A->B까지 최단경로로 가면서, 가능하다면 A에서 어떤 물건을 사서 B에서 그걸 파는 거지. 최적의 사이클은 이러한 경로 조각 여러 개로 이루어져 있을 거구. A에서 B로 갈 때 벌 수 있는 가장 많은 돈은 각각의 상품을 다 돌아도 된다. $N^{2} \cdot K$가 그렇게 크지 않기 때문이다. 즉, 모든 정점쌍 (A, B)에 대해서 A에서 B로 가는 최단 경로의 길이를 Floyd를 통해 구하고, A에서 사고 B에서 팔 때의 최대 이익(없으면 0)은 미리 계산해 놓을 수 있다(이 값은 Floyd같은 걸로 완화시켜주면 안 된다. 경로의 길이도 바뀌어야 하기 때문). 그래서 코드는 별로 길지 않아서, 금방 짜고 제출했다. 사실 제출하고 결과 안 나온 상태에서 화장실 갔다 오려고 했는데(나 없는 동안 결과 딱 나와서 AC면 엄청 멋있을 것 같았다) 손을 들었는데 아무도 안 와서 그냥 앉아서 지켜봤다. 제출했더니 한 번에 AC가 나왔다. 속칭 CMS green을 본게 진짜 얼마만이야... 기분이 엄청 좋아졌다. 생각에 확신이 없다고 하나, 자세히 집고 넘어가지 않은 부분이 있긴 한 것 같았는데 아무튼 맞았으니까 만족. 음의 사이클 판별 방법은, Bellman-Ford에서 $V+1$번 째의 relaxation에서도 relaxation이 일어나거나, $d_{ij}=d_{ii}=\infty$로 가중치를 놓고 플로이드를 돌렸을 때 $d_{ii}<0$인 게 존재하면 음의 사이클이 있는 것이다. 그러고보니까 정수로 답을 구하라는게 딱 파라메트릭을 편하게 하라고 하는 거였던 거네...! 답의 최댓값은, 간선 1짜리 두 개로 이루어진 사이클에서, 각각 1원짜리를 사서 10억원짜리를 파는 게 최댓값인 것 같다. 그냥 넉넉하게 (10억+5) 정도를 잡았다.

koala로 가면 또 말릴 것 같아서, 그대로 다시 rainbow로 올라갔다. 영역의 수... 직사각형 영역을 잡았을 때, 원래 있던 영역들이 적당히 잘릴 것이다. 바깥쪽에서는 이어지는데 안쪽에서는 끊긴 거... 판단하기가 너무 어렵고 엄청 많을 수도 있을텐데. 영역의 수, 인접한 공간으로 이어져 있는 면의 수... 닫혀있는 도형의 수. 변으로 둘러싸인 면의 수. 그 때 정말 기가 막히게 하나의 식이 생각났다.

$$v-e+f=2$$

옛날에 이 식에 대해서 많이 고민한 적이 있었다. 아무리 생각해도 정점의 수라는 것이, 교차하는 것들을 다 세어야 하는건지, 모서리도 끊기는 걸 다 세어야 하는건지, 왜 교차하는 걸 안 세면 안 되는건지, 면은 어떻게 정의되는지, 무한한 배경 평면도 왜 면으로 세어야 하는 건지. 모서리 중간에 갑자기 점이 생기면 $v$가 늘어나지만 모서리도 끊기면서 $e$가 늘어나서 다시 식이 원래대로 되돌아온다. 저 식이 어떻게 그걸 다 판단할 수 있지? 진짜 재밌는 식이라서 많이 고민해봤었다. 수학적 귀납법을 써서 평면 상의 단순 그래프에 대해서 증명할 수 있는데, 이건 별로 마음에 안 들었고 더 아름답고 멋있는 증명이 있지 않을까 생각했었다.

아무튼 저 식을 정확히 쓰면 이렇게 된다.

$$v-e+f=C+1$$

이 때 $C$는 컴포넌트의 수이다.

그래프를 이렇게 생각해보자. 각각의 강이 있는 칸은, 네 개의 꼭짓점과 네 개의 변으로 이루어진 정사각형이다. 이것들이 쭉 이어져있고, 어떤 쿼리의 영역은 어떤 직사각형 테두리이며 우리는 이 테두리를 포함해서 안쪽의 그래프만 생각하자.

$v$의 경우, 꼭짓점의 수는 테두리의 꼭짓점의 수에, 영역의 안쪽에 있는 꼭짓점의 수의 합이다. 직사각형 영역의 안쪽에 있는 점의 수를 세어야 하기 때문에, 꼭짓점에 대한 2D 자료구조가 필요하다.

$e$의 경우, 테두리를 두르고 있는 모서리의 수와, 영역의 안쪽에 있는 모서리(모서리의 한 쪽이 영역의 가장자리에 닿아 있는 경우도 포함)의 수의 합이다. 이 또한 2D 자료구조를 쓰면 편하다. 나는 각각의 모서리에 대해서 그 중점 위치에 점을 찍고, 그러면 좌표가 0.5 단위가 되니까 각 좌표성분을 두 배 해서 2D 자료구조에 넣었다. 물론 영역 질의를 할 때도 이걸 잘 세어주어야 한다.

$f$의 경우, (우리가 구하고자 하는 답) + (배경의 무한 영역) + (강의 수)이다. 각각의 강 셀 또한 하나의 격자칸이고, 주변을 네 모서리가 둘러싸고 있기 때문이다. 영역 안에 있는 강의 수는 또다시 2D 자료구조를 쓸 수 있다. 무한 영역은 한 개 뿐이다.

$C$의 경우, 일단 강의 칸들은 하나의 컴포넌트로 이어져있다. 원래 움직이기를 연속적으로 움직였으니까 전체 덩어리는 하나로 붙어 있고, U자 모양의 일부분이 잘려있더라도 테두리에 붙어버려서 하나의 컴포넌트를 이룰 수밖에 없다. 때문에, 강의 컴포넌트가 쿼리 영역의 컴포넌트와 완전히 떨어져 있는 경우에는 컴포넌트가 두 개, 그렇지 않으면 한 개이다. 강의 컴포넌트가 쿼리 영역과 완전히 떨어져 있는 것과 필요충분조건이, 영역의 가장 바깥쪽 셀에 강이 하나도 없는 것, 즉 강의 셀의 최소·최대 x, y좌표가 쿼리 영역에 대해 부등식을 만족하는 것이라는 것은 쉽게 알 수 있다.

따라서 3개의 2D 자료구조에 점들을 잘 집어넣고, 각각의 자료구조에 영역 질의를 해서 답을 계산하면 가능하다. 2D 자료구조는 역시 머지 소트 트리!

사실 처음에는 약간 다르게 했다. 각각의 셀의 중심을 정점으로, 모서리 인접 관계를 간선으로 본 것이었다. 자꾸 틀리길래, 예제 파일을 서로 다른 일곱 가지의 모호한 경우에 대해 만들어가면서 이런저런 코딩 디테일을 계속 수정했다. 그런데 결국 $R=2$인 케이스만 맞는 것이었다. 이는 뭔가 알고리즘이 고려하지 못하는 심각한 경우가 있다는 뜻이었다. 끝나기 30분쯤 전에 반례를 겨우 찾은 덕에, 셀을 정점이 아닌 정사각형으로 보는 풀이로 바꿀 수 있었다. 이 심각한 경우는 다음과 같은 것이었다.

.ooo
.o.o
..oo
....

이 경우에, 안쪽의 2×2 영역에 질문을 날리면, 대각선 쪽으로는 간선이 그어지지 않기 때문에 틀리게 된다. 이걸 해결하려면 어떻게 할지 생각해보니까 저 둘이 공유하는 하나의 꼭짓점, 그걸 정점으로 보는 수밖에 없는 것이었다. 30분이 남아있었지만, '문제는 고민이 제일 어렵다. 풀이를 확실히 알고 있으면 실제 코딩은 많아야 15-20분밖에 걸리지 않는다.'라는 말을 누군가에게 들었던 걸 떠올리면서 마음을 다잡고 열심히 코딩했다. NSEW를 해석하는 것이라든가 세 개의 서로 다른 2D 자료구조를 써야 하는 부분이 똑같아서 시간을 많이 절약할 수 있었다.

끝나기 10분인가, 5분인가 전쯤에 AC가 나왔다. 진짜 너무 행복했다. 2개나 풀었어! 3문제짜리중에! 생각해보니까 1번은 v-e+f를 떠올릴 수만 있으면 다들 풀었을 것 같고, 2번은 좀 무서워 보이지만 별로 어렵지 않은 문제인 것 같은데. 다들 풀었을라나...? 1번은 v-e+f에 대해서 고민했던 옛 경험이 식과 원리에 대한 명확한 이해와 그래프 설정을 하는 데에 도움이 되었고, 2번은 대회 전에 khsoo와 이야기했던 어떤 내용이 좀 도움이 되었던 걸 생각해보면 꼭 그렇지만은 않을 지도 모르겠다. 다시 3번을 조금 고민해보았는데, 잘 모르겠었다. 조금 있으니 대회가 곧 종료된다는 공지를 하시길래, 그 상황에서 가장 적절한, 유서 깊은 고전명작 Emacs 테트리스를 켰다.

풀이 요약

1.

$(v-e+f=C+1)$과 2D 자료구조를 잘 사용해서 풀 수 있다. 참고로 $f$는 답과, 강이 있는 셀과, 바깥쪽 배경을 포함한다.

2.

답에 대한 (정수) 파라메트릭을 하고, 각각의 정점쌍(경로)에 대해서 $kl-E$를 가중치로 두면, 음수 사이클의 존재 여부가 답에 대한 결정문제가 된다.

3.

• min : 1 00..00
• max : (11...11) -> (11..11 00..00) -> (33..33 11..11 00..00 00..00) -> (16 16 16 16 16 00...00)
• greater: k k 00..00 for k in [1, 2, 4, 8]

후기

주변 친구들 중에는 3번을 푼 친구들도 있어서 대단하다 싶었다. 3번은 풀이가 친구들마다 조금씩 다른(그리고 그럴 만한) 문제였다.

2번은 꼬이고 말리기 쉬운 것 같았다. 1번에서 저 식이 떠오른게 너무 적절했고 핵심적이었다.

APIO 문제들은 시간 넉넉히 잡고 천천히 고민하면서 풀면 어느 정도 풀만한 것들이 생각보다 많이 있는데, 대회를 직접 쳐서 그런지 문제가 많이 어려워보였다. 그래도 풀 수 있는 것들을 풀어서 다행이다.

점수는 100+100+33 = 233.