2025 ICPC Seoul Regional 예선 후기 (Road to ICPC APAC 2026 Part 3)

2025년 10월 11일 진행된 ICPC 서울리저널 온라인예선대회에 참가했습니다. 팀명은 Kpop Ssal Hunters, 결과는 6+413/10=#xx/291입니다.

(최종 스코어보드가 나온 뒤에 올리려 했는데, 빠른 시일 내에 안 나올 것 같아서 먼저 올립니다. 참가팀 291팀 중, 프리즈 이전 기준 15등이며, 제가 아는 정보를 기준으로 대회 종료 시점에서 이론적 최고 등수는 16등, 최저 등수는 23등입니다. 대충 20등 정도가 나올 것 같으며, 따라서 30등 이내 팀 전형으로 본선에 진출함은 확실합니다. 이 부분은 최종 결과가 나온 뒤 수정하도록 합시다.)

본선에 매우 안정적으로 진출하며 전에 돌았던 23/24 예선과 대략 비슷한 등수 퍼포가 나왔으므로 결과는 일단 만족스럽습니다. 다만 J와 C에서 패널티를 쌓아 등수가 깎이고 아슬아슬하게 E번의 구현을 못 끝낸 채로 대회가 끝나서 조금은 아쉽습니다.

대회 이전

대략 10시 반 정도에 팀노트를 완성하고 학교로 이동했습니다. 가는 길에 버스에서 Part 2 부분 블로그를 완성했습니다.

12시 정도에 팀원들을 만나서 밥을 먹고 학교에 들어갔습니다. 동방에 잠깐 있다가 팀노트와 필통만을 들고 회장으로 갔습니다. 회장은 제4공학관, 동방은 제1공학관에 있었는데, 위상적으로 같은 건물이라서 이럴 거면 왜 나눠 놨지 싶었습니다. 연세대 공학관은 언제 가도 어지럽습니다.

참가팀이 11팀으로, 나코더 송년대회보다 규모가 작았습니다. 어떻게 해야 ICPC 유입 규모를 늘릴 수 있을까요?

대 nflight님께서 예비소집일과 대회일에 회장에 인원수만큼의 음료수를 사두셨습니다. [[감사합니다]].

0:00~0:20

• 한국어 문제가 A, F, I번이었습니다. starbucks_americano가 머신 구성을 하고, 제가 A, juwonhyme이 F 혹은 I를 잡아 시작했습니다.
• juwonhyme이 I가 쉬운 문제라고 주장헀다가 취소했습니다.
• A번의 첫인상은 그리디, 그 다음 인상은 BFS-like 상태공간 탐색, 그 다음 인상은 제곱 DP였습니다. 세 번째 인상이 매우 좋은 인상이라 생각했고, 조금 생각하니까 풀이가 나왔습니다.
• starbucks_americano가 머신 구성을 끝낼 때쯤 저는 A의 풀이를 내서 머신을 가져왔습니다.
• 동시에 juwonhyme이 I 풀이의 빠른 구체화를 위해 starbucks_americano를 데려갔습니다.
• 제가 A를 제출했고 맞았습니다. (11분)
• juwonhyme이 아직 starbucks_americano와 I번에 대한 얘기를 하고 있어서, 저는 다른 한국어 문제인 F를 읽었습니다.
• F번은 조금만 생각하면 브론즈 구현 시뮬레이션 문제였습니다. 몇 가지 반례를 체크하고 구현했습니다.
• 15분쯤에 juwonhyme이 I를 풀었다고 했습니다.
• 제가 F를 제출했고 틀렸습니다. (17분)
• 틀리자마자 자명한 반례 두 가지가 떠올랐고, 머신을 돌려주기 전에 이를 수정해 제출해서 맞았습니다. (19분) I 구현을 위해 머신을 juwonhyme에게 전달했고, 저는 H번과 J번을 읽었습니다.
  • H번은 이전에 juwonhyme이 읽었는데, 아마 세그 문제일 것 같다고 주장했던 것 같습니다.

0:20~1:00

• juwonhyme이 H번을 어렵지 않게 풀 것이라 생각하고 일단 J번을 봤습니다.
• J번을 읽고 4-cycle을 모두 셀 수 있으면 된다는 것을 알아냈고, 팀노트에 4-cycle의 수를 세는 것이 있기 때문에 그냥 짜면 될 것이라고 생각했습니다.
• starbucks_americano가 C번이 쉬운 문제일 것이라 주장하면서 문제를 알려줬습니다. 실제로 어렵지 않은 문제일 것 같아 보였습니다만, 구현량이 많을 것 같아서 일단 넘기기로 했습니다.
• starbucks_americano가 D번이 쉬운 문제일 것이라 주장하면서 문제를 알려줬습니다. 저는 어려운 문제라고 생각했습니다.
• G번을 읽으려다가 별로 읽을 가치가 없다고 생각했던 것 같습니다.
• juwonhyme이 I를 제출했고 맞았습니다. (35분)
• juwonhyme에게 H를 돌려주고 제가 머신을 잡아 4-cycle 코드를 구현했습니다.
• 얼마 안 가 juwonhyme이 H를 해결했다고 주장했습니다. 그러고 나서 아마 starbucks_americano와 E번이나 C번을 읽은 것 같습니다.
• 제가 J를 제출했고 WA를 받았습니다. (45분) 프린트 요청을 하고 juwonhyme에게 머신을 넘겼습니다.
• 프린트가 오는 데 조금 오래 걸렸고, 그래서 그 동안 starbucks_americano에게 E의 설명을 들었습니다.
• 디버깅을 했고, 최초 사이클을 찾은 이후 사이클을 찾지 않고 있다는 사실을 알아냈습니다. 다시 E번으로 돌아가 고민했던 것 같습니다.
• juwonhyme이 H를 제출했고 맞았습니다. (56분)
• 제가 J를 수정했고 맞았습니다. (58분)
• 이 시점에 8등이었던 것으로 기억합니다.
• 이때를 전후로 Endgame이 유일한 6솔브로 1등을 하는 것을 직관했습니다. 연세대 폼이 꽤나 좋다고 생각한 동시에, 저희와 퍼포먼스가 비슷하거나 저희보다 우위일 것이라 생각했던 SEVERANCE 팀이 생각보다 아래에 있다고 생각했습니다.

1:00~2:00

• starbucks_americano와 C에 대해서 얘기했고, starbucks_americano의 주장대로 좌표압축을 적당히 한 뒤에 나이브를 돌리면 될 것이라는 결론을 내렸습니다.
• 적당히 좌표압축을 해서 전탐색을 하는 코드를 구현했습니다.
• 제가 C를 제출했고 RE를 받았습니다. (87분)
• 이 RE가 사실 TLE나 MLE에서 오는 것이라 생각해서 좌표압축의 강도를 늘렸고, RE를 받았습니다. (90분)
• 그냥 자명하게 RE가 나오는 부분이 있어서 이를 수정했고, 제출해 WA를 받았습니다. (94분)
• 이것을 출력해서 juwonhyme에게 던져주었고, RE를 수정하기 전 좌표압축의 강도를 늘린 것을 다시 풀어서 내라고 해서 그렇게 했습니다. 제출해 WA를 받았습니다. (100분)
• starbucks_americano에게도 한 부를 던져주었고, juwonhyme이 그냥 좌표압축 코드가 틀린 점을 찾아내서 좌표압축 부분을 다시 구현했습니다. 제출해 AC를 받았습니다. (114분)
• 이 시점에 12등 정도였던 것으로 기억합니다.

2:00~3:00

• 6문제를 풀어 B, D, E, G가 남아 있었습니다. 1등 팀이 7솔브로 E를 해결했고, 그 외 어떤 팀도 4문제 모두 해결하지 못한 상태였습니다. G는 잡으면 안 되는 문제라 판단, D는 문제를 이미 알고 있었으나 어렵다고 생각했습니다.
• 일단 juwonhyme이 starbucks_americano와 E를 잡고 있었던 것 같아서 설명을 들었습니다. 세그 내지는 모스 문제일 것 같았고, 어려운 문제라 생각했습니다.
• E를 juwonhyme에게 던져준 채로 starbucks_americano로부터 유일하게 모르는 문제인 B의 설명을 들었고, 10분 정도 고민했습니다. 그래프가 아래로 가다가 위로 가는 모양이 나와서 삼분탐색이 가능하지 않을까 싶었는데, 너무 어려운 것 같아서 E를 잡는 것이 더 좋다고 생각했습니다.
• 그래서 130분 정도 시점부터 starbucks_americano에게 B를 맡기고 juwonhyme과 E번을 잡았습니다.
• 20분 정도 이런저런 논의를 하다가, 150분경에 juwonhyme이 풀이를 낸 것 같다고 주장했습니다. 저는 대략 틀리지 않은 것 같다고 생각했고, juwonhyme이 155분경부터 구현을 시작했습니다.
• juwonhyme이 구현하는 것을 도와주면서 starbucks_americano와 B를 조금씩 봤습니다. 언젠가 SEVERANCE 팀에서 환호가 들리면서 B의 제출 수가 올라가서, B를 풀었구나 싶었습니다.
• juwonhyme이 구현을 끝내지 못해서, 178분경에 포기했습니다.

이후

• 프리즈 전 39등이었던 SEVERANCE 팀이 실제로 B를 해결해서 7솔브를 했다고 들었습니다. 프리즈 전 3등이었던 Endgame이 6솔을 했음을 확인하고 Endgame이 연세대 1등이 아니라는 점에 놀랐습니다. 세브란스는 강합니다.
• 프리즈 전 36등이었던 3Blue1Nutella가 SEVERANCE보다 근소하게 위에 있었어서, 저 팀도 매우 강한 것 같다고 생각했고, 실제로 프리즈 동안 6솔을 했다는 것 같습니다. 6솔브는 확정적으로 본선 진출이 가능한 것 같아서, 본선 팀이 적어도 4팀은 되므로 좋다고 생각했습니다.
• 그 다음 팀이 프리즈 전 56등이었던 Morgo Chobo 팀인데, 프리즈 전 3솔 최상위이지만 4솔브를 못했다는 것 같아서 아쉽습니다. 아슬아슬하게 본선에 진출하거나 아슬아슬하게 본선에 떨어질 것 같습니다.
• 특이하게도 프리즈 전 4솔팀은 8팀밖에 되지 않습니다. 5솔은 18팀, 3솔은 30팀입니다.
• 대회 전부터 floorsum과 Just Use CRT 중 어디가 더 강할지가 계속 궁금했습니다. 이번 예선에서는 CRT가 6솔브를 무려 168분으로 해냈으나, floorsum이 E를 88분에 해결해 7솔브로 이겼습니다.
• Ssalhur는 항상 개개인의 레이팅에 비해 강한 팀 같다고 생각했지만, 이번에 Endgame과 동급의 퍼포를 내는 것을 보고 확실히 많이 강한 팀이라 생각했습니다.
• 프리즈 전 기준 저희 팀 바로 위의 팀이 Just Reboot JungSangHwa 팀입니다. 팀명을 저희와 비슷한 방법으로 작명한 것 같아서 기억에 남습니다.

분석

• 5솔브까지 정말 잘 했습니다. 초반 1시간의 폼은 매우 이상적으로 나왔다고 생각합니다.
• C에서 4번 틀리고 25분 정도를 버린 것이 가장 큰 실책이었습니다. 순전히 제 잘못이라서 + E가 몇 분 차이로 구현이 안 나왔기에 팀원들에게 약간 미안합니다.
• 8/9번째 팀연습과 같이, 초반에 강하고 중반에 패널티를 많이 쌓는 그림이 아무튼 다시 그려졌습니다. 이번에는 6솔브-7솔브 사이 난이도 갭이 컸고 5솔브가 그만큼 빨리 되었기 때문에 그런 그림이 별로 큰 음의 효과를 주지 않아서 다행입니다만, 아직 팀연습은 많이 해야 될 것 같습니다.
• 근데 어쨌든 아챔 진출이 - 물론 쉽지 않긴 하지만 - 불가능하지는 않은 정도의 등수가 나와서, 희망을 가지고 열심히 팀연습을 돌 것 같습니다.

이제 진짜 중간고사 시험 공부를 해야 합니다. 10월 26일에 있는 런 모의대회 전까지는 팀연습을 쉬어가고, 그 이후에는 다시 주 2..3번 정도 팀셋을 돌 예정입니다.

역시나 정진합시다.