UCPC 2021 예선 참가 후기

64등

작년에 이어서 올해도 UCPC를 참가했다. 팀원은 yooshnn, openingsound였고, UCPC 참가 모집 공지가 올라오고 나서 학교 피아노 동아리 내에서 팀원을 구했다.

 

작년 예선은 백준 서버가 터지는 바람에 조금만 노력하면 본선에 진출할 수 있었는데, 올해는 상대평가로 상위 50여 팀만 진출할 수 있기 때문에 컷이 많이 빡셀 것이라고 예상했다. (수정 : 결국 60팀이 진출했다고 한다)

 

세 명 다 알고리즘에 투자하는 시간이 많이 줄었기 때문에 별도의 팀 연습은 하지 않았다.

 

 

타임라인

먼저 시작하기 전에 UCPC 예선에서는 전통적으로 A번에 가장 쉬운 문제가 나온다고 알고 있었기 때문에 팀원 3명이 일단 A번을 읽고 나서 자신 있는 사람이 구현을 진행하고, 나머지 9문제를 3문제씩 나눠서 읽기로 했다. 내가 담당한 문제들은 E, F, G였다.

 

 

0:20 A AC(+3)

문제를 읽어보았고, 구현하다가 실수할 여지가 꽤 많다고 생각했다. openingsound가 구현을 맡겠다고 해서, 내가 담당한 문제들을 읽으러 갔다. 3번 틀리고 맞은 걸 보니 꽤 말렸던 것 같다. 이 때 나는 E와 F가 상당히 어려워보여서 코드포스에서 볼 수 있을 법한 구성적 문제인 G를 잡았다.

 

 

0:50 B AC

yooshnn은 H, I, J를 읽어보고 나서 시간이 오래 걸리고 복잡한 문제들 위주라고 판단해서 앞쪽 문제들을 보기 시작했고, B를 풀어주었다.

 

 

1:03 C AC

그 무렵 나는 내가 작성한 G 코드의 반례를 찾아냈고, 생각보다 어려운 문제라고 판단해 꽤 많이 풀려 있었던 C를 보고 브루트포스가 가능할 것이라고 생각했다. openingsound가 C를 구현해주었고, 한 번에 맞을 수 있었다.

 

 

1:08 G WA

openingsound가 C를 잡고 있고, yooshnn이 H를 잡고 있는 동안 나는 다시 G로 돌아와서 그럴듯하다고 생각했던 풀이를 작성해서 제출했다. WA가 나왔고, 지금 다시 생각해보면 이 풀이는 상당히 허점이 많은 풀이였다.

 

 

1:15 H AC

yooshnn이 DAG dp 문제인 H를 맞아왔다. 이 때까진 순위가 생각했던 것보다 높아서 본선 진출이 가능할 수도 있겠다고 생각했다.

 

 

1:51 G AC(+1)

G 문제의 스페셜 저지를 만드는 것은 어렵지 않았기 때문에 스페셜 저지를 구현해놓고 여러가지 풀이를 시도해봤다. 이 때, 소수를 이용해서 등차수열을 만드는 풀이가 작은 소수 범위에서는 제대로 되지 않고, 큰 소수 범위에서는 제대로 작동한다는 것을 깨달았다. 몇 번 돌려보고 나서, 소수가 전부 N 이상이면 문제를 풀 수 있다는 것을 알아냈다. 나는 소수표를 열고 2000 이상의 소수 30개를 하드코딩했고, 다행히도 AC를 받을 수 있었다.

 

G AC를 받고 나서 얼마 안 지나 스코어보드가 프리징되었고, 이 때의 순위는 54등이었다. 한두 문제를 더 풀면 본선에 진출할 수 있을 것이라고 생각했다.

 

 

2:03 D WA

팀원들은 D를 잡기로 했고, 나는 I를 잡았다. 팀원들은 dp를 이용해 이런저런 풀이를 작성해보았지만 대회가 끝날 때까지 D를 풀지 못했다.

 

I번은 꽤나 구현량이 많은 문제였지만, 이와 비슷한 문제를 전에 풀어봤던 적이 있었다. 다만 시간이 70여분 밖에 없었고, 구현에서 한 번 틀리는 순간 디버깅이 상당히 힘들어질 것이라고 생각해서 최대한 조심스럽게 코드를 작성했다. 기존에 풀어봤던 문제와의 차이점은 I번은 인접한 L-트로미노의 색깔이 다 달라야 하고, 3개의 색만을 사용해야 한다는 점이었다. yooshnn은 구현에 참고가 될 만한 그림을 3장 정도 나에게 보내주었고, 이는 구현에 큰 도움이 되었다.

 

노트에 극한의 case work를 하면서 이를 코드로 옮기는 작업이 계속 진행되었고, 대회가 끝나기 8분 전 거의 모든 구현이 끝났다. 이제 남은 것은 마지막 4칸에 대해서 @를 제외한 칸들에 적당한 색을 부여하는 일이었다. 사실 8분이나 있어서 충분히 풀 수 있겠다고 생각했지만 구현 방향을 잘못 잡아서 대회가 끝날 때까지 문제를 풀지 못했다.

 

여기까지 구현하고 못 풀었다

대회가 끝나고 나서 자고 일어난 뒤 코드를 조금 수정해서 I AC를 받았다. 조금 아쉽기도 했지만 내 실력이 부족해서 못 풀었다고 생각하니 마음이 한결 편해졌다.

 

전체적으로 문제 수준이 좋았고, G번 같은 문제는 상당히 좋은 문제라고 생각한다. 아쉽게 본선 진출에는 실패했는데, 내년에는 꼭 진출해보고 싶다는 생각이 들었다.