2022 ICPC Korea regional 본선 후기

11월 18일부터 19일까지 2022 ACM-ICPC 한국 리저널 겸 제 22회 전국 대학생 프로그래밍 경시대회를 치르고 왔습니다!

저는 MunSongSong Eggdrop(문송송 계란탁)팀으로 다른 후배 두 명과 참가했고,(스코어보드 기준)전체 7등, 교내 3등을 기록했습니다.

 

최종 스코어보드는 다음과 같습니다.

 

아래에서는 팀 구성부터 본선 당일까지의 타임라인을 죽 훑어볼 예정입니다.

 

0. 팀 구성

때는 바야흐로 2021년, 복학을 앞두고 있던 저는 ICPC 팀이 있었으면 좋겠다고 생각했습니다.

코드포스 오렌지(Eunha)에 solved 다이아 2를 자랑하지만, 대부분은 수학 문제를 푸는 능력으로 밀어 올린 것에 가깝고, 자료구조 등에는 무척 취약한, 그리고 무엇보다도 2년 휴학을 해서 아는 학교 사람들도 점점 사라지는 상황이라, 솔직히 대회에 나가는 게 쉽지는 않을 것이라 생각했습니다. 기껏해야 대회 직전에나 얼레벌레 팀을 만들어서 출전하지 않을까. 하고 생각하고 있었습니다.

 

그러던 도중, 아마 KAIST 수시 발표가 막 난 뒤였나? 경기과고에서 IOI 국대급 애들로 이루어진 팀이 있는데, 그 중 두명이 우리 학교로 오고, 나머지 한 자리에 혹시 관심 있느냐는 연락을 받았습니다. 수학과라는 이점을 충분히 살려 사실상 조커픽으로 채용된 셈이었네요.

 

나머지 두 명의 팀원은 songC와 mhy908, 각각 IOI 1금1은, APIO은상 및 KOI 2은을 자랑하는 멋진 친구들이었습니다. 그렇게 팀이 시작되었습니다.

 

팀 이름은, 팀에 문씨가 한명, 송씨가 두명이라 문송송 계란탁이라는 드립이 어쩌다 나왔는데, 결국 신청할 때까지 이거다!하는 좋은 이름이 떠오르지 않아서 그대로 팀명이 되었습니다. 여담인데, 스코어보드 개봉할 때 읽어주시는 분이 문송송 계란탁임을 중간부터 캐치하셔서 그대로 읽어서 좀 신기했습니다 ㅋㅋㅋㅋ..

 

1. 팀 연습

팀연습은 mss_eggdrop 계정을 BOJ에 만들어서 진행했습니다. 가끔은 각자 연습을 하기 위해서 개인 계정을 사용하기도 했고 그렇게 계정들로 그룹을 만들어서 연습에 사용했습니다. 첫 연습은 5월? 즈음에 CERC로 했는걸로 기억하는데, 솔직히 그 뒤로 거의 암전되다시피 하다가 9월부터야 다시 연습을 시작했네요.

 

팀연습을 하면서 느꼈던 문제점들은 다음과 같았습니다.

-다들 풀이는 바로바로 나오는데, 문제를 짜다가 안될 때 계속 붙잡고 있는 경우가 허다하다.

-한 문제에서 멘탈이 말리기 시작하면 바로 스노우볼이 굴러간다.

-서로 사용하는 환경이 너무 다르고, 심지어 한 명(=저)은 주 사용 언어조차 다르다.

-결론적으로, 팀웍이 망했다.

 

어쩌면 당연한 결과인게, 저는 경쟁 프로그래밍 대회를 거의 간간이 급조팀으로 UCPC를 나가는 것들만 빼면 3년만에 나가는 것이었고, 다른 두 팀원들은 개인 대회인 IOI/KOI 위주로 연습했어서 대회를 해나가는 전략 자체가 ICPC스타일과는 꽤나 달랐습니다. 그나마 이전 대회 경험이 있는(18ICPC, 19ICPC 등)제가 전반적으로 어떻게 전략을 세워야 하고, 분담을 어떻게 해야 하는지 맞춰가면서 연습을 거듭했습니다.

2. UCPC 2022

팀연습과 실전 대회 경험을 위해서 여름에 우선 UCPC에 출전했습니다. 예선은 전체 15등이라는 그런대로 괜찮은 성적으로 본선에 갔지만 본선에서는 처참히 멸망했습니다. 그 과정에선 역시나 앞서 말한 문제들이 결국 결정적으로 발목을 잡았습니다. 이걸로 액땜했다 치고 ICPC때는 더욱 잘하기로 결심했습니다마는...딱히 그 뒤로도 9월이 되기 전까지는 거의 연습을 안 했네요. ㅠㅠ

3. ICPC 인터넷 예선

인터넷 예선 스코어보드는 다음과 같습니다.

올해는 인터넷 예선에서도 본선에서도 둘다 7등을 했었네요.

예선은 학교에서 치뤘습니다. 초반에는 문제들을 아주 빠른속도로 해치우면서 잠시간 1등을 달리기도 했고, 꽤 오랫동안 높은 순위를 유지했지만 결국 D를 해결하지 못해 7솔브에 머물렀고, 7솔브한 팀들 중에서는 1등을 했습니다.

4. 마침내 본선으로

팀연습들을 거듭하면서 팀의 전략이 대략적으로 잡혔습니다. 대략 저희 팀이 n년 전의 서울대 MolaMola 팀의 완전 하위호환이라는 결과가 나와서, 그 팀의 전략을 상당히 참고했습니다. 그 결과, 본 대회에서 제가 푼 문제는 좀 있지만 키보드에 손도 안 댔습니다. 대부분의 경우, 제가 설명하는 시간을 포함하더라도 제 설명을 듣고 다른 사람이 코드를 짜는 속도가 제가 스스로 짜는 것보다 훨씬 빨랐기 때문입니다.

 

팀원들이 다들 잘하는 것과 못하는 것이 조금 극명하게 나뉘는 편이고, 팀연습들을 거듭하면서 그 특성들을 어떻게 퍼즐을 맞춰 시너지를 얻는가?가 가장 큰 문제였습니다. 쉬운 문제들은 빠른 속도로 해치우고 나머지 두 팀원들이 어려운(solved.ac 기준 플레 상위-다이아 정도)문제들을 탱킹하고 있는 동안, 저는 누군가가 컴퓨터를 오래 잡지 않는지 감시하는 역할+(대부분의 알고리즘을 이해는 하고 있으니까)디버깅 과정에서의 도움+오랜 시간 집요한 관찰을 했을 때 좋은 결과가 나올 만한 문제 고민 정도를 하는 방식으로 진행했습니다. 조금 슬픈 점이라면, 마지막 유형에 해당되는 문제가 ICPC 본선에 거의 없었네요.(내심 작년 Squid Game 같이 제가 아주 강한 유형의 문제가 나오길 바랐습니다.)

 

여하튼 다들 부푼 마음을 품고 서울 리저널을 치르러 서울...아니 고양으로 갔습니다. 교통편이 아주 끔찍했습니다. 특히 킨텍스에서 서울로 돌아갈 때 버스 줄이 언제나 환상적이었습니다. 제발 다시 세종대에서 하거나, 아예 그냥 다시 대전 리저널로 해줬으면 좋겠다는 생각이네요(?)

 

첫날은 예비소집이니 간단하게 환경 테스트를 하고, 팀원들(+팀원들의 고등학교 친구들)과 함께 저녁 먹고 헤어졌고, 드디어 11월 19일 본 대회날이 밝았습니다.

5. 본선 타임라인

본선 날 저희 팀의 타임라인이 어떻게 진행되었는지 간략하게 적어보겠습니다.

 

(0분) 대회가 시작되었습니다. 다른 두명이 뭘 봤는지는 잘 기억이 안나고, 저는 마지막 네 문제를 봤습니다.

 

(6분) I를 보고, 풀만하다는 결과를 내고 곧바로 J를 보러 갔습니다. 무슨 트리가 나와서 트리 dp 정도인가...하고 생각하다가 문제를 슬쩍 읽어보니 정말로 쉬운 문제라는 결론을 냈습니다. 제가 짜진 않았고, 곧바로 SongC에게 풀이 설명을 하고(제출 버튼 어디있는지 헤메다가 로그인 과정에서 비번 틀리고 계속 버벅이다가)제출. 바로 AC.

 

(22분) I도 적당한 dp로 해결이 가능하다는 결론을 냈고, SongC와 함께 풀이를 완성했습니다. 제출 후 바로 AC가 나왔습니다. 나중에 들어보니, 그냥 문자열을 반대로 한 뒤로 LCS의 길이가 얼마인지 체크하는 정도로 쉽게 끝낼 수 있다고 하네요.

 

(4n분?) mhy908이 D의 풀이를 가져왔습니다. 바로 맞았더라면 첫 솔브인 상황. 하지만 WA를 받았고, 이게 수많은 패널티 폭탄으로 이어지는 스노우볼이 됐습니다.

 

(50분) K를 처음 보고 약간 확률론쪽 문제인가 생각을 했는데(하필 대회 전에 본 문제 중에 이런 게 있기도 했고)생각보다 퍼솔이 무지 빨리 나와서 다른 쪽인가 하고 다시 봤더니 쉬운 문제였습니다. 풀이를 대강 만들고, mhy(아마도?)가 제출을 해서 바로 AC.

 

(92분) SongC가 E가 적당히 응용된 다익스트라 문제라 금방 할 수 있다고 컴퓨터를 잡았지만 바로 풀지는 못하고 2번의 WA를 지나 AC.

 

(106분) SongC가 이전에 F를 나한테 던졌었고, 유니온파인드 구현 정도로 끝낼 수 있는 쉬운 문제였기에 풀이를 냈고 구현해서 바로 AC.

 

대강 그렇게 2시간만에 5솔을 했지만, 그 뒤로 한참동안 막혀 있었는데, 대강 상황을 보자면

 

A: 게임 이론 쪽 문제인 건 보자마자 알아챘지만 이상한 조건들이 너무 많이 붙어 있어서 SongC랑 제가 같이 멘붕. 언젠가 풀어야지 하고 밀어 뒀다.

B: 성질을 관측해야 하는 대단한 문제로 보여서 저한테 와있었던 상황. 후에 실제로 제가 제안한 Conjecture는 모두 맞고, 그대로 구현하면 되는 상황이었지만 특정 케이스 처리를 위해서 거치는 마지막 과정을 어떻게 처리할지가 문제였고,(나중에 들은 바로는 재미없는 dp 노가다로 할 수 있다고 합니다.)바로 그런 관찰들이 따라오지는 못했기에 답보

C: 풀이는 바로 나온 기하 문제고, mhy가 시간만 있으면 바로 짤 수 있다고 했지만 그게 너무나도 귀찮은 문제.

D: mhy가 제출하고 틀려서 바로 멘붕 온 문제. 만악의 근원.

G: 수치해석학 삘이 나서 mhy랑 같이 잡아보려고 했다가, 오차가 제곱 오차가 아닌 절댓값 오차라는 사실에 아주 절망하며 던짐. 그 어떤 팀도 G를 풀지 못했던 걸 보면 잡지 않은 게 좋은 선택이었다고 생각한다.

H: 문자열 문제. 다들 던져 놨다. 나중에 들어보니 팀원 모두가 모르는 어떤 테크닉으로 풀린다고 했다. 안 잡는 게 맞았다.

L: 풀이가 늦게 나오지는 않았는데, 여러 예외 상황들을 처리하는 과정에서 꼬인 상황.

 

(159분) mhy가 L 풀이는 한참 전에 냈었지만 예외 상황을 처리하지 못했어서 WA. 어떤 에외가 있는지 찾아냈지만, 그 상황 처리 코드가 이상해서 다시 WA. 그걸 고쳤지만 또 다른 상황에선 잘 되지 않아서 WA. 어쨌건 4번의 WA 끝에 L을 맞았습니다. 이 시점에서 패널티는 이미 걷잡을 수 없이 불어나 있었습니다.

 

(대략 이 사이에서 스코어보드가 닫힘. 스코어보드 닫힌 시점에서 6솔브, 21위. 이대로라면 차비도 못 챙기고 돌아가는 상황.)

 

(223분) 모두가 D를 붙잡고 뇌절을 거듭하는 와중 mhy가 C 기하를 지금 짜겠다 선언. 오목사각형이 포함되는 경우라는 걸 적당히 확인하고, 저랑 같이 풀이 확인하고 아주 타당한 풀이라서 바로 구현 시작. 대강 다이아쯤 되어보이는 기하 문제인데 놀랍게도 30분만에 구현하고 바로 AC.

 

대략 이 즈음에서 1시간이 남아있었고, 저는 B를 포기하고 mhy의 D를 같이 보고 있었고, SongC는 A를 잡고 있었습니다. 다들 스코어보드에서 D가 많이들 풀리는 걸 보고(결과적으로, 1등부터 25등팀까지의 모든 팀이 D를 풀었습니다. D 못풀고 끝났으면 대략 10등 언저리에서 혼자 D 못푼 이상한 팀이 됐겠네요.)우리가 이렇게 헤멜 문제가 아닌데 너무나도 말렸다라는 결론을 내리고 어디서부터 잘못되었는지 근본적으로 따졌습니다. SongC가 세그를 요리조리 쓰는 다른 풀이를 냈지만 그것도 틀린 상태였고, 애초에 문제 해석을 잘못 했다는 결론이 나와서 다시 mhy랑 원래 풀이대로 돌아가다시피 했습니다.

 

(대략 270분?) 7솔브로 대회를 끝낼 위기에 처했지만, 이때즈음 mhy가 각성을 해서 A에서 결정적인 실마리를 찾아내서 SongC가 풀이를 만들게 했고,(처음 상태가 모두 꽉 찬 상태여서 이상한 특이 케이스를 처리할 필요가 없다.)D에 대해서 우리 모두가 놓치고 있던 사실을 하나 발견했습니다. 대략 요약하자면 "뒤에 뭐가 더 붙었는데 전체 결과는 더 줄어드는 경우가 있을 수 있다."란 거였고, 이 부분을 고치기 시작했습니다.

 

이때 즈음엔 SongC가 A 풀이를 만들었고 예제는 통과했지만 제출했을 때 WA가 두번 떠서 코드를 출력해 검사하러 갔습니다.

 

(284분) mhy가 고친 풀이를 제출했고, D가 3번의 WA 끝에 드디어 AC가 나왔습니다.

 

(290분) SongC가 자신의 A 코드에서 잘못된 부분을 찾았고, 바로 고쳐서 AC가 나왔습니다. 이때쯤 다들 완전 환호 질렀던 기억이네요.

 

(297분) 결국 스코어보드 Freeze 이후로 3솔브를 한 팀이 되었고, 이미 이대로여도 충분히 스코어보드 개봉이 재미나겠지만(?)더욱 재미를 주기 위해서 B와 H에 가짜 제출들을 하기로 결정. B WA 2번, H WA 6번을 받았습니다.

 

(300분) 대회가 종료되었습니다.

6. 대회 후

스코어보드 개봉에서 저희 팀은(당연하게도)문제를 계속해서 맞으면서 순위가 쭉쭉 올라갔고, 20등 후반대에서 출발한 순위는 7등까지 올라갔습니다. 대회가 끝난 뒤로는 해봐야 장려정도 나오지 않았을까 하는 분위기였고, 가장 희망적인 예상도 한 8등 9등 언저리였는데, 9솔브를 한 팀이 생각 이상으로 적었어서 패널티가 아주 많음에도 7등으로 여유롭게 동상 수상에 성공했습니다!

 

완전히 만족스럽지는 못했지만, 그래도 어려운 상황까지 말렸다가 마지막에 이것저것 해결하면서 좋은 결과를 낼 수 있어서 정말로 기뻤습니다. 조금 아쉬운 점이라면 결과적으로 제가 B에서 냈던 많은 추측들이 실제로 맞았다는 것과, 제가 수치해석에 조예가 더욱 깊었더라면 G 풀이 실마리정도는 바로 낼 수 있었을텐데 하는 게 있네요. H는 셋 모두 처음 보는 알고리즘을 팀노트에서 베껴서 naive하게 적으면 풀린다고 했는데, 역시 더욱 공부가 필요한 부분입니다.

 

전체 1등은 무려 3년 연속 우승을 달리고 있는 C14H9Cl5팀이, 교내 1등은 작년에 월파 문턱에서 쓴 고배를 마셨던 BabyPenguin 팀이 차지했습니다. 두 팀 모두 진심으로 축하드립니다!

7. 앞으로?

대강 팀원들끼리 밥을 먹으면서 제가 적어도 내년까지는 졸업하지 않을 것이고, 나머지 두 친구들도 올해 새내기라 시간이 많고, 딱히 내년에 카이스트로 들어올만한 사람 중에서 제 자리에 더 적합한 사람이 없다는 결론이 내려져서, 별 일이 없다면 내년에도 이 팀 멤버 그대로 출전하지 않을까 생각합니다. 이런 멋진 팀원들과 1년을 같이 했다는 것만으로도 충분히 기쁜데, 내년에도 또 나가게 된다면 저로서는 영광스럽기 그지 없네요. 그와는 별개로, 팀명이 계속 유지될지는 모르겠습니다. ㅋㅋㅋ...

 

다들 풀이를 내는 실력은 아주 뛰어나지만, 그에 비해서 실제로 코딩하면서 꼬이는 경우가 팀 연습때부터 빈번해서 이걸 바로잡는 훈련을 계속해야 될 것 같습니다. 더불어서 제 강점이 이번에는 충분히 활용되지 못하고 제가 적당히 쉬운 문제들 처리한 정도로 역할을 마쳤는데, 더욱 수학이랑 기하에서 강점을 쌓아 다음에는 더욱 제 몫을 하고 싶습니다.

 

팀원들이 모두들 훌륭하고 욕심도 있어서 내년에도 이 팀원대로 나간다면 더욱 높은 성적과, 조금 더 나가서는 월파도 노려보지 않을까 싶습니다. 제 오랜 꿈인 월드 파이널 진출이 이루어진다면 더없이 기쁠 것 같지만,(아마 제게는 마지막 대회가 될)내년에 성공하지 못하더라도 너무 낙담하지는 않으려고 합니다!

 

무엇보다도, 정말로 훌륭한 팀원들을 만나서 대회 준비와 진행 과정에서 정말로 많은 것들을 배웠습니다. 이 글을 빌어 못난 누나랑 같이 연습한다고 고생한 SongC, mhy908에게 진심으로 고맙다고 전하고 싶습니다.

 

8. 번외: 문제별 간단한 풀이 요약

A: 스프라그-그런디 정리 + 4차원 DP, 마름모를 직사각형으로 변환하기만 잘 하면 된다. BOJ에 거의 같은 문제가 있다.

B: 대회 중에 풀지 못했다. t=2인 경우에는 대강 가능하다는 걸 증명했고, t=1인 경우에서 대강 윗껍질/아랫껍질을 생각해서(WLOG X-monotone)추측으로 나온 강한 조건을 걸고 그 뒤로 어느정도까지 그리는 것이 최소인지는 dp로 잘 찾으면 된다고...는 하더라. 이전 국대 선발에 거의 비슷한 문제가 나왔었다고 들었다.

C: 기하 문제. 오목사각형을 생각해야 함에 주의. 대각선이 될 수 있는 두 점을 먼저 잡고, 왼쪽/오른쪽에서 각각 다른 점을 포함하지 않는 삼각형을 만들고 합치면 된다. 주의할 점은, 볼록사각형은 대각선이 두개라 두번 세어지는데, 오목사각형은 대각선이 한개라 그렇지 않다는 것. 따로 세줘야 한다.

D: 앞에서부터 dp(라고 해도 될지를 모르겠지만)로 구해나가면 된다. 이게 monotone한 수열이라는 추정을 하면 큰일난다.

E: 간선을 정점으로 두고 다익스트라.

F: 합쳐진 구간들을 유니온 파인드로 관리. 이후 직접 돌려보면 된다.

G: 모른다. 감도 안 잡힌다. 뭔가 convex한 함수 잡아서 삼분탐색하면 되나? 싶긴 한데 k개를 어떻게 고를지 의문이다. 분할 정복으로 되려나.

H: 모른다. 아기펭귄 팀은 무슨 팀노트에 있던 어떤 걸 그대로 베껴서 naive하게 제출하면 된다고 했다.

I: 단순 dp로 해도 되고, 뒤집은 문자열과 원래 문자열의 LCS를 구하는 식으로 해도 된다.

J: 괄호 문자열을 앞에서부터 검사하다가 ()가 나오는 순간들마다 트리의 leaf니까 값을 더해주면 된다.

K: LCS같은 느낌으로, 딜러결과/내 한쪽/다른쪽을 가지고 dp

L: 1자로 이어진 경우가 아닌 이상 DFS 해서 깊이 차이가 같은 서로 다른 두 노드 쌍이 있음을 보일 수 있음. 그 쌍들로 삼각형 만들기. 1자로 이어진 경우에도 비슷하게 비둘기집의 원리를 적용시키면 만들 수 있음을 쉽게 보일 수 있다. 데이터가 약했는지, 어떤 팀은 랜덤하게 한 점을 잡는다->삼각형을 찾는다->다른 점을 잡는다->삼각형을 또 찾는다와 같은 방법으로 해서 맞았다고 한다.