ICPC 2025 Seoul Regional Nationwide Copetition 후기

ICPC 2025 서울 리저널 인터넷 예선이 끝났습니다. 끝난지는 한참 됐는데 그래도 해 바뀌기 전에 후기는 써야할 것 같아 급히 작성합니다.

 

Just Reboot JungSangHwa라는 팀명으로 출전했습니다. 이상한 뜻이 있는게 아니고 ICPC 2024의 팀 JungSangHwa를 리부트해서 새롭게 멤버를 짜왔다는 의미입니다. 

 

qvixnh22: 2024 JungSangHwa 팀에서 유일하게 남은 팀원입니다. 논증기하, 그래프, 직관에서 증명으로 넘어가기에 상대적으로 강하고 구현에 아주 약합니다. 이 부분은 본선에서 아주 크게 작용합니다.

6729skl: 2024 LeetTtukBang 팀 멤버입니다. LeetTtukBang의 mbae059와 Yera_가 졸업을 하는 바람에 혼자 남겨졌습니다. 팀에서 개발 경력이 가장 길기 때문에 디버깅에 강합니다. 하지만 이 부분도 본선에서 크게 작용합니다.

kolorvxl: 25학번 신입생(였던 것)입니다. 코드포스 레이팅이 높은 만큼 구현 실력이 팀에서 가장 좋습니다. 로직 이해가 어려운 편인 문제의 구현을 전적으로 맡았습니다.

 

대회 직전까지 본선 진출에 대해서는 아무 걱정이 없었습니다. 부산대학교 팀 역사상 가장 강력하다고 추정되는 수준의 팀이 나왔다싶기도 했고, 학교 1등으로 단독 진출을 노리기에 다른 팀들에 비해서 실력 차이가 충분히 난다고 판단했기 때문입니다.

 

천천히 시작했습니다. 2024 예선때와 마찬가지로 교내 전체 참가자가 강의실에 모여서 컨테스트를 진행했고, 또 마찬가지로 문제지가 빠르게 도착하지 않았기 때문에 문제지를 모니터로 가장 먼저 확인했습니다.

 

문제지를 순서대로 나눠 가지고 문제를 읽었습니다. 제가 A~D, kolorvxl이 E~G, 6729skl이 H~J를 받았던 것 같습니다. 앉아있는 순서대로 문제지를 나눠 가졌습니다. 

제가 가장 먼저 잡은 문제는 A입니다. (기억은 안나는데 kolorvxl이 제가 A를 풀었다고 했습니다.) 범위를 보자마자 배열 A와 배열 B를 공통으로 사용하는 DP가 가장 먼저 떠올랐지만 여러가지 생각해보니 dp 포인터가 대각선에서만 움직이므로 선형 dp로 해결가능함을 관찰했습니다. (아마 그랬을겁니다.) 그래서 dp update가 선형 시간에 돌아도 됨을 확인하고 선형 시간에 동작하는 dp update 로직을 찾았습니다.

 

그 와중에 kolorvxl이 F를 빠르게 읽고 빠르게 구현했습니다. 실제로 전체 문제 중 가장 쉬운 문제였습니다. 그리고 시작한 지 7분만에 WA를 받았습니다.

F를 일단 6729skl이 디버깅하기로 하고 제가 A를 구현해 14분만에 AC를 받았습니다. I가 정수론이고 제가 팀에서 정수론을 가장 잘한다는 팀원들의 일방적인 주장에 따라 I를 고민하고 있었습니다.

 

kolorvxl이 I를 같이 고민하는 동안 6729skl이 F의 leading zero 반례를 하나 찾았습니다. 찾은 시점에 이게 마지막 남은 반례가 맞는 지 토의했습니다. 제가 세 번 고민 끝에 제출하자고 했고 18분에 AC를 받았습니다. 이 시점에서 13위까지 올라갔기 때문에 예상 이상으로 좋은 성적을 받을 수 있으리라 생각했습니다.

 

결국 I 풀이를 내기까지 오랜 시간이 걸렸습니다. 아무래도 근을 먼저 정해 두고 전개하는 관찰이 좋지 않았던 것 같습니다. 상수항이 이미 인수분해가 한 번 이상 된 꼴이라 더 말린 것 같습니다. kolorvxl이 근의 공식으로 가면 좋겠다고 한 뒤로 쉽게 해결되었습니다. 근의 공식을 쓰니 p가 가져야 할 restriction이 바로 보였습니다. p(p-4k)가 완전제곱이기만 하면 된다는 점을 바로 관찰했고, kolorvxl이 디테일을 챙겨 구현해 50분에 AC를 받았습니다. 다르게 식을 정리할 것 없이 p(p-4k)가 완전제곱인지만 봐도 충분했을 것 같습니다.

근의 공식 이전에 대칭이므로 개수만 알면 합은 쉽게 구할 수 있음을 알았지만 모든 경우를 탐색하는 것으로 개수를 알아내는 방법을 선택해 의미가 없었습니다.

 

I를 구현하는 동안 H를 읽었습니다. UCPC2024의 "산을 그리세요"와 비슷한 감성으로 dp를 챙겨보려 했습니다. 제법 오래 고민했던 것 같은 기억이 있으나 H를 언제부터 읽었는지 기억나지 않습니다. I의 AC 이후 kolorvxl과 함께 H를 고민했는데 제가 다른 문제를 잠시 보고 오는 사이 45도 돌리면 LIS가 되는게 아니냐는 풀이가 나왔습니다. 10초정도 보니 formal proof가 바로 보여서 kolorvxl이 구현을 시작했습니다. 6729skl과 함께 J를 읽었던 것 같습니다. 그 와중에 이분 탐색을 짜고 있길래 팀노트에 LIS 구현이 있다고 해서 빨리 구현을 완료할 수 있었습니다. 63분에 AC를 받았습니다.

 

H를 구현하는 동안 6729skl이 J를 읽고 그래프 모델링이 끝난 버전으로 설명해줘서 함께 고민했습니다. 기억하기로는 비슷한 유형의 문제를 연습 중에 깨달았던 것 같습니다. 2-path의 모임을 관리하면 200만개 이하의 에지만 관리해도 됨을 함께 관찰했습니다. 다만 degree 제곱의 합만큼 돌아야했는데 O(m^2)이 아닐까 하고 고민을 했습니다. 지금 생각하니 O(nm)에 바운드되는데 왜 관찰하지 못했나 싶습니다. kolorvxl이 구현했던 것 같고 67분에 AC를 받았습니다.

 

그리고 혼자 B로 넘어가고 팀원들이 C를 어떻게 잘 풀어왔습니다. C는 아직 풀이도 뭐도 잘 모릅니다. B,D,E를 번갈아 보며 뭐가 쉬운지 가늠했던 것 같습니다. 결국 B는 제가 문제를 잘못 읽어 예제가 왜 저렇게 나온지도 이해하지 못하고 마무리했고, E는 하나를 시간 축으로 삼는 구간쿼리 문제임을 짐작했지만 오프라인 쿼리를 써볼 생각을 하지 못했고, 마지막으로 D의 구성을 조금 생각해봤으나 결국 찾지 못했습니다. 

 

최종 스코어 6솔브 16등으로 마무리했습니다. 

진짜 중요한 얘기는 본선에서 나옵니다.