ACM-ICPC Jakarta Regional 2018

후기 안 쓰려고 했으나 그냥 간단히 써보려고 한다.

11월 9일 금요일

대전에서 CMP 팀과 함께 인천공항으로 출발했다.

KTX 탈 때마다 홍보하는 광명역 도심공항터미널을 이용해 보았는데, 안내도 잘 안되어 있고 버스비도 비쌌다. 서울역에서 공항철도 타고 가는게 훨씬 더 싸고 편했을 거 같다. 😠

인천공항 게이트 쪽에 일본 사람들이 있었는데 대회 후드인걸 보았을 때 누가 봐도 ICPC를 참가하는 사람들 같았다. 아마 2등한 교토대 팀이었을 것 같다. 하지만 대회 끝날 때까지 말할 기회는 없었다 :(

숙소는 기숙사라서 기대하지 않았는데, 거의 호텔급이어서 놀랐다. 매우 좋았다. 근데 수건이 2개였다. 😠

11월 10일 토요일

단체 사진을 찍고 가이드와 만났다. 한국에 관심이 많은 분이어서 기본적인 한국어는 하실 줄 아셨으나, 의사소통은 조금 힘들어서 영어로 했다.

Opening Ceremony를 아침에 해서 많이 졸렸다. 이것저것 많았는데 잘 기억이 나지 않는다. 스폰서 톡이 아주 솔직하더라는 것만 기억이 난다... 반응이 한국보다 훨씬 좋았다. Technical Review때 대회 시스템 관련 중요한 이야기들이 많이 나왔으나, 나랑 수찬이는 무슨 생각이었는지 전혀 듣지 않았다. 다행이도 나중에 알고 보니 민규가 다 들어줬다. 개이득

Practice Session에는 2017년 리저널 문제 2개와 처음 본 문제 하나가 나왔다. 처음 본 문제의 내용은 다음과 같다.

길이 $N$의 정수 수열이 주어졌을 때, 이 수열의 모든 원소의 최솟값도, 최댓값도, 합도 아닌 음이 아닌 정수를 아무거나 출력하라.

민규가 그냥 puts("13105") 를 냈고 맞았다.

Practice Session은 2시간 정도였는데, 끝날 때까지 못 나가게 해서 안에서 매우 지루했다. 끝나고 숙소에서 낮잠을 잤다.

저녁은 가이드 분이 로컬 푸드로 한상 크게 차려주셨다. 기름종이에 싸여서 우아한 자태를 뽐내고 있는 저 음식들은 굉장히 향이 강하고 끈덕지다. 정확히 민규 취향일 듯. 실제로 싱가폴에 산 적이 있던 민규의 추억을 자극하는 소울 푸드였던 것 같다. 다만 아쉽게도 전체적으로는 호불호가 있었다.

사실 로컬 푸드는 식중독의 위험이 있어서 조심히 먹어야 한다. 난 처음에 신경 안 쓰고 막 집어먹다가 갑자기 그 생각이 나서 그때부터 조심히 먹기 시작했다. 그럼에도 먹은 후 배가 썩 좋지는 않아서 다음날이 걱정됐다.

11월 11일 일요일

오전에 일어나서 대회장으로 갔다. 다들 속이 그렇게 좋지 않았는지 화장실부터 찾았다 (...) 다행이도 그 이후 화장실에 다시 간 사람은 없었다.

초반은 순조롭게 말렸다. 문제 선택도 잘못됐고 코딩도 밀렸던 것 같다. 2문제에서 올라오지 못해서 20등 밖으로 떨어지고 화면에서 사라지기도 했다.

45분에 3번째 문제인 L이 늦게 나오고, 이 즈음부터 대충 틀린 문제들이 정리가 되고 풀이들이 나오기 시작했다. 특히 C에 대해서 재밌는 이야기가 나왔는데, 몇 주 전에 종원이형이 휴가 나오면서 민규한테 알려준 De Bruijn Sequence를 그대로 구하면 된다는 것이었다. De Bruijn Sequence는 우리 팀원들이 거의 처음 들어본 개념이었고 (고로 다른 팀들에게도 낮설 가능성이 아주 컸고) 이해도 하지 않았으나, 우리 팀노트에는 그걸 구하는 코드가 그대로 있었다. 팀노트를 생각 없이 베끼면 AC가 나오는 엄청난 꿀문제가 있었던 것이다.

UCPC 2018처럼 스코어보드에 혼란을 주기 위해서 논의가 끝난 즉시 C를 잡았다. 금방 맞았다. 그 사이에 내가 H에 있던 코딩 미스를 고쳐서 5문제로 올라왔다. 이 때부터 시동이 걸렸다. 그 후 K, J, D가 빠르게 완성되어서 8문제로 올라갔다. 이 때 1등을 탈환했다.

이후 F와 G가 승산이 있어 보여서 이 둘을 잡았다. F는 아이디어가 빨리 나왔으나, 접근에 따라 구현이 헷갈릴 수 있는 문제였고, 그걸 간파하지 못하고 성급하게 코딩해서 (내가 아니라 민규가 ㅎㅎ) 많은 불필요한 WA를 받았다. 누구든간에 이런 일은 있어서는 안된다. G는 $O(n^3)$ 이 될 것 같은데 뭔가 복잡할 것 같았고, 시간 제한이 1초라서 빡빡하지 않을까 싶었다. 약간 복잡하지만 될 거라는 확고한 믿음을 가지고 내가 코딩을 시작했는데, 알고 보니 처음에 불필요한 절차를 고려하고 있었다. 이 절차를 빼니까 매우 간단한 알고리즘이어서 여유롭게 맞았다.

이후 남은 문제가 B와 E였다. 둘 다 상당히 어려운 문제로 보여서 1등하기 위해 꼭 다 풀고 갈 필요는 없겠다고 생각했다. E의 경우에는 바로 보이는 풀이가 없었고, 그건 B도 마찬가지였다. 하지만 트리에 지루한 쿼리를 날리는 것만큼 재밌는 일이 없기 때문에 내가 B를 열심히 시도했다. 그러다 대략의 접근 방식이 나와서 내가 바로 구현을 시작했고, 팀원들이 남은 부분을 검토하기로 했다.

열심히 구현하니 최종적으로 7.2KB정도 나왔다. 좀 돌아간 거 같기도 하지만 뭐 대회니까.. DM도 컴퓨터 빌 때 짜 놓았으나, 예제를 그냥 돌려보았더니 맞아서 냈고, 바로 AC! 진짜 짜릿한 순간이었다.

남은 시간 동안 E를 어떻게 뚫을까 고민했으나 별 생각이 안 나서 그냥 나이브 알고리즘을 구현해 보기로 했다. 아무 의미 없어 보이지만 태국에서 이거 비슷한 방식으로 정말 올솔브를 띄운 적이 있어서 (...) 시도해 보았다. 애석하게도 TLE. ㅠㅠ

그러고도 정말 시간이 남아서 E의 풀이를 고민했다. 확실히 B보다는 아이디어와 구현 모두 쉬운 문제였다. 남은 시간 34분이면 구현을 시도는 해 볼 수 있었을 것 같다. 이번에는 별 상관 없었으나, World Finals 레벨에서는 내가 B 하고 있을 때 풀이가 나와서 같이 구현하고 맞았어야 한다고 생각한다.

대충 난이도를 정리하면:

• easy: I < A < L
• easy-med: H = D < J < F < K = G
  
• med-hard: C
• hard: E < B

최종 스코어보드는 다음과 같았다. K는 난이도에 비해서 상당히 푼 사람이 적었고, 반면에 G와 C는 그 난이도에 비해 푼 사람이 많았다. 알고 보니 C는 그러한 문자열의 존재성을 믿고 랜덤 + Euler tour로 푸는 풀이가 있었고, 그것이 의도된 풀이었던 것 같다. 우리의 알고리즘보다 구현량은 더 많을 것 같으나 생각하기는 조금 더 쉬웠던 것 같다. G는 $O(n^3\log n)$ 이 통과되었다는 후문을 들어보면 데이터가 약한 것으로 보인다. 그게 결과에 얼마나 영향을 줬는지는 모르겠으나..

대회가 모두 끝난 후에는 시상식이 있었다. 맨 처음 시작한 것은 퍼솔 시상식이었다. 퍼솔 시상식은 대회 때 퍼솔이 나온 10문제에 대해서만 진행했는데, 우리 팀이 그 중 4개를 먼저 풀어서 6개의 텀블러와 머그컵을 받았다 😛

그 다음에는 대망의 본 대회 시상식이 시작되었다. 시상하고 스코어보드 까는 모 이상한 ICPC 리저널과는 다르게, 이 리저널은 바로 리졸버를 켰다. 리졸버는 World Finals의 것을 그대로 사용했고 행사도 거의 동일하게 진행했다. 환호가 여기저기서 터져나오는 분위기의 시끄러운 시상식이었다. 한국도 UCPC 시상식때는 아주 시끄러웠는데, ICPC는 그러기 힘들다 :(

시상은 월드 파이널과 비슷하게 금메달 3팀, 은메달 4팀, 동메달 5팀을 수상하고, 인도네시아 탑 12팀에 대해서 따로 시상이 진행되는 식이었다. (인도네시아 내부 수상은 메달 팀은 제외하고 시상했던 것으로 기억한다.) 우리는 프리즈 당시 스코어보드를 보는 것만으로도 1등임을 확정할 수 있는 상황이어서 그냥 재미있게 앉아서 지켜보고 있었던 것 같으나, CMP는 다른 상위권 수상자들의 결과에 따라서 메달 색이 바뀔 수 있어서 그것보다는 흥미진진했을 것이다.

최종적으로 CMP 팀은 4등 (은메달), 우리 팀은 1등 (리저널 챔피언) 으로 대회를 마무리했다. 상품으로는 보조 배터리, 헤드셋, 외장하드, 등등... 액수가 크지 않은 물건들을 여러 개 주는 방향이었다. 갖고 가기는 힘들겠지만 나름대로 왕이 된 기분을 느껴보라고 의도적으로 그렇게 진행하고 있다고 한다 :) 

이후 저녁 식사가 있었으나 일정이 늦어져서 바로 공항으로 달려가야 하는 상황이었다. 저녁 식사는 출장 뷔페가 와서 나름대로 성대하게 차려준 것 같으나 (이건 한국이 더 낫긴 했다.) 그렇게 많이 먹지는 못하고.. 가이드에게 도움을 요청해서 택시 2대를 잡고 출발하였다. 잡고 타는 데 이런저런 문제가 있었으나, 현지 가이드 분들이 정말 성심성의껏 뛰면서 도와주신 덕분에 무사히 탈 수 있었다. 정말 많이 고마웠다. 대회 동안 거의 항상 같이 다녔던 가이드와 작별 인사를 하고, 공항으로 떠나서 한국에 도착했다.

한국에 도착하니까 현지 대회 organizer에게 우승을 축하한다는 코드포스 DM을 받았다. 모 PP 리저널은 organizer가 코드포스 DM으로 "니네 코드에 이거 안넣어서 실수오차로 틀렸음 ㅋㅋ" 라고 보냈다던데 친절한 메시지에 감동을 받아서 잘 답장해 주었다. 마지막 ICPC 리저널 대회를 즐겁게 보내서 좋고, 대회에 애착이 많은 사람들과 함께 할 수 있어서 기뻤다 :)

 

문제 셋은 코드포스 Gym에 올라와 있다. 퀄리티는 무난한 편이고, 재밌는 문제들도 있다. 지금까지 진행된 PP 대회 (한국 / 대만 / 인도네시아 / 태국) 중에서는 문제가 제일 좋은 것 같다. 링크

대회 풀이 역시 상세하게 잘 적혀 있어서, 특별히 내가 풀이 Writeup을 할 필요가 없다고 생각했다.