올해도 5등해서 은상 받았습니다.

팀

팀 구성

작년에 휴학했던 kyo20111이 복학하면서 자연스럽게 edenooo + jhnah917 + kyo20111 이 함께 뭉쳤습니다. 3명 모두 한국 PS판에서 나름 굵직한 성과를 낸 사람들이기에 이번 대회에 큰 욕심이 있었습니다. 더 나아가서, 이미 3명 모두 월드 파이널 티켓을 한 번씩 딴 상태였고 edenooo는 이번 학기를 마지막으로 졸업하기 때문에, 정말 마지막이라는 생각으로 한 번 더 월드 파이널 진출 티켓을 따기 위해 열심히 준비했습니다.

미적분학이나 정수론~~, 그리고 고등학교 수학~~을 제외하면 PS 대회에서 나오는 대부분의 분야에서 약점이 없는 팀이라고 생각합니다. 3명이 모두 강점이 서로 다른데, 저는 기하 문제와 다양한 사전지식을 활용하는 문제, edenooo는 앳코더 스타일의 조합론 문제와 네트워크 플로우 관련 문제를 잘 해결하고, kyo20111은 수학을 제외한 모든 분야에서 일정하게 강한 모습을 보여줍니다. 기본적으로 세 명 모두 푼 문제 수가 정말 많고, 팀원 개개인이 약한 부분이 있지만 팀원 조합으로 대부분의 약점을 커버할 수 있는 게 가장 큰 장점입니다. 팀원 3명의 코드포스 레이팅만 보면 레드 + 레드 + 오렌지로 별로 강해 보이지 않지만, 각자 못 푸는 문제를 팀원이 풀어준다면 충분히 3레드 팀 이상의 퍼포먼스를 뽑을 수 있는 팀이라고 생각합니다.

한 가지 문제점이라면 월드 파이널(11/12~11/17)과 서울 리저널 대회(11/25) 사이의 간격이 너무 짧고, 두 대회를 서로 다른 팀으로 출전하기 때문에 팀 연습을 할 시간이 많이 없다는 점이었습니다. 3명이 함께 대회에 참가한 적은 없지만, 그래도 2020~21년의 LongestPathToWF(aeren + edenooo + kyo20111)팀과 2022년의 NLP(chansol + edenooo + jhnah917)팀에서 2명이 함께 연습한 경험이 많았고, 지난 몇 년 동안 함께 공부하면서 서로를 잘 알고 있는 팀이라고 생각해서 팀 연습 횟수가 적더라도 별로 걱정되진 않았습니다. 굳이 팀 연습을 하지 않더라도 개인 연습은 그 누구보다 열심히 하는 사람들이기도 하고요.

팀명

팀 대회를 준비할 때 가장 어려운 두 가지는 팀 이름을 정하는 것과 팀노트를 만드는 것이라고 생각합니다. 팀노트는 한번 잘 만들어두면 매번 조금씩 수정해서 사용하면 되지만 팀 이름은 매번 새로 정해야 해서 매년 고통을 받고 있습니다.

UCPC는 별생각 없이 “BOJ 20000 Solve“로 정했습니다. UCPC 본선까지 한 달 정도 남았을 때 팀원 3명이 푼 문제 수의 합이 19600문제 정도밖에 안 된다는 사소한 문제점이 있었는데…

한 달 동안 매일 한 명이 15문제씩 푸는 방법으로 극복해 냈습니다. 사다리 타기, 돌림판 등의 랜덤 추첨을 사용하기도 하고, 제가 매일 하루에 5문제 이상 푼다는 것을 이용해서 하루 동안 문제를 제일 적게 푼 사람이 다음 날 15문제를 푸는 등의 방법도 사용했습니다.

ICPC도 BOJ 20000 Solve라는 이름으로 나가는 것을 생각해 봤지만, 한 번 더 사용하기에는 너무 재미없다는 의견이 나와서 다시 팀명을 고민해야 하는 시간이 돌아왔습니다. ICPC 팀명을 이야기하기 전에 간단한 퀴즈를 하나 내보려고 합니다. 아래 세 가지 중 가장 PS 악귀 같은 행동은 무엇일까요?

매일 5문제씩 2년 동안 풀기
매주 한 문제 이상 5년 4개월 동안 풀기
앳코더 ARC 모든 라운드 버추얼 돌기

어떤 게 가장 PS 악귀 같은 행동인지는 모르겠지만, 저렇게 살고 있는 3명이 한 팀으로 뭉쳤다는 것은 잘 알고 있는 사실입니다. 따라서 PS 악귀 라는 이름으로 ICPC에 참가하게 되었습니다. 영문 이름을 정할 때 ghoul, maniac, devil, restligeist, akgwi, AC-GUI, addict, enslaved 같은 다양한 후보가 있었지만, 다른 것들은 모두 다양한 이유로 기각당하면서 PS akgwi로 최종 결정되었습니다. 기각당한 이유로는 (1) 대문자보다는 소문자가 귀엽게 생겼다, (2) 단어가 너무 어렵다, (3) 악귀에 정확히 대응되는 단어가 없다 같은 것들이 있었습니다.

팀노트

저는 3년째 ICPC 팀에서 팀노트 제작을 담당하고 있습니다. 항상 팀원 3명 중 사전지식을 가장 많이 아는 사람이었고, 저 말고는 팀노트를 보는 사람도 별로 없기 때문입니다. 작년 ICPC 이후로 새로 배운 많은 내용들을 모두 팀노트에 넣고 싶었지만, 이미 지난 몇 년 동안 팀노트에 정말 많은 내용을 넣었기 때문에 이미 25페이지가 모두 채워진 상황이었습니다. 그렇다고 기존에 있던 내용을 뺄 수는 없기 때문에 2열로 되어 있는 문서를 3열로 바꾸고 종이 여백을 모두 없애서 7장 정도의 공간을 만들어냈습니다. 가독성을 희생하면서 얻은 소중한 공간이기 때문에 열심히 코드를 꾹꾹 눌러 담았습니다. 상하좌우 여백은 프린터가 알아서 넣어줄 것이라고 믿었습니다.

ICPC 서울 대회와 월드 파이널은 문제 스타일이 다르므로 팀노트를 서로 다르게 가져가려고 했지만, 따로 작업할 시간이 없어서 결국 한 번에 제작하는 것으로 결정했습니다. 일단 월드 파이널의 이상한 기하 문제를 풀기 위한 2차원 기하 라이브러리를 많이 준비했고, 팀 연습을 진행하면서 본 모르는 알고리즘이나 2번 이상 등장한 테크닉을 모두 팀노트에 넣었습니다. 이 밖에도 이미 공개되어 있는 다른 팀들의 팀노트를 10개 이상 보면서 수학과 3차원 기하, 그리고 절대 안 나올 것 같은 어려운 내용을 제외한 대부분의 내용을 넣었습니다. 참고한 팀노트 목록과 올해 추가한 내용은 다음과 같습니다.

[펼치기 / 접기]

팀노트는 여기에서 확인할 수 있습니다.

UCPC 예선

너무 오래돼서 잘 기억이 안 납니다. kyo20111이 일본 여행 가서 그냥 edenooo와 함께 2인 팀으로 참가하려고 했지만, 다행히 kyo20111이 컴퓨터를 사용할 수 있는 장소를 찾아서 3명이 함께 문제를 풀었습니다. 하지만 컴퓨터를 사용할 수 있는 장소를 구했다고 하더라도 평소 작업 환경과 달라서 그런지 구현하는 것이 편해 보이진 않아서, kyo20111이 풀이를 찾은 문제 중 구현이 복잡한 문제는 제가 풀이를 받아서 구현하는 방식으로 진행했습니다. 올해는 작년에 비해 본선 진출 팀 수가 많이 줄어서 2명으로 참가했으면 본선 진출이 위태롭지 않았을까… 라는 생각도 듭니다.

UCPC 예선은 10~11문제로 구성되어 있고, 가장 쉬운 문제가 항상 A번에 배치되어 있습니다. 따라서 3명 중 구현이 가장 빠른 제가 첫 4문제를 잡고, edenooo가 가운데 1/3, kyo20111이 마지막 1/3을 잡고 시작했습니다.

저는 ABD를 풀고, kyo20111이 예전에 푼 disk convex hull 코드를 받아서 복붙한 다음 코드 10줄 정도 추가해서 C를 풀고, kyo20111이 불러주는 풀이를 그대로 코드로 받아 적어서 H를 풀었습니다. 제가 머리를 비우고 9000바이트 정도 작성하는 동안 다른 팀원들이 머리를 써야 하는 FGIK를 풀어줘서 9솔브 12등으로 마무리했습니다.

대회가 시작하자마자 A를 잡고 빠르게 코딩했지만 몇 초 차이로 first solve를 뺏긴 것이 아쉬웠습니다. H에 4000바이트를 짜고 제출해서 한 번에 맞은 게 기억에 남는데, 코드도 잘 짠 것 같아서 여기에 자랑하려고 합니다. (코드)

UCPC 본선

이것도 너무 오래 돼서 잘 기억이 나지 않을 줄 알았지만… 고작 4달이라는 시간으로는 기억에서 지울 수 없는 대회였나 봅니다.

지금까지는 항상 초반에 빠른 속도로 문제를 풀어서 패널티에서 우위를 점하고 어려운 문제를 고민할 시간을 확보한 다음 중후반에 어떻게든 어려운 문제를 하나 풀어내서 상위권을 확정했었는데, 이번 대회는 대회 첫 1시간 동안 한 문제도 풀지 못했습니다. 3명이 모두 한 문제씩 잡고 구현했지만 3명 모두 틀려서 디버깅하던 게 문제였고, 다행히 60~90분 시점에 막혀 있던 3문제를 모두 풀어서 그 이후로는 잘 진행이 됐습니다.

저는 FHL을 풀고, 다른 팀원들이 5문제를 더 풀어서 8문제 10등으로 마무리했고 4등상을 받았습니다. 초반에 말리지 않았으면 2문제 더 풀 수 있었을 것 같은데… 지금까지 참가했던 팀 대회를 전부 통틀어서 초반에 이렇게 말린 적은 처음인데, 이걸 복구해서 수상까지 간 경험은 이후에 팀 연습이나 대회에서 초반에 조금 주춤하더라도 침착함을 유지할 수 있게 도와준 좋은 도구가 되었습니다. 배운 점이 많은 대회였습니다.

팀 연습 (1)

작년과 재작년에 ICPC에 참가했을 때는 ICPC 예선 전에 단 한 번도 연습을 하지 않았습니다. 첫 번째 팀 연습은 UCPC 예선, 두 번째 팀 연습은 UCPC 본선, 세 번째 팀 연습은 ICPC 예선이라는 말이 괜히 있는 게 아닙니다. 하지만 앞에서도 언급했지만, 올해는 월드 파이널(11/12~11/17)과 서울 리저널 대회(11/25)에 모두 참가해야 했습니다. 두 대회 사이의 간격이 너무 짧아서 귀국하고 시차 적응하자마자 서울 리저널 치러 가야 하는 상황이었고, 월드 파이널 직전에는 월드 파이널 팀으로 연습해야 했기 때문에 리저널 팀으로 연습할 시간이 많지 않았습니다. 따라서 ICPC 예선 전에도 연습을 몇 번 진행했습니다.

예선 전에 진행한 연습 기록은 여기에서 확인할 수 있습니다. 연습을 몇 번 진행하면서 제가 생각했던 것보다 더 강한 팀이라는 것을 깨달았습니다.

ICPC 예선

대회

늘 그랬듯이 한글 문제 3개를 모두 푼 다음에 남은 문제를 적절히 분배하기로 했습니다.

대회가 시작하자마자 문제지를 넘기면서 한글 문제를 찾았고, kyo20111이 C, edenooo가 D, 그리고 제가 G를 잡았습니다. edenooo가 작성한 코드를 윈도우 디펜더가 바이러스로 오인해서 실행 파일을 지워버리는 일이 있었던 것을 제외하면 C와 D는 큰 문제 없이 해결했습니다. 사실 G도 풀이는 빨리 나왔지만 $N \leq 5000$에 TL 0.5초인 게 마음에 걸려서 다른 팀원에게 키보드를 넘기고 잠시 기다렸습니다. 아니나 다를까 다른 팀들이 G에 빨간 기둥을 세우는 것을 보고 $O(N^2 \log N)$은 안 된다고 판단해서 $O(N^2 \log \log N)$ 풀이로 수정해서 작성하고 한 번에 AC를 받았습니다. BOJ에서 10000문제를 풀면서 생긴 똥문제 감지 능력이 빛을 발하는 순간이었습니다. 이렇게 별 탈 없이 첫 30분 동안 한글 문제 3개와 그다음으로 쉬운 K번까지 총 4문제를 풀어서 잠시 스코어보드 맨 위에 이름을 올렸었습니다. 같은 실습실에 있던 다른 팀들이 감탄하던 것이 기억에 남아 있습니다.

그 이후로 저는 반드시 제가 잡아야 할 것처럼 생긴 E를 잡았고, 다른 두 팀원은 AIJ를 적당히 잡고 있었습니다. 사실 E는 대회 전날 팀노트에 추가한 Polygon Union을 그대로 따라서 치면 풀 수 있는 문제였지만, 팀노트 배끼다가 오타를 2번 내서 1시간 정도 날리고, 시계 방향과 반시계 방향을 헷갈려서 시간을 또 버리고, 실수 오차 때문에 WA를 받자마자 키보드를 압수당하고, CLion 경고 무시했다가 클래스 멤버 변수가 아닌 생성자 인자를 수정해 버리는 등의 수난을 겪어서 결국 2시간 24분 정도에 AC를 받았습니다.

using ll = long long;
struct frac{
    ll p, q;
    frac(ll p, ll q) : p(p), q(q) {
        if(q < 0) p = -p, q = -q;
        ll g = __gcd(abs(p), q);
        p /= g; q /= g;
    }
};

문제의 그 코드입니다. 집에서 문제 풀 때는 분자가 양수인 기약 분수로 바꾸는 부분을 void norm() 등의 함수로 빼서 사용하기 때문에 몰랐는데, 이렇게 작성하면 구조체 멤버가 아닌 생성자 인자로 들어온 값을 수정하기 때문에 분모에 음수가 올 수 있습니다. 이것 때문에 분수 대소 비교가 제대로 동작하지 않아서 30분 정도 낭비했습니다.

제가 E에서 고생하는 동안 다행히 팀원들이 A와 I를 풀었고, J도 두 concave function의 max plus convolution을 구하는 파트를 제외한 모든 부분이 완성되어 있어서 제가 10줄 정도 짜고 AC를 받았습니다. 그리고 남은 20분 동안 kyo20111이 F를 열심히 구현했지만 대회가 끝날 때까지 완성하지 못해서 8문제로 마무리했습니다. F는 딱 봐도 스위핑 문제인데 “푼 문제 DB”에 없고 10분 정도 고민해도 풀이가 안 나오길래 어려운 문제인 줄 알고 안 건들였는데, 사실은 어렵지 않은 NYPC 기출 문제였습니다. NYPC 문제들도 풀고 DB에 넣어야 한다는 사실을 깨달았습니다.

3분 차이로 3등했습니다. E에서 한 서로 다른 5가지 실수 중 한 가지만 안 했더라도 이길 수 있었을 텐데… 대회 끝난 이후에도 3일 정도 계속 생각났습니다.

뒷풀이

ICPC 예선 후 회식은 2022~2023년 숭실대학교 컴퓨터학부 문제해결 소모임 SCCC의 유일한(…) 오프라인 행사입니다. 작년에는 회식에 4팀 정도 참가했던 걸로 기억하는데, 올해는 약 50명 정도가 참석해서 무한리필 고깃집 자리 절반 이상을 점거했습니다. 2년 동안 열심히 부원들 가르치고 SCON이랑 소모임 내전으로 PS 영업했던 게 효과가 있는 모양입니다. SCCC에 대한 이야기는 나중에 정리해 보려고 합니다.

팀 연습 (2), 그리고 WF 연기

이스라엘 하마스 전쟁으로 인해 11월에 예정되어 있던 월드 파이널이 연기되었습니다. 덕분에 우리 팀은 그냥 예선 전부터 열심히 연습하고 팀노트를 준비한 팀이 되었습니다.

뭐 아무튼 월드 파이널 팀으로 연습을 안 해도 되니 마음 놓고 리저널 팀으로 연습을 진행했습니다. 5번의 연습을 진행했고, 아직 연습 기록을 정리하진 않았습니다. 날짜와 셋 목록만 적어두고 나중에 수정하겠습니다.

(10/27) 2023-2024 ACM-ICPC Latin American Regional Programming Contest (링크)
(10/29) The 2021 ICPC Asia Macau Regional Contest (링크)
(11/06) 2021-2022 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2021) (링크)
(11/20) 2023 China Collegiate Programming Contest (CCPC) Guilin Onsite (The 2nd Universal Cup. Stage 8: Guilin) (링크)
(11/22) 2020-2021 ICPC Central Europe Regional Contest (CERC 20) (링크)

시간을 다 안 채우고 중간에 그만둔 Macau Regional Contest를 제외하면 모두 만족할만 한 결과가 나왔습니다.

ICPC 본선

대회 전

작년 목표는 14등 안에 들어서 수상하는 것과 고려대/한양대를 이기고 대학 3등을 차지해서 월드 파이널 티켓을 따는 것이었습니다. 하지만 올해부터는 리저널 챔피언이 아니면 아시아 태평양 지역 플레이오프를 통해 월드 파이널에 진출하는 것으로 규정이 바뀌었습니다. 따라서 리저널 대회가 작년만큼 중요하지는 않았지만, 그래도 고려대와 한양대에게 지면 기분이 안 좋으므로 작년과 같이 한국 대학 중에 3등하는 것을 목표로 잡았습니다.

대학 3등이 아닌 한국 대학 3등이 목표인 이유는, 팀 연습 때 단 한 번도 이기지 못했던 누텔라 + 레드 + 레드 조합의 National Taiwan University std_abs 팀(링크) 때문에 그렇습니다. 해외 팀이 한 팀 있다는 소식을 듣고 어떤 팀인지 궁금해서 확인했는데 std_abs 인 것을 보고 절망했었습니다… 한국 대학 2등은 많이 어려울 것이라고 예상했는데, 서울대의 NewTrend, Cafe Garage, Minors와 KAIST의 Penguins, MunSongSong Eggdrop, Final Round, Kim and Jang, IOS를 전부 이기는 것은 불가능하다고 생각했기 때문입니다.

대회

작년 본선은 아직도 매 순간순간이 기억나는데 올해는 그렇지 않습니다. 사실 5시간이 다 지나서 대회가 끝났을 때도 그냥 팀 연습이 끝난 느낌이었지, 작년처럼 긴장이 탁 풀리는 느낌이 들거나 감격스럽지 않았습니다. 그냥 “어? 끝났네” 정도의 생각만 들었습니다. 이유는 잘 모르겠습니다. 올해부터는 리저널 챔피언이 아니면 월드 파이널 직행이 아니라서 그런 건지, 아니면 서울대 카이스트를 제외하면 무조건 이길 수 있다는 자신감이 있어서 긴장이 안 됐던 건지… 그래서 작년에 비해 쓸 내용이 많이 없습니다.

작년에는 대회장 초기 세팅 그대로 모니터를 책상 가운데에 두고 쓰는 팀이 많았는데, 올해는 오른쪽으로 옮겨서 쓰는 팀이 많았던 것이 가장 인상 깊었습니다. 작년에 쓴 후기(링크)와 올해 5월에 작성한 ICPC 준비 가이드(링크)가 많이 퍼진 덕분일까요? 비슷한 이유로 추정되는데, 올해는 대회장 앞에 배치되어 있는 풍선의 개수가 작년에 비해 많이 균등해 보였습니다. 괜히 떠들고 다녔나…

자리 배치가 참 인상적이었는데, 대회장 맨 뒤에 예선 1등(Cafe Garage), 2등(Final Round), 3등(PS akgwi)가 일렬로 붙어있었습니다. 위에 적은 서울대/카이스트 팀들 중 문송송계란탁을 제외하면 전부 가까운 위치에 있어서 대회장 분위기를 관찰하기 편했습니다.

저는 가장 쉬운 문제 중 하나인 D를 풀고, kyo20111이 짜고 틀린 J를 고쳐서 AC를 받고, 그 이후로는 쭉 E를 잡고 있었지만 결국 문제를 풀지 못한 채로 대회를 마무리했습니다. C와 K를 읽자마자 어려울 것이라고 유추하고 뒤로 미뤘는데, C는 팀원들에게 미리 보여주는 게 좋았나… 라는 생각도 듭니다.

결과 발표

대회가 종료됐을 때 프리즈된 스코어보드 상에서는 4등이었고, 프리즈 이후에 문제를 더 풀어서 우리 팀 위로 올라올 가능성이 있는 팀은 Cafe Garage, Final Round, MunSongSong 정도였습니다. 대회가 끝나자마자 양옆에 있는 팀들의 화면을 슬쩍 훑어본 결과 오른쪽 자리에 있던 Cafe Garage와 왼쪽 자리에 있던 Final Round는 우리 팀보다 등수가 낮았습니다. MunSongSong은 자리가 멀어서 염탐을 못하고 후원사 세션 시작 전에 물어봤는데, 프리즈 이후에 문제를 풀어서 총 9문제로 우리 팀보다 등수가 높다는 것을 알아냈습니다.

스코어보드 오픈 전부터 이미 5등이라는 것을 알고 있었기 때문에 작년과 마찬가지로 긴장감 없이 구경했습니다. 대신 다른 팀들의 등수가 공개되는 것을 재미있게 봤는데, 개인적으로 좋은 성적을 거둘 것이라 기대하고 있던 대학이 몇 개 있었는데 그중 몇몇 대학은 수상하지 못해 아쉬웠습니다. 그래도 유학생으로 구성된 유니스트, 팀원 2명이 교체되었지만 여전히 강한 포스텍, 그리고 고등학교 후배 2명이 있으면서 UCPC와 ICPC 예선에서 멋진 퍼포먼스를 보여주었던 한양대가 15등 안에 들어서 수상했습니다. 모두 축하합니다!

마무리

아직 아시아 태평양 플레이오프가 남아있어서 그런지 작년과 다르게 대회가 끝났다는 생각이 들지 않습니다. 내년 3월까지 또 열심히 공부해서 월드 파이널 진출권 2번 따고 명예롭게 ICPC에서 은퇴하고 싶습니다. 월드 파이널 메달은 어… 잘 모르겠습니다.

응원해 주신 분들, 그리고 축하해 주신 분들 모두 감사드립니다. 내년에 플레이오프 후기와 월드 파이널 후기로 돌아오겠습니다.

참고 링크

2023 ICPC Asia Seoul Regional Contest 후기

댓글