[mathjax]
ICPC regional 본선으로는 두 번째고, 서울 본선으로는 첫 번째입니다. 아이러니게도 첫 번째 리저널 본선은 2019년 방콕 리저널이었습니다.
2018년에는 제가 1학년이었고, 코드포스 레이팅도 블루였고, 결정적으로 알고리즘 문제해결 자체를 시작한 지 채 1년이 안 되었을 때였기 때문에 그냥 ‘대회가 이렇게 돌아가는 거구나~’를 느끼기 위해 귀여운 새내기 동기들과 같이 나갔었는데요, 겨울에 코드포스로 나름의 하드 트레이닝을 해서 레이팅을 2000까지 끌어올린 뒤 올해는 수상을 목표로 준비하게 되었습니다. 따라서 ICPC를 진지하게 준비해본 건 올해가 처음이었고 예선부터 본선까지의 준비 기록을 한 번 정리해 보려 합니다.
팀 연습
팀 연습이라는 것을 해 본 적이 없는 저였기 때문에 팀원들에게 예전에 어떻게 했냐고 물어봤는데, 기억이 어렴풋했던 것 같습니다. 그래서 제가 어떻게든 진행을 해 봤습니다.
날짜와 장소 정하기
팀 연습은 조금 늦게 시작했던 것 같습니다. 개강하고 나서(적어도 9월에) 3명이 모두 참가할 수 있도록 날짜와 시간을 잡았습니다. 장소는 학회 아니면 PC방, 시간은 매주 2회 오후 7시 반이었습니다.
학회실 못 써서 팀연습하러 PC방에 49시간 충전하는 흑우가 있다 pic.twitter.com/GvQQXkBDSM
— shift* 시프트 (@shiftpsh) September 16, 2019
서강대학교의 경우 컴퓨터공학과 실습실 4곳을 스터디 학회들(ICPC Team, Release, CSPC Lab, CNU)이 각각 관리하는데, 실습실에 수업이 없을 경우에는 컴퓨터공학과 학생들이 자유롭게 사용할 수 있도록 되어 있습니다. 실습실을 학과에서 정해진 개방 시간 이외에 개방하는 것은 학회 자율이기 때문에 저녁 7시 30분에 연습을 시작해 새벽 12시 30분까지 문제를 풀고 에디토리얼까지 보고 집에 갈 수 있는 나름 좋은 환경이었습니다. 다만 실습실에 수업이 있는 날에는 PC방에서 연습을 해야 했는데, 가격도 가격이었지만 시끄러운 환경에서 머리 쓰는 건 나름 고역이었습니다. 뭐 어쩔 수 없었지요.
플랫폼 정하기
연습은 처음엔 Codeforces Gym에서 Virtual contest에 참가하는 방식으로 하다가 언젠가부터 BOJ 그룹의 연습 기능을 이용하게 되었습니다.
Codeforces Gym은 Ghost라는 기능을 제공합니다. 실제 대회의 제출 기록을 스코어보드에 반영한 것인데, 실제로 해당 대회에 참가했다면 순위가 어땠는지를 가늠할 수 있다는 것이 장점인 것 같습니다. 다만 팀 연습 초기에는 제가 셋을 고를 때 너무 쉬운 셋이나 너무 어려운 셋만 골라서 별로 의미가 없었고, 그래서 오히려 스코어보드를 보고 스트레스를 받지 않기 위해 + 쉬운 문제를 빨리 찾아내는 훈련을 하기 위해 BOJ로 옮겼습니다.
BOJ 연습 기능은 정말 간단하기 때문에 딱히 설명할 건 없는 듯 합니다. 연습 시간을 설정하고 문제를 미리 등록해 두면 됩니다. 물론 스코어보드는 그룹 내부 인원이 해당 시간에 연습에 참여한 것밖에 안 나옵니다. 쉬운 문제를 못 찾겠다면 대회 진행 1~2시간 후에 대회 공식 사이트에서 최종 스코어보드를 띄워놓는 식으로 연습했습니다. 좋은 방법은 아니었던 것 같습니다.
셋 고르기
역시 저는 ICPC 리저널에 대한 지식이 전무했기 때문에 처음에는 말 그대로 아무거나 골라 풀었습니다. 첫 두 팀 연습은 ICPC 리저널 셋이 아니었습니다. 첫 번째는 사설 대회였고 두 번째는 KAIST RUN 대회였던 것으로 기억합니다.
뭔가 제가 고른 셋이 전부 엄청 쉽거나 아니면 엄청 어렵다 보니까 이대로는 안 되겠다 싶어서 인터넷에서 여러 글을 찾아봤습니다. 이후로는 koosaga님의 내가 문제풀이를 연습하는 방법에서 ICPC-style 부분을 많이 참고했고, 유럽 리저널 특히 NWERC 위주로 골라 풀었습니다. Subregional은 너무 쉬웠고, regional 위주로 골라 풀었던 게 가장 적절한 난이도였던 것 같습니다. BOJ 슬랙에서 추천받은 셋들도 풀었습니다.
그렇게 대회까지 총 13셋 정도를 풀었습니다. 개인적으로는 봄부터 연습을 시작했더라면 어땠을까 하는 후회도 없지 않습니다.
전략 세우기
혼자 나가는 대회가 아니다 보니 연습을 거듭할수록 누가 어떤 문제를 언제 풀지 스케쥴링하는 것도 상당히 중요하다는 걸 느꼈습니다. ‘분명히 이건 우리가 풀 수 있는 문제였는데 왜 못 풀었지?’ 같은 현상이 연습 중반까지 자주 일어났습니다. 대표적으로
- 풀이는 맞는 거 같은데 자꾸 틀렸던 경우
- 완벽한 풀이를 생각했는데, 다른 팀원이 디버깅을 하느라 시간이 다 가서 코드로 옮기는 것조차 하지 못했던 경우
가 있었습니다.
첫 번째 경우에는 단순한 실수일 가능성이 크기 때문에, 보통 온사이트 대회에서는 코드 인쇄를 신청하고 다른 팀원이 다른 문제를 푸는 게 일반적입니다. 하지만 저는 그런 걸 몰랐고 더군다나 PC방에서는 인쇄가 안 되었기 때문에… PC방 모니터가 크다는 점을 이용해, 왼쪽에서는 다른 팀원이 다른 문제를 풀었고 오른쪽에서는 제 코드를 띄워 놓고 눈으로 디버깅했습니다. 온사이트에서 인쇄가 가능하다는 걸 빨리 알았으면 좋았을 것 같습니다.
두 번째 경우는 스케쥴링의 문제였습니다. 예를 들면 ‘나 E, F, H 풀이 생각났어!’인데 누군가 J를 계속 디버깅을 하는 케이스인 건데, J 때문에 E, F, H에 병목현상이 생겼습니다. 따라서 틀린 솔루션을 디버깅하는 것보다 확실한 솔루션을 짜는 쪽으로 우선순위를 뒀습니다. 그리고 컴퓨터는 한 명만 쓸 수 있기 때문에 최대한 컴퓨터 자리를 공석으로 두지 않도록 했습니다. 이렇게 전략을 짜니 ‘풀 수 있었는데 못 푼 문제’가 많이 줄었습니다.
실패로부터 배우기
마지막으로, 대회가 끝나면 에디토리얼을 꼭 읽었습니다. 우리가 알고 있는 테크닉이었는지, 알고 있었다면 어떤 걸 잘못해서 틀렸는지 분석했고, 모르고 있었다면 이런 테크닉도 있구나 하고 새로운 기술을 알아갔습니다. 모르던 테크닉이나 실수가 많았던 테크닉은 팀노트에 작성했습니다. 정작 대회에서는 팀노트가 필요없었던 것 같습니다만…
연습이 끝나고 풀지 못한 대회 문제들을 풀어보는 걸 업솔빙upsolving이라고 하는데, 에디토리얼을 다 읽고 어디서 틀렸는지 토론하다 보면 새벽 1시가 훨씬 넘었고, 낮에 다시 학교에 와야 했기 때문에 안타깝게도 무리였습니다. 여건이 된다면 이후 연습에서는 업솔빙까지 꼭 해보고 싶었습니다.
예선
예선은 가족같은 분위기의 학교에서 진행했습니다. 무려 학회 실습실. 항상 오던 곳이라 편안하게 칠 수 있을 줄 알았으나 서버 상태가 메롱이어서 편안하게 못쳤습니다. 여하튼.
예선에서는 6문제를 빠르게 풀었습니다.
I. Registration (3분, shiftpsh): 2013년부터 꾸준히 나와 오고 있는 문제입니다. 아이디와 비밀번호를 출력하면 됩니다. 대회 시작 직후에 여기저기서 ‘야 등록 어딨어’ 같은 소리가 들렸던 거 같은데 제출 서버가 맛이 가서 의미가 없었습니다. 다들 등록 제출하느라 이런 거겠지 하고 생각했으나…
B. Balanced String (14분, semteo04): \(2^{\left\lfloor\frac{n+1}{2}\right\rfloor}\)를 계산하는 쉬운 문제였습니다. 쉬운 문제였는데 서버가 맛이 가서 실제로 푼 시각보다 5분쯤 늦게 제출하게 되었습니다.
H. Four Squares (24분, shiftpsh): 라그랑주의 네 제곱수 정리를 풀어본 적이 있어서 금방 짰습니다.
C. Byte Coin (32분, lvalue): 쉬운 그리디여서 금방 짰습니다. 역시 채점 서버 때문에 제출이 몇 분 늦어졌습니다.
L. Two Machines (73분, semteo04): 냅색 DP였습니다. 냅색이라는 건 알았는데 제가 풀이가 갑자기 생각이 안 나서 저는 못 짜겠다고 선언했습니다.
D. Canal (117분, shiftpsh): 제가 고민중이었는데, semteo04가 이분 탐색이라고 하길래 multiset을 믿고 짰습니다. 이 문제는 대회 서버 때문에 대회가 끝나고 나서도 한두시간 동안 채점 결과를 받아보지 못했는데, multiset이 터졌다는 다른 팀의 증언을 듣고 상심하고 여의도 불꽃놀이나 보면서 심신을 안정시키기로 했습니다.
— shift* 시프트 (@shiftpsh) October 5, 2019
서강대에서 서강대교까지는 그렇게 멀지 않기 때문에 학교에서 아무 생각 없이 서강대교까지 걸어가서 불꽃을 혼자 구경했습니다. 서강대교에 도착하기 직전에 채점 결과가 공개되었는데, 이 때 D가 맞았다는 걸 알게 되어 안도했습니다. 프리즈 전에는 9등이었다고 합니다.
Convex hull trick이라는 걸 알고도 못 푼 J가 너무 아쉬웠는데, 팀노트 코드를 베끼려고 보니 팀노트에 적혀 있던 코드가 그냥 특공대 솔루션이었습니다. 이후 본선에는 보완해 들고 갔는데 본선에는 CHT 안 나오더라고요. 너무하네
A가 LR flow인 걸 몰랐던 것도 아쉬웠습니다. 근데 어차피 서버 나가서 코드를 더 짰어도 문제를 더 맞았을 확률은 희박했을 거라고 생각합니다.
빨리감기해서…
본선 전날
본선은 온사이트 대회고, 온사이트 대회에 가면 인터넷에서나 볼 수 있었던 많은 분들을 뵐 수 있기 때문에 전날에는 수다 떠느라 안타깝게도 따로 연습은 못 했습니다.
Team Redshift @ Sogang U
— shift* 시프트 (@shiftpsh) November 8, 2019
+ Team Twitter Heavy Light Decomposition @ Hanyang U
+ Team JonMatTaeng @ POSTECH pic.twitter.com/mZgRwOXlHE
한양대학교의 Twitter HLD 팀, POSTECH의 JonMatTaeng 팀과 함께 대회 전날 저녁식사를 했습니다. 레스토랑 이름이 기억이 안 나는데 꽤 맛있었습니다. 서강대 앞에도 점포 내줘요.
연세대/이화여대 상권에 뭔가 다 몰려 있어서 서강대생들은 뭘 먹거나 뭘 하려면 신촌 쪽으로 내려가야 하는데, 여기도 건대 상권에 거의 다 몰려 있어서 아마도 세종대생들도 건대 쪽으로 내려와야 하는 게 아닐까 하는 생각을 했습니다. 제 생각이 맞다면 서강대와 세종대가 의외로 이런 비슷한 점이 있는 거 같습니다. 서강대가 학교 규모는 훨씬 작지만…
??? pic.twitter.com/aM9qEjXeYQ
— shift* 시프트 (@shiftpsh) November 8, 2019
다음날 대회가 아침에 있어서, 근처 호텔에서 묵었습니다. 가고 싶은 공연이 있었지만 대회 일정 때문에 신청을 못 했는데, 알고보니 묵던 호텔 바로 옆 건물에서 하더랍니다. 나한테 왜 그래
본선
일단 일어나서 초콜릿 도핑을 많이 했습니다. 빼빼로데이 시즌이길래 페레로 로쉐 2+2 행사를 하고 있었는데 사재기해 둘걸 그랬네요…
팀원 중 한 명은 본선대회일에 쳐야 하는 시험 때문에 숙소에 안 오고 학교에서 공부를 하다가 늦잠을 잤습니다. 다행히도 택시아저씨께서 존경스러운 속도로 운송(?)해 주셔서 실격은 면했습니다.
본선에서는 7문제를 풀었습니다. 개인적인 목표가 7문제였는데 달성해서 상당히 기뻤습니다. 추가로 C와 J를 처음으로 풀었습니다.
J. Triangulation (11분, shiftpsh, First to solve): A가 상당히 쉬운 문제였어서 lvalue가 바로 솔루션을 생각해내 구현을 시작했는데, 제가 J를 보다가 그림 하나를 그려보고…
…이게 다른 어떤 문제보다 구현이 훨씬 더 쉬울 거 같아서 인터셉트해 제출했습니다. 아이디어를 빨리 생각해내서 운좋게 퍼스트 솔브를 했습니다. 서버 이슈가 없어서 다행이라고 생각했습니다.
J를 푼 직후 아주 잠시동안 1위였습니다. 스크린샷을 찍어 뒀고 대회가 끝난 뒤 휴대폰으로 컴퓨터 화면을 찍었습니다.
A. Fire on Field (13분, lvalue): 구현하라고 하는 걸 구현하면 되는 쉬운 문제였습니다. 제가 J를 짜려고 인터셉트했을 때 A 코드도 거의 다 짜여져 있던 상태였으므로 바로 제출해 맞았습니다.
L. What’s Mine is Mine (36분, semteo04): 간단한 유형의 DP라서 semteo04가 금방 풀었습니다.
I. Thread Knots (47분, shiftpsh): 그림만 봐도 이분 탐색의 냄새가 나는 문제였습니다. 바로 뚝딱 짰습니다.
B. Gene Tree (103분, semteo04): Tree DP라는 건 알았는데 제곱이 섞여 있어서 식이 괴랄하게 나왔습니다. 제가 식을 열심히 전개하면서 ‘이렇게 분해해서 생각하면 되지 않을까?’ 같은 식의 말을 했더니 semteo04가 뭔가 생각난 듯 열심히 구현했고, 제출해서 맞았습니다.
H. Strike Zone (164분 +2, semteo04): Kadane’s와 세그먼트 트리를 잘 섞으면 되지 않을까 싶어서 일단 제가 짜서 두 번 제출했는데 틀렸습니다. 알고 보니 KOI 2014 중등부의 금광 문제와 똑같은 문제였습니다. lvalue와 저는 정보올림피아드 준비/출전 경험이 없어서 몰랐지만 경험이 있던 semteo04가 제 코드를 버리고 새로 짜 순식간에 맞췄습니다.
C. Islands (204분 +6, lvalue, First to solve): 남은 문제 중에 풀만한 문제가 없어서 lvalue가 잡았는데, 솔직히 왜 맞았는지 아직도 아는 사람이 없습니다. 풀이가 맞는 게 맞는지 아니면 데이터가 약한 건지…
K번 Washer는 뭔가 3차원을 다루는 거 같아서 제가 3차원 벡터 연산하는 코드를 짜고 있었는데, 대회 15분 전에 ‘평면으로 잘라서 \(\binom{100}{3}\times 2^3\) 브루트포싱하면 되지 않을까?’라는 생각이 들어서 그 방향으로 구현했으나 WA를 계속 받았습니다. BOJ에 데이터가 올라온 후 제가 같은 방법으로 다시 구현해서 제출했더니 AC를 받아서 너무 안타까웠습니다. 아마 외적을 잘못 구현했거나 출력 포맷을 잘못 지켰던 것 같습니다…
— shift* 시프트 (@shiftpsh) November 9, 2019
최종 순위는 팀 랭킹 15위, 학교 랭킹 8위였습니다. 서강대학교가 학교 순위가 1자리수였던 건 2015년(6위) 이후 4년만이라 결과는 만족스러웠습니다. 색깔과 닉네임을 붙여서 팀명을 지으면 수상한다는 전설도 지켰습니다(2017년 BlueJoker, 2015년 PurpleNoon).
개인적으로는 제가 푼 게 많지 않아서 + K를 결국 풀지 못해서 조금 아쉽긴 했습니다. 그래도 제가 어시스트를 많이 했으니 괜찮지 않았을까 싶어요 ..?
스코어보드를 시상식 이후에 공개하는 게 아쉬웠습니다. 꼭 이렇게 해야 했나… 그래도 본선대회 운영은 전반적으로 만족스러웠고(특히 CLion이 있었다는 점에서!), 다과와 저녁은 맛있었습니다. 감사합니다.
사실 해외 리저널에 참가비가 있다는 건 방콕 대회 때문에 알았는데, 오히려 우리나라가 특이하게 참가비가 없었던 것이었습니다. 내년부터는 참가비가 생긴다는데, 참가비는 얼마든지 괜찮으니 예선 서버 이슈같은 문제만 되풀이되지 않았으면 좋겠습니다.
당분간 휴학할 예정이라 다음에는 2022년 혹은 2023년 리저널에 참가하게 되지 않을까 싶습니다. 팀명처럼 진짜 레드 만들어 와서 월드 파이널에 꼭 한 번 나가보고 싶네요!
수고하셨습니다. 🎈
너무 대단해요!