ICPC 2025 Bangkok Regional/Seoul(Busan) Regional 후기

배경

 

ICPC 2025 Bangkok Regional과 Seoul(Busan) Regional에 참가했다. 기본적인 배경을 말씀드리자면 월파 진출에 대한 기본적인 룰은

대학에서 리저널 우승한 팀이 0팀->아챔

대학에서 리저널 우승한 팀이 1팀->그 팀이 월파

대학에서 리저널 우승한 팀이 2팀 이상->코치교수님이 팀을 선택하거나 APAC에서의 결과로 결정을 미루는 것이 가능(사실 교수님이 한 팀을 선택하는 부담을 질 이유가 없었기에 APAC에서 미루는 것이 정배였다.)

의 방식인데, 리저널 우승이 가장 중요한 팩터인 이상 해외 리저널도 참가하여 최대한 우승기회를 늘리는 것이 중요했다.

그런데 해외 리저널들의 일정을 봤을 때,

대만(11/16) -> std_abs가 너무 강해서 우승이 힘듬

자카르타(11/23) -> 부산리저널이랑 겹침

베트남, 요코하마, 마닐라 -> 시험기간과 매우 겹쳐서 못 감

 

인 상황이라 참가 가능한 리저널이 11/2에 열리는 방콕 리저널뿐이었다. 그래서 방콕 리저널에 참가하기로 결정했고, 이건 서울대의 다른 강팀인 floor_sum한테도 똑같이 적용이 돼서 이 팀도 방콕 리저널에 참가하게 되었다.

그래서 결국, 서울대에서 제일 센 두 팀인 Just use CRT와 floor_sum의 대결로 보았을 때 3판2선 대결을 해서 이기는 팀이 월파를 가는 매우 흥미로운 Bo3 대결이 되어버렸다.

 

준비

 

ICPC 준비 자체를 그렇게 열심히 하지는 않았다. 그것보다는, 2025년 올해가 개인적으로 PS를 열심히 해서 실력에서 스텝업을 한 해였다. 2월~7월 기간에는 1일1버추얼을 돌아서 약 200개의 코포/앳코더/OI 버추얼을 돌기도 했고, 백준에서 다이아도 많이 풀었다. 이렇게 PS를 열심히 할 수 있었던 이유는, https://qwerasdfzxcl.tistory.com/44 에 가서 PS 잘한다는 이유로 여기 가서 극진한 대접을 받아보니 그냥 기분이 좋아져서(...) PS 더 잘하고 싶어서 열심히 했다. 너무 단순한 사고방식이다. 기분좋아져서 열심히 했다는 매우 단순한 방식이었던만큼 즐기면서 했다. 다만 약간 역설적인 건, ICPC가 다가올수록 연습량이 줄었다. 이건 그냥 3-2에 소프트웨어 개발의 원리와 실습(소개원실) 때문에 로드가 많아서 그런 것도 있지만, 오히려 결전의 날이 다가올수록 욕망이 줄어드는 것이 되게 신기하기는 했다. 월파를 가지 못해도 그렇게 억울하지는 않겠다는 생각도 들었었다. 심리학적인 방어기제의 발동일 수도 있고, 잘 모르겠다...

팀연습도 많이 돌았는데, 사실 어느정도 즐기고자 하는 목적이라 ICPC 팀이 아닌 형식으로도 많이 돌았다. 예를 들어 floor_sum의 이지후(Numbering)나 박상훈(qwerasdfzxcl)이랑도 팀연습을 많이 돌았다. 그냥 약간 친구들 N명 풀 중에서 시간 되는 3명 돌아서 팀연습 도는 느낌이었다. Just use CRT의 이동현 최다니엘 조영욱 3인 체제로 돈 팀연습들을 정리해보면 아래 몇 개 정도인 것 같다.

 

https://qoj.ac/contest/1708 : 유컵 제3회 세미파이널에 대한 연습을 위해 유컵 제2회 세미파이널을 돌았다. 중국맛이었다.

https://qoj.ac/contest/2506 : 유컵 파이널 참가 도전을 위해 유컵 제3회 세미파이널에 참가했다. 너무 어려워서 개망했다..

https://qoj.ac/contest/1452(SEERC 2023) : 11솔을 했다.

https://qoj.ac/contest/1522 (EC-final 2023) : 돌 셋이 없어서 중국 ICPC 파이널을 돌았다. 중국맛에 정신을 못 차리다가 빠른 8솔로 마무리했다.

https://qoj.ac/contest/2511 (SEERC 2022) : 올솔로 1등을 했다. qoj에서 돌았는데, 코포 미러 기준으로도 1등이었다. 굿.

https://contest.ucup.ac/contest/2581 (유컵 Stage 5) : 내심 유컵 파이널에 가고싶은 마음이 있어서 시간을 내서 유컵을 돌았다. 버스 타고 높은 등수를 기록해서 유컵 레이팅 쌀먹에 성공했다...

https://codeforces.com/contest/2172 (2025 대만 리저널 미러) : 11솔로 미러에서는 1등을 했다. D에 4시간을 박았지만 시간 내에 AC를 받지 못하고 대회 종료 10분 이후 AC를 받았고, 그래서 현장 1등보다 낮았던 점은 좀 아쉽다.

 

아무튼 이런 몇 개의 팀연습을 돌았고, 전반적으로 엄청나게 망한 셋이 있는 건 아니어서 분위기는 되게 좋았다. 다만 floor_sum 팀도 되게 강팀이어서 대부분의 팀연습을 다 잘했기 때문에, 결국 그냥 잘하는 게 아니고 서울대 내에서 저 팀을 이겨서 3판2선 매치를 가져와야 하는 상황에서는 떨릴 수밖에 없었다.

 

방콕 리저널

 

학기중에 금요일 출국/월요일 새벽 입국 이라는 일정으로 빠듯하게 방콕에서 대회를 치뤘다. 대회 전날에는 예비소집을 하고 GEN vs KT 롤드컵 4강 경기를 보고 저녁을 먹고 잤다. 수면패턴 관리가 매우 잘 되어있어서 좋았다. 대회는 신기하게 오전 8시였는데, 호텔 조식으로 아침을 든든하게 먹고 대회를 치러갔다. 상세한 내용은 https://leinad2.tistory.com/38 참고하면 될 것 같다. 나는 내가 풀만한 유형의 문제인 DEFGH를 풀었는데, 약간 티피컬한데 난이도는 있는 문제들이라서 할 수 있는 범위에서 팀에 충분한 기여를 했던 것 같다. 물론 우승은 버스받아서 겨우 성공했다 ㅎㅎ

 

부산 리저널

 

이번에도 금요일에 기차를 타고 내려가서 토요일 밤에 서울로 돌아오는 일정으로 부산 리저널에 참가했다. 이번에 문제였던 점은, 예비소집 이후 너무 지쳐서 숙소에서 그냥 6시쯤 잠들어버렸다는 점이다. 12시에 깨고 2시에 깨고 3시에 깨고 4시에 깨고 계속 깼지만, 그때 깨면 진짜 대회를 망칠 것일 게 자명한 상황이어서 온 힘을 다해서 다시 잠들었다. 5시에 깼을 때는 진짜 다시 잘 수가 없을 것 같았는데, 10시 대회면 5시에 깬 정도면 오케이일 것 같아서 그냥 일어나서 씻고 폰 봤다. 아침은 옆에 있는 24시간 순두부찌개 가게에서 든든하게 먹고 메가커피에 들러서 200mg어치 카페인도핑을 때리고 대회장에 갔다. 

대회 시작 전, 대회장 앞에 있는 풍선의 개수가 다르길래 순서대로 A~M을 의미하고 풍선의 개수가 적은 것이 어렵고 풍선의 개수가 많은 것이 쉽다는 얘기를 팀원들이랑 했다. 이 가설에 따르면 A와 M은 쉬운 문제이고 E는 어려운 문제라고 이야기하였다. 물론 나중에 보면 알겠지만 원숭이 수준의 정확도다...

아무튼 대회 시작 전 전략은 ABCD를 다니엘이 보고, EFGHI를 내가 보되 E는 조금만 어려워보여도 어려운 문제니까(...) 그냥 던지고 JKLM을 동현이가 대회 시작 직후 환경세팅을 한 다음 보기로 했다. E는 지문이 길길래 그 판단에 의해 그냥 던졌고, F부터 읽은 다음 G 지문에 집중이 안 돼서 H로 갔다. H를 읽어보니 문제세팅이 M과 같다고 해서 M이 쉬운 문제라는 가설도 같이 생각나서 M을 뺏어왔다. 문제를 읽어보니 너무 쉬운데 4분 시점에 아직 솔브가 없어서 의아했었는데, 그냥 맞을 수밖에 없어서 매우 간단한 코딩을 하고 낼지말지 망설이다가 그냥 6분에 제출해서 퍼솔을 먹었다. 그냥 마지막 문제라서 아무도 아직 안 봤던 것이었다.

그리고 H를 읽은 다음 F를 좀 고민하다가 G를 읽었다. 지문 시작 부분이 읽기 버거웠던 건데, 그 부분은 그냥 사실 의미없는 내용이었어서 그 뒤는 금방 해석됐고 풀이는 금방 나왔다. 당시 솔브가 없는 상황이어서 퍼솔을 먹겠다고 열심히 구현했지만 퍼솔도 뺏겼고 심지어 제출한 코드는 WA를 받았다. WA를 받는 게 진짜 말이 안 돼서 보니까 __int128 범위일 것은 롱롱으로 관리하고 있었다. 그래서 그걸 고쳐서 냈는데 다시 WA를 받았다. 알고보니 __int128로 고쳐야할걸 하나 덜 고쳤다... 아무튼 28분에 +2로 AC를 받았다.

이후 I를 읽어보려고 하는데 지문이 그냥 머리에 안 들어와서 팀원들한테 유기했다. 그리고 C가 풀렸길래 C를 봤는데, 내가 넓이*2+1=경로길이 가 아니냐는 희대의 트롤풀이를 낸 다음 1분만에 반례를 찾았다. 반례는 경로 내부에 가지들이 달려있는 형태인데, 가지에 해당하는 간선 개수를 모두 셀 수 있으면 문제가 풀려서 그 방향으로 접근하게 돼서 진짜 망했다. 그런데 계속 솔브가 우수수 쏟아졌고, 이 풀이로 풀리는 문제라면 이정도로 풀리는 것은 도저히 말이 안 되는 상황이었다. 그때 다니엘이 다른 풀이로 접근을 시도했더니 대충 풀이 견적이 나왔고, 나는 C에서 할 수 있는 게 없어보여서 C를 떠났다.

사실 계속 내마음을 사로잡고있던 문제는 F였다. 가장 처음 읽은 문제기도 했고 재밌어보였다. 그래서 그때부터 F에 온몸을 박았다. 처음에는 O(N^4)이라고 주장하는 풀이를 내고 구현을 했는데, 40^4이라는 점에서 서울리저널식 TL에 어울리지 않아서 굉장히 무서웠지만 일단 맞는 것 같아서 구현을 했다. 하지만 물론 예제가 안 나왔다... 예제를 고칠 방법을 생각을 하다가 인자를 하나 더 추가하면 해결된다는 사실을 깨달았다. 그렇게 해서 O(N^5) 풀이가 나왔고 제출했지만 WA를 받았다. 그 N^5 풀이를 프린트해서 열심히 보니까 실수한 부분이 있었고, 이 풀이를 고쳐서 예제를 돌려봤더니 이제는 예제가 안 나왔다... 예제 3에서 원래 3이 나와야 하는데 2가 나왔다. 사실 틀린 부분을 맞게 고친 건데 예제가 이제 안 나오는 상황이라 엄청 기이한 상황이었는데, 상태개수가 O(N^4)인 dp에서 dp값을 하나하나 찍어보면서 문제원인을 찾아내는 엄청난 과정을 거친 끝에 내가 생각하던 문제상황에서는 답이 2가 맞다 라는 놀라운 결론을 얻어냈다. 내가 고려하지 않은, 값을 정수로만 바꿔야 한다는 조건이 문제였고, 그것 때문에 답이 2가 아니라 3이 되는 것이었다. 그 조건 자체는 dp를 맵을 사용한 O(N^6) dp로 바꾸면 해결할 수 있었고, 잘 구현해서 어케어케 했지만 TLE를 받았다. (사실 이 시점까진 내 복잡도가 얼마인지는 생각하지 않고 있었다. N이 40이면 아무 다항시간이나 짜면 된다고 생각했는데 결국 TLE가 나왔다.)

내가 F에 머리를 박고 있는동안, 팀상황은 8솔을 하고 각자 박치기를 하고 있는 구도가 되어있었다. 그리고 J에서는 풀이가 나왔었는데, 2d seg를 사용하면 되는데 2d seg를 짤 줄 아는 사람이 나밖에 없다 라고 하였다... F에 머리 박는 것도 힘든데 J에서 2d seg 짜주기도 해야 하는 어지러운 상황이었고 어떻게든 F를 쳐내서 머리를 맑게 해야겠다는 생각밖에 안 들었다.

프린트해서 코드를 열심히 본 결과 사실 내가 낸 코드는 N^6도 아닌 N^7이고, N^6으로 줄이는 것은 매우 쉽다는 결론을 냈다. 그래서 N^6으로 복잡도를 줄였는데, 중간에 코딩실수를 해서 예제가 안 나와서 상당히 곤란했다. 그런데 N^6으로 제출을 해도 TLE를 받았다. 40^6이 40억이라는 사실을 그제서야 깨달았다. 그렇지만 내 코드가 40억이라는 사실을 깨달아도 포기할 수는 없었다. 이미 너무 멀리 왔고, 아무리 생각해도 dp상태와 전이가 충분히 바운드돼서 /24 정도는 충분히 붙을 코드였다. 그래서 나는 맵 dp를 언오더드 맵으로 하고 프라그마를 박으면 돌 것이다! 라고 주장을 했고, 그런데 이미 5번이나 틀린 상황이라 그러고 내기는 좀 곤란한 상황이어서 코드를 더 보면서 최적화할 부분을 찾아봤지만 딱히 더 최적화할만한 부분은 없어서 언오더드 맵으로 바꾸기+프라그마 박기 를 하고 제출을 하고 기도를 했다. 아니 사실 기억해보니 기도를 한 것이 아니라 제출하자마자 J의 2d seg 파트를 짜러 끌려갔었다. 제출의 결과는 팀원이 대회장 앞 스크린에 떠있는 슼보로 확인해줬고, 꽤 오래 돈 결과 AC를 받아 퍼솔을 먹었다. (206분, +5) 2시간을 약간 넘는 시간을 박은 것이 결국 보상으로 돌아왔고, 스코어보드를 확인해보았을 때 F를 제출해본 팀조차 우리밖에 없었기 때문에 F를 푼 것이 대회 종료 시점에서도 엄청난 크랙으로 작용할 것이 분명한 상황이었기에, 엄청나게 기분좋았다.

이후에 한 일은 J에서 디버깅을 하고(2d seg 파트에서도 실수가 있었다 ㅈㅅ ㅎㅎ) TLE를 받는 상황에서 최적화를 열심히 하는 것이었다. floor_sum 팀이 J를 푼 것은 거의 확실해보였지만 J를 풀었다해도 우리가 약 40 차이로 패널티를 이기고 있음은 확실해보였다. 다만 floor_sum 팀이 한 개를 더 풀 가능성이 꽤 있기 때문에 이 상황에서 우리가 지지 않기 위해서는 무조건 솔브가 하나 더 필요했다. (패널티가 낮은 솔브가 필요하다는 생각은 대회 끝나고나서야 했다.)  그렇지만 J에서 무한 TLE를 받았고, 시간을 줄일 아이디어들을 총동원해보았지만 계속 TLE가 나왔다. 마지막 299분 55초 시점까지 조금씩 시간을 줄여서 제출해봤지만 결론은 TLE. 그렇지만 그 시점까지 우리가 우려하고있던 floor_sum 팀의 추가제출은 없었기에 대회를 기분좋게 마무리할 수 있었다.

 

스코어보드. 생각보다는 10솔이 더 많이 나왔다. 내가 F를 푼 이후로 그걸 이정표로 F를 잡아서 풀어낸 팀이 많은 것 같다. 각각의 패널티 차이도 그렇게 크지 않아서, 1등을 운으로 겨우 했다는 생각이 좀 들었는데 그냥 J TLE받은 게 억까라고 생각하기로 했다. 25만 로그제곱 TLE;;;;

 

후기

 

아무튼 2023년과 2024년의 실패를 딛고 2026 ICPC World Finals에 진출하게 되었다. 우리 팀은 충분히 잘하는 팀이라고 생각하기 때문에, 월파에서 좋은 성과를 내고 싶다. 일단 올해 노력한 것은 모두 좋은 결과로 돌아왔으니, 앞으로도 계속 좋은 결과가 돌아오면 정말 좋을 것 같다.