2023 ICPC Seoul Regional 예선 후기

서론

 

올해도 어김없이 ICPC에 출전했습니다. 올해의 팀 구성은 kwoncycle, petamingks로 kwoncycle과는 1학기 초에, petamingks와는 팀원 한 명이 미정이던 시기에 퍼플을 찍어와서 같이 팀을 하기로 했습니다. 2학기에 동아리로 복귀하신 kkpos0206 선배가 SCPC 4등상을 비롯한 여러 뛰어난 퍼포먼스를 보여주셨으나, 우선 두 명과 말해놓은 것이 있기에 kkpos 선배와는 내년 대회를 같이 나가게 될 것 같습니다. 올해 팀원 둘은 여러모로 비슷한 부분이 많은데, 둘 모두 Codeforces 탑레가 오렌지라는 점, MO 출신이라는 점, PS에서도 그래프나 자료구조보다는 DP나 수학에서 강점을 가진다는 점 등이 있습니다. 차이점이라고 하면 petamingks는 python을 사용하기 때문에 코딩이 비교적 빠르다는 점, 수학 외의 분야에서 kwoncycle이 조금 더 낫다는 점이 있습니다. 하지만 둘 다 유의미한지는 잘 모르겠습니다. 아직 팀 연습을 충분히 하지 못해 전략은 딱히 없으나, 아마 쉬운 문제는 각자 풀고 어려운 문제는 두 명이 관찰, 제가 구현을 맡아서 하게 될 것 같습니다. 팀명은 저희의 당찬 포부가 담긴 것으로, 셋 모두 e-sports를 즐겨 보는데 T1 팬인 petamingks가 흔쾌히 허락해주어서 정할 수 있었습니다. 

 

대회 중

 

이번에도 포스텍은 전력 몰빵식 팀 구성을 했기 때문에, 예선은 여느때와 같이 긴장감 없이 쳤습니다. 과연 3시간 내내 여유롭게 칠 수 있었을까요?

 

~0:11

문제지 프린트를 기다리면서 한글 문제를 먼저 읽었습니다. D와 C를 읽었고, 더 쉬운 C 먼저 코딩에 들어갔습니다. kwoncycle이 잡았는데, python으로 짰지만 반올림을 할 줄 몰라 시간이 조금 지연되었습니다. 하지만 다행히 별 문제 없이 맞을 수 있었습니다.

 

~0:18

petamingks가 D 풀이를 찾아 코딩에 들어갔습니다. python이라 코딩 시간은 짧았지만, 실수가 있어서 한 번 틀리고 맞았습니다. 

 

~0:30

저는 딱 하나 남은 한글 문제인 G를 읽었습니다. 문제는 어렵지 않았는데, 나이브가 도는게 굉장히 애매한 제한이어서 고민하다 한글 문제임을 믿고 짰습니다. 빠르게 짠 후 냈지만, TLE를 받았습니다. 이후 자잘한 조정을 2번정도 더 했지만 모두 TLE를 받아서 풀이를 고쳐야 한다는 결론이 나왔습니다. 저는 머리가 하얘졌기에 kwoncycle에게 이를 맡기고 풀린 I와 J를 보러 갔습니다.

 

~0:53

petamingks가 K 풀이를 찾아서 짰지만, 또 TLE를 받았습니다. -파- 당했을 것이라 추측한 후 제가 같은 코드를 C++로 옮겨서 짰지만 또 TLE를 받았습니다. 여기서 상수를 더 줄이려면 map을 unordered_map으로 바꾸는 방법과 상수에 1/2을 붙이는 방법이 있었고, 후자로 짰더니 다행히 맞을 수 있었습니다.

 

~1:48

kwoncycle은 G 풀이를 찾았다고 선언 후 꽤 긴 구현에 들어갔습니다. 전처리는 제곱 정도로 조금 더 빠르게 하고, 답을 구할 때 이분탐색을 사용해 제곱 미만으로 푸는 풀이였던 것 같습니다. 그 동안 저는 I, petamingks는 J를 봤습니다. J는 제가 해석을 대충 해서 줬지만 다행히 회전이 되지 않는다는 점을 비교적 빨리 알아차렸습니다. 뭐라도 하려면 각 열마다 DP를 해야 하는데 이게 \(O({{N^3}\over{6}})\)이었고, 이후 과정도 쉽지 않았습니다. I는 비전형적인 제곱 DP였습니다. 다행히, 그리디한 성질을 때려맞추기 쉬운 편이라 우선 찍고 증명을 해 풀이를 찾을 수 있었습니다. 컴퓨터를 기다리는 동안은 내려갈 대로 내려간 (학교 1등도 아닌 ㅋㅋ) 순위를 보며 마음을 다잡는 시간을 가졌습니다. 이후 kwoncycle이 G를 성공적으로 맞아왔고, 제가 I 구현에 들어갔습니다.

 

~2:00

I 코딩은 어렵지 않았고 예제도 잘 나왔지만, WA를 받았습니다. 조금 고민했지만 아무리 봐도 틀린 부분이 없었습니다. 다행히 kwoncycle이 J의 뒷부분 풀이를 찾았고, J에 필요한 DP를 짠 후 컴퓨터를 넘겼습니다.

 

~2:31

스코어보드 프리즈 1분 뒤 kwoncycle이 J 코딩을 마쳤고, 다행히 한 번에 맞았습니다. 다른 문제를 풀 수 있는 시간은 아니어서, 모두가 I의 오류를 찾는 데에 집중했습니다.

 

~2:42

petamingks가 I 코드의 오류를 찾아냈습니다. DP값을 -INF로 초기화해야 하는데 0으로 초기화한 것이 이유였습니다. 평소라면 안 할 실수인데.. 어쨌든 기존 코드에 한 줄을 추가해 맞았습니다.

 

~3:00

남은 문제를 잠깐 둘러보았습니다. A는 지문이 길길래 읽지 않았고, E는 쉽지만 짜기 싫은 기하였습니다. 후에 들은 바로는 A도 쉽지만 지문에 문제가 있었다고 합니다. 이후에는 반성과 성찰의 시간을 가졌습니다.

 

대회 후기

 

또 엄청나게 절었습니다. G에서 나간 멘탈을 잡기 쉽지 않았던 것 같습니다. 컴퓨터를 좀 잡긴 했지만 실질적으로는 0솔과 다름이 없었습니다. 문제 전반에 걸쳐 논란이 있긴 한데, 결국 잘하는 팀은 잘하기에 그냥 연습이 더 필요할 것 같습니다. 하지만 팀원들이 버스를 태워주어서 & 문제 셋 이슈로 인해 등수 자체는 나쁘지 않게 나왔습니다. 다만 올해는 강한 팀이 많다기보다는 저희 팀과 비슷한 전력의 팀이 많은 것 같아서 수상 & 플레이오프 진출을 노리기 위해서는 실력과 멘탈을 모두 잡을 필요가 있어보입니다. 또한, 이번에는 포스텍 본선 진출 팀이 3팀으로 늘었습니다. 제가 입학한 후로 1팀 -> 2팀 -> 3팀 순서로 늘고 있는데, 나름 긍정적인 지표 같아서 좋습니다.

 

모두 수고하셨습니다! 본선에서 만나요~