2022 ICPC Seoul Regional 예선 후기

Links

Problem

Scoreboard

대회 후기

작년 ICPC 이후, 우리 팀은 내년에는 좀 더 잘해보자 라는 마인드로 1년을 다시 준비했다. 그런데 대회 시즌이 됐을 때, 다들 각자 바빠서 대회 준비를 잘하지 못했다. 비록 UCPC에서 수상을 하긴 했지만 서울대 쿼터를 뚫기는 정말 쉽지 않기 때문에 전날까지도 긴장을 했다. 대회 중에도 계속 걱정을 했는데 정말 다행히도 운 좋게 턱걸이로 교내 6등을 하며 본선에 진출했다. 대회가 끝나고도 계속 바빠서 후기 작성을 못했는데, 본선 전에는 복기를 하고 싶어 간단히라도 남긴다. 아래는 스코어보드이다.

 

우선, 올해 대회 문제 셋은 너무 평이했다. 9솔이면 9솔, 8솔이면 8솔, 모든 팀들이 푼 문제가 다 똑같다. 그 말은 문제들의 난이도 배열이 너무나 명확했다는 뜻이다. 우리 팀 또한 어렵지 않게 A, C, E, F, G, K를 먼저 푼 뒤에 남은 시간 동안 J, D를 고민했다. 그러다 J가 $O(N\sqrt{N}\log N)$에 될 것 같았고, unordered map을 활용해서 로그를 떼면 되지 않을까 하고 짰는데, TLE를 받았다. 그래서 알고리즘을 살짝 수정하여 $O(N\sqrt{N})$의 시간복잡도를 만들어냈고, AC를 받았다. 그리고 D는 풀지 못하고 대회가 마무리됐다. 

 

그렇게 평범하게 대회를 치른 줄 알았는데, 팀원들과 복기를 해보던 중 우리가 짠 J코드가 맞을까? 라는 생각이 들었다. 그래서 간단한 예제를 넣어보니 무려 37초나 걸렸다. 문제의 시간제한은 2초였는데, 아무래도 코너 케이스를 넣지 않은 것 같다... 조금 더 생각해 보니 우리의 풀이가 최악의 경우 $O(n^2)$이 된다는 것을 알 수 있었다. 이번에는 운이 참 좋았다고 생각이 들고, 다음 본선에서는 운보다는 실력으로 더 좋은 성적을 받고 싶다!