2025 ICPC Seoul Regional 본선 후기

이번에도 Fox is cute 팀으로 나갔다. 팀원은 SongC와 serin이다. 모두 코드포스 기준 레드 이상이라서 나름 잘하는 팀이라고 생각한다.

 

팀연습

• 카이스트 가을대회에서 2등을 했다. 세린의 H번 버저비터가 인상적이었다.
• SEERC 2024를 돌아 1위 성적을 냈다.

지금와서 찾아보니 최근 2달간 별로 팀연습을 안한거 같다. 아시아 퍼시픽 챔피언십까지는 좀 해야겠다.

 

개인 ps

시험기간때 ps를 완전히 놓았다가 시험기간이 끝나고 다시 재활을 시작했다.

• UCPC 2025 문제들을 모두 풀어봤다. 생소한 알고리즘들을 좀 써서 나름 교육적인 셋이었다고 생각한다. 이거 푸는데 2주 걸렸다.
• icpc 직전에 기출을 좀 공부하고 갔다. 2022 icpc때 현장에서 풀었던 empty quadrilateral, longest substring, stock price prediction 등등 문자열과 기하를 벼락치기 했다.

ucpc 2025 올솔!

 

icpc 예선

모두가 푸는 6문제를 풀었다. 이후 serin이 B번을 풀겠다고 해서 키보드를 잡게 하고 songC랑 같이 문제들을 순회했다. 아직 안 푼 문제들의 난이도가 상당히 어려운 것 같아서 예선 컷은 대충 넘겼다고 생각하고 놀았다. 풀만한 자료구조 문제를 "절대 못 푸는 문제"라고 하고 방치하고 다른 어려운 문제들을 봐서 그런지 1문제도 풀이를 내지 못했다.

 

icpc 본선

아침에 속이 좋지 않았다. 그래서 아침을 거르고 대회장에서 간식을 먹을 생각이었지만 간식이 없어서 슬펐다. 배고픈 상태로 머리가 잘 돌아갈지 의문이었다.

 

SongC가 구현을 잘하는 것 같아서 초반에 쉬운 문제 / 구현이 어려운 문제는 SongC에게 던지는 전략을 선택했다.

기하는 나보다 serin이 구현을 잘하는 것 같아서 serin에게 던지기로 했다.

0:00 ~ 2:11

내가 JKLM을 읽기로 했다. J번의 부등호 조건들을 보는데 배고파서 그런지 무슨 소리인지 이해가 되지 않았다. 가볍게 패스를 하고 K번을 보는데 n범위가 2000인 기하가 있었다. 대회 초반에 볼 문제는 아닌 것 같아서 넘겼다. L번을 보는데 다 읽어보면 자명한 문제가 쿼리가 주어지고 n, q 범위가 2백만이어서 문제를 잘못 읽은건지 긴가민가했다. G를 짜겠다는 SongC의 키보드를 빼앗고 바로 짰다. 제출 전에 스코어보드에서 AC가 떴길래 내 풀이가 맞았다는 확신을 가졌다. 가볍게 AC를 받았다. 내가 L을 짜는 사이에 SongC가 스코어보드에서 AC가 뜨는 M을 풀었다. G를 SongC가 마저 짜서 AC를 받고, M에서도 AC를 받았다.

 

0:09 (L AC), 0:19 (G AC), 0:21 (M AC)

 

그동안 나는 스코어보드에서 AC가 나오는 C를 보고 cell을 기반으로 하는 forest에서 dfs를 하는 풀이를 냈지만 구현을 빠르게 할 자신이 없어서 SongC에게 던지고 슼보에서 풀리는 D번을 읽었다. 그 사이에 serin이 E를 풀었다. 

 

0:44 (E AC)

 

SongC가 C를 짜는 동안 문제들을 좀 봤다. K번을 보니까 그냥 불도저를 하면 풀리는 문제였다. 세린의 큐에 넣었다. 나중에 보니까 불도저를 쓰지 않고 그냥 각도정렬을 하면 된다고 한다. 바로 안 짜서 다행인 것 같다.

스코어보드에서 풀리는 D번을 풀려고 노력했다. 중간에 10^9 범위에서 knapsack을 해야 한다는 결론에 도달해 삽질을 좀 하다가풀이를 냈다. 구현이 쉬운 것 같아서 SongC의 키보드를 빼앗았다. 제출을 하기 직전에 내 풀이에 살짝 틀린 부분이 있어서 고친 후에 AC를 받았다. 페널티를 아껴서 좋았다. 그 이후 SongC가 C를 맞았다.

 

1:07 (D AC), 1:12 (C AC)

 

serin이 K번을 구현하기 시작했다. SongC는 레전드 구현 문제 I번의 구현을 구체화하고 있었다. 나는 문제를 풀어야 되는데, 남은 문제가 ABFHJ이었다. 그냥 레전드 어려운 문제밖에 없다는 사실을 알 수 있다. A는 지문이 길어서 던졌다. B는 월파에 쿼리 없는 버전이 루비로 나왔던 거 같은데 쿼리를 덕지덕지 발라놓은 것 같아서 던졌다. J는 자료구조 비빔밥처럼 생긴게 어려워가지고 못 풀겠었다. 나중에 알고보니 부등호 조건이 말하는게 "구간이 겹친다"라는 것이었는데 기초적인 관찰도 못했으니 못 풀겠는 것이 당연하긴 하다. 그리고 SongC가 수학처럼 생겼다고 던져준 H를 보고 있었다. 

 

H번은 생성함수 비빔밥처럼 생긴게, modulo로 998244353을 주지 않는게 좀 수상한 문제였다. 대충 쪼물딱대는데, FFT 1번으로  풀리는 것 같아서 풀이를 냈다고 선언을 했다. 그동안 serin과 SongC가 K와 I를 맞았다.

 

1:38 (K AC), 2:21 (I AC)

 

2:11 ~ 5:00

초반 분위기가 너무 좋았다. 스코어보드에서 1위를 다투고 이 페이스를 유지하면 우승도 할 수 있을 것 같았다. serin은 F번의 풀이를 냈다고 주장하고 있고, 조금 이따가 B번의 풀이가 나왔다. H번은 풀이가 다 나왔고 금방이면 구현을 할 수 있을 것 같았다. 모두 푸는 것을 목표로 했다.

 

serin이 F번을 15~20분에 짤 수 있을 것 같다고 선언을 한 후 키보드를 잡았다. 그동안 나는 H번의 구현을 구체화하고 있었다.

 

FFT 1번을 해야 하는 것에서 FFT 3번을 해야 하는 것으로 늘어났다. SongC가 내 풀이를 듣고 나서 일반적인 FFT를 하면 숫자 범위가 10^24까지 가서 실수 오차가 나고, 3개의 소수에 대해 NTT를 한 이후에 CRT를 해야 한다고 말했다. 그래서 팀노트에서 베껴야 할 코드가 더더욱 늘어났다. 설상가상 팀노트의 CRT에서 사용하는 함수를 못 찾겠어서 CRT는 내가 직접 짜야 했고, 정말 많은 분량의 코딩을 해야 했다. serin이 예제가 안 나오고 디버깅이 길어지자 내가 키보드를 뺏고 구현을 했다.

 

팀노트 따라치기에서 실수를 2번 정도 한 것을 잡으면서 기나긴 디버깅을 한 끝에 예제가 나왔고 제출을 해서 TLE를 받았다. NTT를 9번을 하니까 그럴 수도 있다. 이것보다 빠른 풀이는 절대로 있을 것 같지가 않아서 상수 최적화를 하기로 결심했다. serin은 중간중간 F번의 디버깅을 고쳤다고 하기도 하고, 풀이가 틀렸다고 하고 고치기도 했다. 이때부터 우승은 물건너갔다고 생각했다.

 

H번의 NTT 소수들을 const로 고치기, 나눗셈을 곱셈으로 고치기 등등의 상수 최적화를 했지만 TLE만 계속 되었다. 스코어보드에서는 한번에 맞는 AC가 나오고 나는 내 풀이를 의심하기 시작했다. 이것이 정해라면, 내가 이렇게 상수최적화를 하고 있어야 하지 않을 것이다. 그래서 serin이 F번을 풀기 위해 다시 키보드를 잡는 동안 SongC와 함께 H번의 풀이에 대해 논의를 했다.검토를 해도 내 풀이는 맞았고, 의미없는 상수 최적화만 계속 해나갔다. AC가 나올 것이라는 기대는 하지 않았다.

 

팀 분위기가 안 좋아져갈 무렵, 한 가지 생각을 해냈다. 사실 초반에 빠르게 8솔을 한 것이 굉장히 잘한 것이라서, 후반을 좀 말아먹어도 결과적으로 좋은 등수를 가져올 것이라는 것이다. 실제로 8솔을 한 팀들 중 페널티가 1등이었다. 그리고 리저널 우승을 하지 못할 것이라면, 아시아 퍼시픽 챔피언십을 나가는 것은 카이스트 3등만 하면 되는 것이기 때문에 크게 잘할 필요가 없다는 것이었다. 그래서 적당히 마음을 내려놓았다.

 

대회가 거의 다 끝나가고 팀노트에 있는 FFT를 구경하고 있었다. 한가지 코드가 눈에 보는데, multiply(vector <ll> v, vector <ll> w, int mod)같은 함수였다. 사실 내가 NTT를 3번 돌리고 CRT를 돌려서 개고생을 할 필요가 없었고 팀노트에 있는 이 함수를 베끼면 되는 것이었다! 10분을 남기고 팀노트를 따라치기 시작했다. SongC와 serin은 내가 코드 베끼는 것을 구경하고 있었다. long double을 사용한 FFT 풀이와 double을 사용한 FFT 풀이를 따로 제출해서 기도를 하는데, AC가 나왔다. 레전드 버저비터에 환호성이 나올 수 밖에 없었다.

 

대회 이후

스코어보드에는 프리즈 이후 제출이 많았다. solved.ac 디스코더 서버에서는 누가 오렌지 3명있는 팀들이 다들 9솔브를 했을 것 같다고 말했다. 온몸비틀기 해서 겨우 버저비터로 9솔브를 했는데 좀 슬펐다. H번에 제출을 많이 한 것과 초반에 잘한 것이 합쳐져서 9솔 중반 정도의 순위에 안착하지 않을까 싶었다. 기나긴 후원사 세션을 마치고 대회장에서 스코어보드를 까는데...

 

그냥 해외 팀을 제외하고 프리즈 이후 우리 밑에 있던 팀 중 9솔브가 없었다. 그래서 국내 3등을 하고 마무리하게 되었다. 참고로 H를 풀던 안 풀던 순위가 바뀌지 않는다. 어이x

 

후기

H번에서 말린건 팀연습을 많이 돌지 않아서 생긴 사전지식 부족이라고 생각한다. serin의 F번도 말리지 않게 중간에 누가 풀이를 논의했으면 좋았을 것이라는 아쉬움도 든다. 하지만 결과적으로 좋은 등수가 나왔으니 만족한다. 앞으로 팀연습을 열심히 해서 덜 말리는 팀이 되면 좋을 것 같다!