2024 ICPC 후기

2024 ICPC Seoul Regional 후기

우선 종경이의 후기다. 자세하고 풍부하게 잘 써줘서 나는 내 시점 부연 설명을 해보겠다.

 

 

예선

https://www.acmicpc.net/category/detail/4344

 

나는 여느 때처럼 쉬운 문제들을 잡고 풀었다. E는 어려울 게 없었고, F는 선분 교차 판정을 해야 했다. 그런데 구면 좌표에서 직교 좌표로 변환하는 게 영 찝찝하니까, 구면 좌표계에서는 선분 교차를 특별하게 할 수 있나 오래 고민했다. 그러다가 하나 구현해 봤는데 예제가 안 나오길래 그냥 디버깅 안 하고 버렸다. 그러고 좌표 변환을 그냥 하니까 바로 맞아서 시간이 아까웠다.

 

이후에는 I를 오래 고민하다 포기했고, 그나마 내 스타일인 B를 잡았다. B는 뒤에서부터 노드를 추가하면서 트리와 답을 관리해줄 수 있는데, 이때 트리가 특수해서 트리를 답에 비례하는 시간으로 조작할 수 있는 것 같았다. 답이 어느 정도 바운드된다는 걸 민철이하고 같이 추론해서 가능성이 있는 풀이였다. 종경이의 A 구현이 거하게 말리고 대회 종료 N분 전에 내게 머신이 왔다. 풀이가 어느 정도 구체화된 상태에서 퍼솔의 부푼 꿈을 안고 코딩을 시작했지만, 마지막 디버깅에 실패하며 아쉽게 코드를 완성하지 못했다. 대회가 끝난 후 다시 차분하게 봤더니 틀린 부분을 금방 찾을 수 있었고, 최근 문제가 업로드된 백준에서 AC를 받아 더욱 아쉬움이 커졌다.

 

 

본선

https://www.acmicpc.net/category/detail/4348

 

작년에 본선 당일 잠을 충분히 자지 못한 것이 후회로 남아서, 이번에는 내가 호텔 예약을 강하게 추진했다. 이는 지금도 잘한 일이라고 생각한다. 호텔이 가깝고 좋아서 불필요한 컨디션 낭비를 최소화할 수 있었고, 덕분에 팀원 모두 대회 종료 전까지 크게 지치지 않았다.

 

이번에도 내가 쉬운 문제인 A를 잡고 시작했다. 금방 코딩을 마치고 가벼운 마음으로 제출했는데 틀렸다. 코딩 실수는 딱히 없어 보였고, 같은 시간에 일어나는 이벤트도 내가 짠 코드에서는 잘 처리되는 것처럼 보였다. 일단 이 팀에서 내가 첫 문제에서 막힌 적이 사실상 처음이라 멘탈이 급격히 나갔다. 원래라면 A를 맞고 내가 B까지 읽었어야 하지만, 우선 A를 고치기 위해 B를 종경이에게 넘겼다. 내가 A에서 갈피를 못 잡는 동안 종경이도 B를 깔끔하게 풀지 못했다. 난 고민하다 도저히 모르겠어서 민철이를 불렀고, 같은 시간을 따로 처리하라고 해서 수정했으나 틀렸다. 내가 또 헤매고 있으니, 민철이가 와서 한 줄을 추가하고 맞았다. 나는 왜 이 줄을 추가해야 하는지를 대략 30분 후에 깨달았다. 이렇게 A, B에서 누구보다 많은 페널티를 쌓으면서 초반 페이스가 완전히 박살났다.

 

이후 나는 C, D를 마저 읽었다. 종경이가 L이 쉬운 기하라면서 가져왔는데, 나는 앞에서 크게 말린 터라 조금 자신이 없었다. 그걸 캐치했는지는 모르겠지만 별로 안 어려우니까 본인이 짜겠다며 다시 가져가서 곧 맞았다. 아무튼 나는 D가 어려운 문제임을 깨닫고 C를 계속 고민했다. 일단 각 사분면에 존재하는 색들을 알고 있을 때 해당 조건이 홀의 결혼 정리와 같다는 것은 바로 알았다. 홀의 정리를 쓰려면 색 집합의 합집합을 구해야 하고, 이를 빠르게 할 수 있는 자료구조로 비트셋을 떠올렸다. 비트셋을 쓰면 문제에 필요한 스위핑도 $\frac{N^3}{64}$에 빠르게 할 수 있었다. 물론 C의 악랄함을 아는 지금은 어림도 없다는 것을 알지만, 당시에는 충분히 시도해 볼만한 풀이였다. 우선 적당히 짠 코드는 TLE를 받았고, 나는 상수 차이라고 생각해 메모리를 줄이고 캐시 히트를 높이도록 코드를 고쳤다. 그러나 최대한으로 최적화했다고 생각한 코드조차 TLE를 받으며 잠시 소강상태에 들어갔다.

 

풀이가 망한 C를 잠시 놓고 기하 문제라 추정되는 E를 고민하기 시작했다. 막 convex한 뭔가를 찾아야 한다는 건 알겠는데 구체화도 잘 안되고, 위쪽 뚜껑만 고려하면 되는 게 아니라 바닥을 지나는 경로도 고려해야 한다는 사실에 좌절했다. 이쯤에서 E도 포기하고 C를 다시 잡았다. 나는 비트셋 풀이에서 벗어나지 못하고 있었는데, 종경이가 갑자기 4개만 보면 되는 거 아니냐고 해서 생각해보니 맞았다. 그래서 비트셋을 전부 크기 4짜리 array로 수정했다. 이제 TL은 어느 정도 여유가 생겼다고 생각해서, 구현을 틀리지 않기 위해 최적화가 덜 되었지만 구현이 간단한 코드를 베이스로 수정했다. 그런데 제출해 보니 또(!!) TLE가 나왔다. 미쳐버릴 노릇이었다. 마지막으로 남은 방법은 최적화된 코드에서 비트셋을 뜯어내는 것이었고, 수정은 금방 했으나 예제가 나오지 않았다. 그렇게 또 한참 동안 코드를 뚫어져라 보다가 결국 오류를 발견해서 고쳤더니 AC가 나왔다. 대회 종료 20분 전이었다. 이 문제에 너무 오래 끌렸다는 사실에 엄청나게 분했지만, 그래도 끝까지 못 풀지 않았다는 것에 가슴을 쓸어내렸다.

 

남은 시간 동안 H의 디버깅을 성공해야 확실하게 수상권에 들 수 있었다. 그런데 다행히 금방 고치고 맞더라. 진짜 둘다 유관력이 상당하구나 싶었다. 그래서 수상은 어느 정도 예상했고, 이제 서울대 팀이 우승을 할지, 그리고 어떤 상을 받을지가 관건이었다. 우리 팀의 최종 순위는 전체 8등, 서울대 6등으로 동상을 수상할 수 있었다. 대성호가 우승을 차지한 상황에서 우리가 얻을 수 있는 거의 최선의 결과를 얻은 것이다. 내가 고점이었다면 E까지 풀고 은상을 노려볼 수 있었겠지만, 더 망할지도 모르는 와중에 동상은 나에게 과분한 결과였다.

 

 

감상

 

팀원들이 정말로 잘해줬다. 평소 팀연습을 하면서도 개개인의 레이팅보다 훨씬 실력이 뛰어난 팀이라고 느꼈고, 이를 대회에서 증명해 낸 것 같아 기쁘다. 한 명이 제 역할을 못 하는 와중에도 각자 1.5인분씩을 맡아준 팀원들에게 정말로 고맙다. 지난 6개월 동안 함께 대회를 준비하면서 정말 즐거웠고, 덕분에 높은 곳을 꿈꿀 수 있었다.

 

종경이의 후기를 보고 나서 갑작스러운 고민이 생겼다. 내가 군대를 1년만 미루고 이 친구들과 내년에도 해볼까 하는 것이다. 올해 여러 대회들에서 아쉬운 점들이 있었고, 이 페이스대로 1년만 더 열심히 CP를 한다면 내년에는 만족할 만한 성과가 나올 것이라는 생각이었다. 또, 내가 군대를 갔다 온다면 지금만큼 잘 맞고 만족스러운 팀을 구하지 못할 가능성이 크다. 매번 같은 멤버로 대회에 참가하는 팀들이 부러웠던 것도 있고, 지금 팀으로 일 년만 더 합을 맞추면 내년에는 더 잘할 자신이 있었다. 무엇보다 그냥 지금 팀이 좋아서 잃고 싶지 않았다.

하지만 군대를 미루는 것의 디메릿은 널리 알려진 사실이고, 만약 내년에 아시아 퍼시픽이라도 나가게 된다면 1년 미루는 것으로 끝나지 않는다. 또, 내년 초에 공군을 가기 위해 했던 모든 노력들이 허사가 되고, 앞으로의 인생 계획이 조금 크게 틀어진다.

 

이 문제를 진지하게 고민하기 위해 요 며칠간 가족, 친구, 주변인들과 많은 대화를 나눴다. 또 그만큼 혼자 고민하는 시간을 가졌다. 그래서 내가 내린 결론은, 원래 계획대로 군대에 가는 것이다. 지금 팀을 놓치는 것이 매우 아쉽고 슬프지만, 팀에 끌려가듯이 이 판에 남는 게 별로 바람직하지 않다고 느꼈다. 군대에서 실력을 갈고닦고 나와, 내가 팀의 구심점이 되고 싶다. 물론 그때는 내가 원하는 수준의 팀을 꾸리지 못할지도 모른다. 그래도 그냥 내 실력을 꾸준히 보여주면 언젠가 다시 좋은 팀원들을 만나게 될 것이다.

 

그래도 며칠 동안 갑자기 추가될 일 년을 상상하면서 행복했다. 작별이다, 최강. Farewell, BitsetNapsac..