2022 ICPC Seoul Regional 본선 후기

Links

Problem

Scoreboard

대회 후기

예선 때와 마찬가지로 정말 준비를 못하고 대회를 쳤다. 고작 대회 직전에 팀 연습 2번이 다였다. 작년보다 더 잘하고 싶은 마음은 있었지만 사실 힘들다는 것은 어느 정도 알고 있었다. 그래도 정말 운이 좋게 작년과 같은 상인 동상을 수상할 수 있었고, 충분히 만족한다. 스코어보드는 아래와 같고 간단히 문제를 복기해보려 한다.

-------------------------------------------------------------
I: 쉬운 문제였고, 우리 팀이 제일 먼저 푼 문제이다. (12 min.)

J: Tree의 Euler Tour가 주어져 있을 때, leaf node들의 깊이의 합을 출력하는 문제인데, 역시 쉬운 문제였지만 long long을 안 써서 한번 틀렸다. (19 min.)

-------------------------------------------------------------

F: union-find + prefix sum을 사용하면 되는 문제였다. 쉬운 문제에 속하긴 했지만 생각보다 구현에서 말려서 오래 걸렸다. 지금 생각해보면 긴장했던 것 같다. (65 min.)

D: dp 문제인데, 풀이가 바로 떠오를 것 같지 않은 문제였다. 그럼에도 팀원이 잘 풀어주어서 다행이었다. (78 min.)

E: dijkstra algorithm을 살짝 변형하여 풀 수 있는 문제였다. 역시 어려운 문제는 아니었고, F를 내가 구현할 때 동시에 다른 팀원이 구현을 하고 있는 문제였는데, 둘 다 말리다가 D를 푼 이후에야 디버깅을 끝내고 맞을 수 있었다. 그래도 D가 구현은 어렵지 않아서 다행이었다. (86 min.)

 

여기까지가 비교적 쉬운 문제들이었고, 남은 문제들은 어느 정도 난이도가 있었다. 이때까지 3명 모두 어느 정도 긴장을 해서 그런지 본 실력이 안 나와서 순위가 쳐졌었는데, 이후에는 잘해준 것 같다.

-------------------------------------------------------------

K: 역시 dp였는데, 다른 팀원이 $O(n^3)$ dp식을 거의 완성해놓고 TLE여부를 고민하고 있었다. $n=500$이고 시간은 1.5초여서 간당하다고 생각했지만 될 것이라는 확신으로 내가 맡아서 구현하였고, Toggling을 넣어 공간 복잡도를 $O(n^2)$으로 줄여 맞았다. (109 min.)

C: 우리 팀이 가장 못하고 기피하는 것이 기하 문제인데, 이 문제가 생각보다 많이 풀려서 걱정이 됐다. 그래도 팀원이 이 문제를 꾸준히 잡아주었고, 구현도 깔끔하게 해서 한번에 맞았다. 그동안 대회에서 기하 문제를 거의 푼 적이 없는데 이번에 해결해서 기분이 좋았다. (146 min.)

L: 일단 문제 해석이 어려웠다... 정말 단순한 문제인데 description을 너무 어렵게 써놓은 느낌이었다. C를 다른 팀원이 구현하는 동안 풀이를 생각했는데, 생각보다 case-work가 있었다. 그래도 pigeon-hole principle을 잘 다듬어서 사용하니 풀이가 보였고, AC를 받을 수 있었다. (198 min.)

-------------------------------------------------------------

이때가 Freeze 직전이었고, 6등이었다. 그런데 이대로 아무것도 풀지 못하면 등수가 계속 떨어질 것이기 때문에 최소 1문제는 풀어야했다. 그래서 우리 팀이 선택한 문제가 A와 B이다.

A: 풀이는 생각보다 쉽다. Sprague-Grundy Theorem을 그대로 구현하면 되는데, 대각선 방향으로 문제가 구성되어 있어서 구현은 절대 쉽지 않았다. 내가 이걸 구현하기 시작했다.

B: 내가 A를 구현하는 동시에 다른 팀원들은 B 풀이를 생각하기 시작했다. 끝나기 30분전 정도에 풀이가 대강 나왔고 나는 A를 디버깅하고 컴퓨터를 넘겨줬다. 정확한 풀이는 나도 모르지만 엄청난 dp인 것 같다.

 

이렇게 두 문제를 동시에 잡았고, 종료 10분 전에 B를 제출했는데 RTE를 받았다. 디버깅을 10분간 했지만 결국 두 문제 다 풀지 못했다. 그래서 너무 아쉬웠는데, 끝나자마자 버그를 잡아서 더욱 아쉬웠다. 그래도 위안이 됐던 것은, 9위로 겨우 동상을 받을 수 있었고, 두 문제 중 하나만 맞았어도 여전히 동상이라는 사실이었다. 물론 두 문제 모두 풀었으면 좋았겠지만, 그러기에는 우리 실력이 부족하다고 생각한다.

 

3년째 이 대회에 참가해오고 있고,  그 중 한번은 예선에서 떨어져도 봤지만 이 대회는 참 매력이 있는 것 같다. 늘 대회가 끝나면 한번더..? 라는 생각이 든다. 특히 이번 대회는 지난 2년과 다르게 대면 대회를 진행했어서 더 재미있게 참여했다. 내년에는 군문제로 참여하지 못할 가능성이 매우 커서 더 아쉬움이 남긴 했지만 그래도 노력 대비 좋은 성적을 받았다고 생각한다. 복학 후 다시 ICPC에 참여할 수 있을지 모르겠지만 가능하다면 더 잘해보고 싶다!