2025 ICPC 서울 예선

https://youtu.be/EPebm2XM0-U?si=AoF1G7Jpb8saTcQN

 

 

어찌보면 올해 가장 중요한 이벤트 중 하나인 ICPC 서울 리저널이 시작되었다. 특이사항이라면 부산에서 본선을 개최하지만 이름은 서울 리저널이라는 점이다. 리저널로 월드 파이널 진출을 가르던 과거와 다르게, 현재는 2024년에 등장한 아시아 챔피언십으로 가는 등용문의 역할을 하고 있다. ICPC라는 이름의 무게와 명예는 아직 건제하며 많은 이들이 도전하고 있다.

 

팀

학기초, 입학하기 전부터 어느정도 알고 있었던 도훈(dohoon)형과 함께 팀을 하게 되었다. 그 후 코드포스 오렌지 신입생인 누스(gmroh06)을 영입하여 팀 NGM이 결성되었다. 그러나 도훈이형의 군대 이슈 때문에 팀은 해체되게 되었고, 새로운 팀을 구해야했다. ALOHA 학술부장이며 PS 입문 1년만에 퍼플을 단 레전드 재능충 성준이형(jsj0412)을 다른 팀에서 빼돌리는 것에 성공하여, 팀 NJG가 탄생하였다.

 

팀명

NJG (Nus Jsj Gubshig) 개인적으로 개짜치다 생각하는데 둘이서 자꾸 이상한거 들먹이면서 주장하길래 어쩔 수 없었다.

 

팀원 소개

jsj0412 - PS에 입문한지 얼마 되지 않았지만 굉장한 실력자이다. 쉬운 문제를 빠르게 풀 수 있고, 플레~다이아 하위 정도의 문자열을 굉장히 잘 푼다. 팀에서 보드게임 중독자, 최연장자, 문자열/기하 담당을 하고 있다.

 

gmroh06 - 영재고 출신 코드포스 오렌지이다. NGM에서도 합을 맞쳐본 바가 있고 숭고한도 나와 같이 나갔었다. 머리가 좋기에 애드혹, 구성적, DP, 그리디 등등에 강하고 아이디어를 굉장히 잘 낸다. 팀에서 일진, 얼굴담당, 능지담당을 하고 있다.

 

gubshig - OI를 어느정도 열심히 준비하여 자료구조, 그래프, DP, 웰노운 등에 강하다. 팀에서 십덕, 패널티쌓기, 머신 낭비하기, 뇌절하기, 웰노운을 담당 하고 있다.

 

각자 잘하는 분야가 명확하고 적당한 셋이 나왔을 때 잘 소화해 내리라 생각한다. 그러나 결성한지 얼마 안되기도 하였고, 팀연습때 (주로 내가한) 각종 병크가 발생하여 팀 퍼텐셜이 어느정도인지 모르는 상태다. ICPC 예선은 30등 이내에 드는 것을 목표로 하였다.

 

예선 당일

팀노트는 justicehui의 뉴비용 팀노트에 내가 요청한 자료구조들 몇개를 추가하여 만들었다. 사실, 기하와 문자열을 제외하면 팀노트를 사용할 일이 거의 없는 것 같아서 크게 신경을 쓰지 않았다.

 

예선은 3시간 대회이고, 등수보다는 통과하는 것이 중요하기에 특별한 전략을 준비하진 않았다. 쉬운 3문제부터 빨리 풀고, 나머지 문제를 각자 잘하는 사람한테 넘겨주기를 할 예정이었다.

 

개인적으로는 ICPC에서 문제의 구현에 대해 많은 생각을 해보았다. 코딩을 할 때 어떤걸 짜야할지 고민하는 시점이 있으면 안되는 것 같다. 그러기 위해서 구현의 큰 틀 뿐만 아니라 세부적인 동작 (어떤걸 함수로 뺄거고 이거에선 어떤걸 어떻게 구할것이며 좌표압축은 어떤걸 해줘야 하고 등등...)을 전부 정하고 어느정도 종이에 쓴 다음 구현하는 연습을 연휴동안 하였다. 놀랍게도 이 방법은 구현 구체화 + 구현 시간을 합쳐도 기존에 내가 구현하던 시간보다 월등히 빨랐고, 이를 이번 대회에 적용해보고자 하였다.

 

00:00~00:17

나는 A를, 성준이형이 F를, 누스가 I를 잡았다. A는 보자마자 DP인 것을 알았고, 식만 세우고 바로 코딩에 들어가면 되었다. 성준이형이 F 개쉽다고 하길래 일단 넘겨주고 A 구현을 구체화하고 있었다. F를 몇번 틀린 후 많조분임을 깨닫고 다시 풀이 구체화에 들어가서, 내가 머신을 잡고 A를 짜서 맞았다. 이후 한번 더 틀리고 F를 맞을 수 있었다. 대회 초반부에 패널티가 망했지만 그래도 20분에 2솔이 나왔기에 크게 걱정하진 않았다.

 

00:17~00:40

나는 A를 풀고 남은 문제를 읽다 H가 할만해보여 고민하기 시작했다. 성준이형은 J를 잡았고, 누스는 I 풀이가 나왔다. H는 전이가 어떤 영역에 대해 발생할 것이고, 이는 45도 돌리면 2d쿼리가 되서 스위핑 하며 세그를 쓰면 될 것 같았다. 풀이를 구체화해보니 최대 15분 정도 구현이 걸릴 것이라 예상했다. 누스가 먼저 머신을 잡고 있었어서, 누스가 다 짜면 머신을 넘겨받을 계획이었다. I를 제출했지만 틀려서 프린트 요청을 한 후 나는 H를 짜기 시작했고, AC를 받았다.

 

00:40~01:28

J가 그래프 문제여서 내가 푸는 것이 나을것이라는 판단 후, 성준이형과 누스는 I의 디버깅을, 나는 J의 풀이를 고민했다. 옆에서 I가 대체 왜 틀렸는지 모르겠다 같은 소리가 나와서 조금 불안했다. J를 좀 생각해보니 그래프에서 4-cycle과 동치임을 알았고, 이걸 성준이형한테 맞는 것 같다고 말해보니 "아니 이거 내가 종이에 써놨는데? 왜 안읽음?"...?? 4-cycle을 찾는건 차수에 대한 루트질을 하면 된다는 것이 유명하기에 나는 풀이 구체화에 들어가고 누스는 I 디버깅을 하고 있었다. 그 후 머신을 넘겨받고 J를 짰지만 WA를 받았다. 성준이형이 I에 값들이 유니크(나는 문제를 몰라서 뭔소린지 잘 모름)해야한다 어쩌구 해서 std::vector을 std::set으로 바꾸니 AC를 받을 수 있었다 (수정. 이 발견은 누스가 독자적으로 진행하였다고 한다). 그 후 누스는 C를, 나와 성준이형은 J 디버깅을 시작했고 성준이형이 a[0]을 더해야하는데 L[a[0]]을 더하고 있었다는 병티멀을 발견했고 이를 수정하니 바로 AC를 받을 수 있었다. 이 시점에서 5솔이었고 스코어보드 상위에 있었다.

 

01:28~02:09

스코어보드를 보고 풀어볼만한 문제는 B또는 E라 생각했으나 B는 성준이형이 모르겠다 했고 E는 내가 문제를 잘못읽어서 좌표가 다 다른 것도 몰랐고 W, H가 고정인 것도 몰라서 개어렵다 판단 후 던졌다. 그래서 같이 C를 보고 있었다. 누스가 BFS를 하면 될 것 같다고 했고, 나는 맞는 것 같아서 짜보라고 했다. 01:54에 WA를 받았고 구현은 맞는 것 같았는데, 보는 좌표가 +-5여야 한다는 관찰 후 이를 수정하고 AC를 받을 수 있었다.

 

프리즈전 20등이지만 패널티가 다소 망했고 7솔팀도 좀 등장했을 것 같아 아마 등수는 내려갈 것 같다. 어찌되었든 대학교 1등 전형으로 본선 진출은 확정되었다.

 

복기

성준이형이 다소 실직한 면이 있는데, 대회에 문자열 문제가 하나도 등장하지 않았던 점이 좀 컸다.

문제 배분은 좀 더 좋았을수도 있었지만 이정도면 나쁘지 않았던 것 같다.

가장 개선해볼만한 점은 패널티다. F를 초반 3틀한 것이 너무 아쉬운데, 내 생각에 쉬운 문제여도 많조분 냄새가 나면 검토를 꼼꼼히 한 후 제출해야할 것 같다. 그 외에는 팀노트 보강이다. 아무래도 본선에는 좀 더 강한 팀노트가 필요하지 않을까?

구현 연습한 것이 어느정도 도움이 되었던 것 같아 다행이다. 아쉽게도 셋에 구현이 크게 어려운 문제는 없었지만말이다.

 

우리팀이 생각한 셋의 난이도이다.

F 실버3
A 실버1
I 골드2
H 플4
J 플4
C 플3

 

전체적으로 셋이 6솔까지는 쉽지만 그 이후부터는 어려워서 팀의 기량을 확인하기에는 적합하지 않았던 것 같다. 3시간셋이기도 하고... 그래서 본선까지는 팀연습을 많이 해야한다. 

 

이후 곧 군대가는 gggkik의 피날레를 하고 귀가하였다.

 

우리 팀의 목표는 우선 아시아 챔피언십 진출이다. 그 별에 닿을 수 있을까?