대회후기: 2020 ACM-ICPC Seoul Regional 예선

대회를 너무 캐주얼하게 진행했더니 캐주얼하게 망해버렸다.

 

원래 같았으면 대충 윗공대에서 치렀을텐데, 두 대의 카메라를 동원해 Zoom에 접속해 컴퓨터 화면과 팀원들이 나오도록 설치해 둔 상태로 대회를 진행해야 한다는 번거로운 온라인 대회 규칙 때문에 서울대입구역의 토즈 스터디룸을 빌려 대회를 진행하게 되었다.

 

대회에서 시도한 문제 순서대로 정리하겠다.

---

I: Project Teams

스코어보드를 참고해 제일 쉬운 문제인 I를 먼저 잡았다. 문제를 다 읽기도 전에 정렬 후 앞뒤로 짝지어주는 well-known 풀이가 떠올랐다.

E: Cycle Game

그래프를 그려나갈 때, 사이클이 생기는 시점을 감지하면 된다. 읽자마자 UFDS를 떠올렸으나, 문제를 잘못 이해한 Nyso가 다른 방법으로 시도한 후 한번 실패한 이후에야 UFDS를 이용해 해결하였다. 시간이 낭비되어 아쉬운 문제이다.

 

이 문제 해결 이후 Nyso는 K를, MathAmp는 L을, 나는 F를 잡았다.

K: Road Reconstruction

이 문제도 이상한 방법으로 뻘짓을 하고 있다가, F를 잠시 접어두고 함께 합류한 내가 Nyso의 지적을 듣고 Dijkstra를 그냥 쓰면 된다는 것을 깨달았다.

L: Sliding Coins

MathAmp가 그리디한 방법으로 풀고 있었다. 왠지 그리디가 안될 것 같다는 예감이 들었었는데, 원래 코드가 하도 버그가 많았던지라 버그 때문에 WA를 받은 줄 알고 디버깅으로 시간을 많이 버렸다. 결국 Nyso와 MathAmp가 함께 DP를 이용해 해결하였는데, 주어진 문자열에서 분리되는 길이 $n - 2$짜리 문자열을 $A$, 길이 $2$짜리를 $B$라고 하면, $D_{i, j}$를 $A$의 $i$번째까지와 $B$의 $j$번째까지 사용해 목표 문자열에 맞출 수 있는지의 여부로 정의한 후 $O(3n)$의 DP를 돌면 된다.

 

F: Escaping

어렵지 않은 문제인데 이상한 접근만 하다가, 대회 종료 직전에서야 비스무리한 방향성을 잡았다. 대회 종료 직전에 정말 대충 코딩한 소스를 제출해 보았으나, WA를 받고 마무리하였다.

 

도둑이 한 방향으로만 도망갔을 때, 탈출이 가능한지 확인하면 된다고 한다.

---

결론

99등으로 마무리했다.

우리 대학 19팀 중 최하위이다.

세명이 다 최상의 실력을 발휘했다면 5문제, 혹은 6문제까지도 해결 가능했을 대회인데, 4문제밖에 풀어내지 못해 아쉬운 느낌이 있다.

사실 더 높은 성적을 내려면 ICPC 형식으로 팀 연습을 진행했어야 한다.

세 명의 문제풀이 역량이 엇비슷한 상황에서 컴퓨팅 파워(?)의 분산을 효율적으로 하지 못한 탓이 크다고 생각된다.

 

팀 역량을 키우던가 개인 역량을 키우던가... 둘 다 키우던가 하자..!