2025 ICPC 후기

첫 ICPC(2025 ICPC Korea Regionals - 예선)에 대한 후기를 남기고자 다음의 글을 남깁니다.

서론

대면으로 바로 시작되는 1번째 ICPC! 본인의 성적은 KOI 1차에서 터지고 nypc 2차에서 터진 고등학교 때는 좋지 않은 성적으로 관련 PS 대회들을 마무리했는데, 오랜만에 칼을(?) 갈고 ICPC Regional 예선에 임하였다. 팀을 이룬 3명은 다음과 같다:

• Moonlight_: 정수론(수학)쪽 잘함, 구현 실력 딸림, 그래도 실력 자체는 블루급?
• Cenix820: lower bound가 강해서 쉬운 문제 빨리 구현하는 능력은 진짜 좋음, 실력은 블루급
• Loreips3115: 팀의 핵심. 직관이 매우 좋고, 구현 능력이 매우 빠름. 코포를 안 치긴 했다만 필자는 이 친구는 렌지급이라 생각함.

(25학번-25학번-25학번)인 신생 뉴비 팀!

팀명은 그냥 Entropi로, Entropy의 음만 같은 걸로 정했음. 사실 팀연습을 $0$회(?!)하긴 했다만, 4년 동안 아는 사이라, 서로의 장단점은 거의 완벽하게 파악하고 있다는 게 장점. 큰 팀 전략은 크게 없고, 적당히 잘하는 것에 분배하다가 풀 수 있는 게 없으면 쭉 한 문제 파는 방식으로 진행된 것 같다. 나중에 자세히 설명하겠다만, 팀에서 아이디어를 전달하는 과정이 매우 잘 된 것 같아서 기분이 좋다.

대회 전

전날 급하게 팀노트를 짰다. 우리 팀의 경우 C++보다 파이썬이 오히려 주력 언어라, 파이썬으로 여러 알고리즘들 바꾸느라 고생을 좀 하긴 했다만,

• 어차피 우리가 괴상한 알고리즘 쓰는 문제를 건드릴 수 있을까
• 기본적 알고리즘만 충실해도 충분한 게 아닐까
• 라는 마인드로 적절히 필요한 알고리즘 추가해나가면서 정리를 하였다.

이제 그냥 슬슬 마무리가 될 시점에 각자의 최애캐로 토템을 넣으며 팀노트를 마무리하였다.

• Moonlight: 최애캐 2개 넣는 대신 첫 번째 캐릭터 음해를 허용했고, 그게 8.4의 결과…아야카이뿌다
• Loreips3115: 비타
• Cenix820: 넬

그렇게 0회 팀연습 이후로 첫 팀연습을 ICPC 예선으로 진행하게 되었다. (???) 목표는 적당히 6솔 정도하면 본선 안정권이지 않을까라는 생각으로 임했다.

대회 중

(0:00) (0 Solved)

ICPC 예선의 시작으로 종이를 받은 후 Cenix820은 나랑 Loreips3115한테 문제지를 분배하기 시작하였다. 우선 전통적으로 쉬운 한글 문제를 보면서 A F I가 있었는데…

슈퍼무브1: Cenix820는 F를 나한테 주려다가 훨씬 정수론틱한 I를 보냈다. 이는 현재 I의 평판을 생각하면 굉장한 수였고, 그렇게 F/A/I를 파고 있었다.

(0:24) (1 Solved)

몇 분이 흐른 후, Cenix820는 Loreips3115의 도움으로 여러 반례들을 찾으며 F를 해결하였다. 생각보다 F는 예외 케이스가 많은 문제였기에, 4틀이라는 아쉬운 점이 남아 있긴 하다만.

그 사이 Moonlight는 I를 여러 가지 방안으로 접근하던 중. 피타고라스 원시쌍이라는 접근을 시도했으나 잘 안 되서(나중에 알고 보니, 이를 쓰는 풀이 또한 존재했다고 한다) 합차공식을 바탕으로 한 접근으로 시도하고 있었고,

(0:39) (2 Solved)

결국 약수적 접근을 바탕으로 한 접근에 성공했다. 다만, $O(N)$이 됨을 알고, 그냥 폴라드 로 쓰면 된다고 Loreips3115한테 말하니까, 구현은 금새(?) 완료되었다. (사실 폴라드로 안 쓰고 깡 $O(\sqrt{N})$ 접근으로 되긴 한다만….) 그렇게 I를 2번째에 1트컷으로 완료.

(1:4) (3 Solved)

슈퍼무브2: 여러 문제를 보고 있긴 했는데, 그 이후 Loreips3115가 각도를 45도 돌리면 LIS 형식의 문제로 치환된다는 것을 확인하고 Cenix820가 짜서 AC.

그 사이 Cenix820와 Moonlight는 C를 건드리고 있었는데, 뭔가 위치관계를 바탕으로 한 다익스트라하면 어떨까라는 아이디어가 나오긴 했는데, 다른 걸로 이어지진 않고 뭔가 아쉬운 아이디어로 남아있었다.

(1:20) (4 Solved)

Loreips3115는 J를 깡구현으로 된다는 사실을 파악하고 짜고 AC. 역시 믿을 만하다.

(1:35) (5 Solved)

Loreips3115와 Moonlight_는 같이 A를 보고 있었고, Moonlight_는 잘못된 DP 아이디어를 제시하고 바로 틀리지만, 이후 Loreips3115가 $O(N^{2})$ 아이디어 발견해서 바로 해결. 이 문제가 슼보 기준 상당히 빨리 풀렸는데, 이 아이디어를 늦게 발견한 게 좀 아쉬운 점.

(2:03) (6 Solved)

그 사이에 남은 문제를 여러 개 보고 있었는데, 도통 다 안 풀리고, 실제로 C를 제외하고, 나머지 문제는 E를 푼 1위 팀을 제외하고 안 풀려 있었다. 그러다가

슈퍼무브3: 그렇게 기존 C의 위치관계 관련 아이디어를 Loreips3115한테 갔다주니, 좀 더 위치관계를 세분화할 시 BFS로 해결된다는 아이디어가 탄생하였고, 노드 수도 적절해서 해결이 되었다.

(~3:00) (6 Solved)

남은 문제들은 건드리기가 매우 어려웠다. 결론적으로 7솔을 한 팀은 매우 적었고…6솔에 한 것에 만족하고 15분 전부터 그냥 슼보나 둘러보면서 대회를 마무리하였다.

대회 종료 후

그렇게 팀 세 명이서 저녁을 먹으면서 solved.ac 디코에서 icpc 얘기나 나누면서 마무리했다.

대회 후기

생각보다 괜찮은 문제가 많았고, 팀 간의 협업도 잘 되서 기분이 매우 좋은 날이였다. 게다가 내일은 호요랜드로 놀러간다! 시험 1주 전 힐링할 수 있는 좋은 경험이였고, 본선 때도 최선을 다할 것이다. 아마 그래도 2솔 이상은 하고 싶긴 하다…teamnote에 조금 더 빡센 알고리즘 몇 개 더 넣지 않을까..