프밍기 학인시를 위해 기초 알고리즘을 공부하던 나에게, Moonlight는 팀 대회에 나간다는 허무맹랑한 꿈을 심어주었다.
그땐 설마 내가 대회를 칠 실력이 될 때까지 PS를 하겠나 싶었다.
그런데 벌써 PS에 입문한지 11개월을 넘어서 1년을 바라보고 있는 시점이 되었다.
그동안 1,300개 이상의 문제들을 풀고, SCPC, LGCPC와 같은 굵직한 대회도 참가하며 경험을 쌓았다.
약하지만 그나마 하나의 전력으로 쳐줄 법한 PS러가 된 것이다.
파이썬을 1도 다룰 줄 모르던 1년 전의 나는 지금 이 모습을 상상이나 했을까.
아무튼!
고등학교 시절부터 친하게 지낸 친구들과 이번 ICPC에 도전장을 내밀었다.
< Entropi의 팀원 소개 >
Cenix820 (나) : 저점이 높은 대신 고점도 그 정도이다. 쉬운 문제 스피드런과 해 구성하기가 강점이다. 코드포스 기준 블루 실력이다.
Moonlight : 저점이 낮지만 고점이 꽤 높다. 수학, 특히 정수론이 강점이다. 코드포스 기준 블루 실력이다.
Loreips : 딱히 약점이 없는 우리 팀의 올라운더이다. 애드 혹과 구현이 강점이다. solved.ac 기준 Ruby III이며, 코드포스 기준 오렌지 실력으로 추정된다.
ICPC 이전
팀명: 뭐로 할래 뭐할래 니가 정해 싫어 몰루 (유기) (결국 Entropi로 정함)
팀 연습: 안 함
팀 노트: 없음
전략: 알아서 풀어라
이렇게 보면 참 완벽하게 망한 팀 같다.
하지만 4년 간 같이 지내며 서로의 강점과 약점을 얼추 파악하고 있다.
결정적으로 나는 이 팀원 둘에게 PS를 배웠기에, 팀원들은 내가 어디까지 아는지조차 잘 알고있다.
아마 신생팀 치고는 합이 꽤 맞지 않을까.
예비 소집일 (10/10)
2025년 추석 연휴.
19년 인생 사상 최장 기간의 황금연휴이다.
그런데 왜 이 기간에 ICPC를 치는 것인가?
연휴를 반납하고 학교로 가서 예비소집에 참여했다.
PA번은 2024년 예선 문제 중 가장 쉬웠던 문제.
난 이미 이 문제를 풀어보았기에 Loreips에게 문제를 떠넘겼다.
PB번까지 풀까 하다가 귀찮아서 그냥 퇴실했다.
그래도 팀 노트는 필요하지 않을까 싶어서, 저녁을 먹은 이후로 팀 노트를 급조하기 시작했다.
우리 팀은 justiceHui님의 teamnote for newbie(https://github.com/justiceHui/icpc-teamnote-for-newbie)를 기반으로 팀 노트를 작성했다.
팀원 세 명 모두 Python을 주력으로 사용하기에, 팀 노트의 코드들을 전부 Python 코드로 바꾸고 필요해 보이는 몇몇 알고리즘들을 추가했다.
완성하고 보니 18페이지라 빈 공간이 많아서 최애캐들을 넣었다.
ICPC 예선 당일 (10/11)
늦게 잠에 들었는데, 방에 모기가 있어서 Loreips와 내가 잠을 설치기까지 했다.
원래 아침 일찍 일어나 PS를 하며 뇌를 풀 생각이었지만, 그냥 정오까지 잔 후 일어나 점심을 먹고 바로 대회를 치러 갔다.
예선은 본인의 학교에서 모든 팀들이 모여 감독 하에 치른다.
우리 학교(KAIST)에서는 13팀이 참가했고, 우리 팀 Entropi는 가장 오른쪽 뒤의 자리에 앉았다.
VSCode를 켜서 문제 파일을 생성하고 대회 시작을 기다렸다.
0:00 (0 solved)
한국어 문제가 3개인 것을 확인하고 내가 문제를 배분하기 시작했다.
A는 슥 보니 어려워보여서 Loreips에게 주고 그 다음 한국어 문제인 F를 Moonlight에게 줬다.
그런데 남은 문제인 I를 읽어 보니 너무 정수론 문제처럼 보이길래, I를 Moonlight에게 떠넘기고 F를 빼앗았다.
0:24 (1 solved / F)
내가 잡은 F는 실버 수준의 쉬운 구현으로 보여서 바로 노트북을 잡아 코드를 쓰고 제출했으나 WA를 받았다.
WA가 계속 쌓이자 마침 A를 던지고 다른 문제를 물색하던 Loreips와 함께 디버깅을 시작했고, leading 0을 처리해야 하는 경우를 발견하여 3틀 이후 AC를 받았다.
쉬운 문제인건 맞았다.
0:39 (2 solved / F, I)
그동안 Moonlight는 열심히 I를 풀고 있었다.
피타고라스 원시쌍을 이용해 풀다가 막혀 다른 방법을 고안했고, 4k^2의 약수를 구하는 문제로 바꾸는 것에 성공했다.
여기서 Moonlight는 k가 10^7이라는 것에 착안하여 폴라드 로를 외쳤다.
너무 과한 오버킬이지 않나 싶으면서도 팀 노트에 적어둔 폴라드 로 코드를 작성하기 시작했다.
도중에 폴라드 로를 쓰지 않는 멀쩡한 풀이가 떠올랐지만 이미 코드가 거의 완성되어 있었기에 그냥 그대로 계속했다.
다행히 한 번만에 AC를 받았다.
1:04 (3 solved / F, I, H)
남은 한국어 문제인 A를 계속 시도했지만 말려서 잘 풀리지 않았고, 스코어보드를 보며 많이 풀린 문제를 탐색했다.
순위권 팀들이 H와 J를 많이 푼 것을 발견해 Loreips가 H를 붙잡았다.
lis 느낌인 것 같았으나 어떻게 변형해야 할 지 몰라 고민하던 와중, Loreips가 좌표축을 45도 기울이는 아이디어를 떠올렸다.
내가 그대로 구현하여 AC를 받았다.
1:20 (4 solved / F, I, H, J)
이것저것 건드려보다가 나는 Moonlight와 함께 C를 붙잡기 시작했고, 여러 케이스를 손으로 짜보다가 위치 관계 기반의 다익스트라 or 진짜로 모든 케이스 하드코딩하는 많은 조건 분기라는 애매한 결론만 내렸다.
그 사이 Loreips가 J를 n^3 상수 커팅으로 뚫는 풀이를 발견하고 C++로 코드를 작성했다.
그런데 제출하니 자꾸 컴파일 에러가 떴는데, <vector>를 <Vector>로 적어서 그렇게 되었다는 사소한 해프닝이 있었다.
근데 왜 로컬에서는 컴파일이 된 것인지를 궁금해하며 AC를 받았다.
1:35 (5 solved / A, F, I, H, J)
A에서 n^3 dp, 그리디 접근 등 다양한 아이디어가 나왔지만 모두 애매해 A를 유기하고 있었다.
Moonlight가 dp를 가장한 그리디 풀이를 작성하여 제출했지만 WA를 받았고, Loreips가 n^3 dp로 바통을 이었다.
C++로 n^3을 뚫으려고 시도하던 도중, Loreips가 n^2 dp 풀이를 발견해 Python으로 코드를 작성하고 AC를 받았다.
2:03 (6 solved / A, C, F, I, H, J)
스코어보드를 보니 최상위권 팀들이 푼 문제들 중 우리가 풀지 못한 문제가 C 뿐이었다.
더 이상 풀 만한 문제도 딱히 보이지 않았기에 어쩔 수 없이 C를 붙잡을 수 밖에 없었다.
나와 Moonlight가 지금까지 떠올린 C의 아이디어를 Loreips에게 전달한 후, Loreips가 위치 관계 기반의 다익스트라 접근을 세분화하여 BFS 풀이를 만들어 AC를 받았다.
이 시점에서의 순위는 15등이었다.모든 케이스 하드코딩하기 귀찮아서 미뤄둔 게 다행이었다.
~3:00
1등 팀을 제외한 모든 팀이 6솔 이하였기에 남은 문제들이 모두 심상치 않다는 것을 깨달았다.
나는 D를 잡았고, Moonlight와 Loreips는 G를 잡아 풀이를 고민하기 시작했다.
옆에서 무슨 G를 오토마타로 어쩌고.. 소리가 들리던 와중에 나는 D의 그리디한 접근을 시도했고, 얼마 지나지 않아 풀이를 발견해 팀원들에게 공유했다.
그런데 풀이가 증명이 되지 않은 것은 둘째치고, 구현하기가 너무 까다로웠기에 남은 시간 안에 풀 수가 없었다.
결국 스코어보드나 구경하다가 대회가 끝났다.
프리즈 당시의 전체 순위는 21위, KAIST 내부 순위는 5위였다.
이변이 없다면 무난하게 본선에 진출할 수 있을 것이다.
첫 팀 대회였음에도 불구하고 우리 팀이 생각보다도 합이 잘 맞아 좋은 성과를 얻을 수 있었다.
모든 것을 혼자 해결해야 하는 개인 대회와는 달리 팀 대회에서는 내가 막힌 부분을 팀원들에게 떠넘기면(?) 그걸 해결해준다는 부분이 참 신기하다.
하지만 이번 대회에서 내가 팀에 기여한 정도가 많지 않다는 점이 아쉽다.
본선에서는 몇 문제 캐리하기 위해 열심히 공부해야겠다.
대회가 끝나고 팀원들과 먹은 저녁 사진으로 글을 마무리한다.
(10/14 업데이트)
최종 스코어보드가 나왔다!
전체 24등, KAIST 6등으로 본선 진출을 확정지었다.
역시 카이는 강하구나
본선 후기로 돌아오겠습니다~