작년에 이어서 올해에도 UCPC에 참가했다. 작년에는 @kth990303, @riroan과 함께 했었다. 올해에도 그 팀을 기대했지만 @kth990303은 바빠서 참석이 어려웠고 @riroan 형은 졸업해버리는 바람에(…) 참가할 수 없었다.

작년 ICPC를 진행하면서 알게 된 @delena0702와는 함께하기로 이야기가 되어 있었다. 접수 마감이 다가오면서 다른 사람을 찾기 시작했고, 몇 명을 컨택해보기도 했지만 이미 팀원이 있었다. 아쉽기도 했지만 올해 동아리를 운영하면서 생기는 선순환이었다. 교내에 많은 사람들이 알고리즘에 관심을 가져줘서 더 즐겁게 할 수 있을 것 같았다.

이곳저곳 연락을 돌리다가 작년 학교에서 열었던 KUPC 2022 우승자 @lixflora와 연락이 닿았다. 팀 매칭 전통 깃허브 이슈를 남기려다가, 내가 운영하고 있는 오문추 디스코드 서버에 있어서 빠르게 연락할 수 있었다. 물어보고 나서 팀이 결성되는 데 한 시간이 채 걸리지 않았다.

작년에는 일감호는우리가지킨다 팀으로 본선까지 진출했었는데, 그 힘을 받아서 같은 팀명으로 결정했다. 학교를 대표하는 여러 동물들의 이름으로 팀원 닉네임을 짓는다. 작년에 있었던 건구스와 만쥬가 함께하지 못하면서 쿠, 춘장이로 교체됐다.

연습 세션

올해 제일 잘 한 일: 학교 알고리즘 동아리 만들기. 덕분에 많은 사람들이 UCPC에 지원해 주었다. 내가 아는 한, 우리 학교 인원이 포함된 팀은 7팀이나 됐다 😎

팀이 많아지니 오프라인으로 함께 연습할 수 있는 세션을 마련했다. 교수님의 지원 덕분에 강의실도 빌릴 수 있었다. 이미 이전 UCPC 예선 문제들을 연습한 팀들이 몇몇 있어 @riroan 형에게 연습셋 문제를 구성해달라고 부탁했다. 고마운 사람들이 많다!

연습셋 난이도는 우리의 실력을 고려해서 기존 UCPC 예선보다는 쉽게, 다양한 알고리즘 풀에서 냈다고 했다. 확실히 오프라인으로 서로 문제를 해결하는 게 재미있었다. 3시간동안 문제를 풀고 나서 다른 팀들과 어떻게 풀었는지 토의하는것도 실력 향상에 분명 도움이 됐을 것이다.

실제로 UCPC에 참가하지 않는데도 팀 연습을 구경하기 위해 와주신 분이 계셨다. 연습하는 것을 지켜보면서 대회 환경에 대해서 흥미를 가지게 되신 것 같아서 감사하면서도 흐뭇했다 ☺

예선

학교 근처 스터디카페를 빌려 예선을 치렀다. 방 안에 모두가 볼 수 있는 컴퓨터 한 대가 있길래, 모니터에 스코어보드를 띄워두기로 했다. 대회 시작과 동시에 새로고침을 다들 하는지 트래픽 때문에 금방 문제가 뜨지 않았다. 문제 전략은 내가 A번을 보고, 나머지 두 명이 앞에서 / 뒤에서 진행하는 방식이었다.

A. 체육은 코딩과목 입니다

2분 AC(+)

왼쪽 / 오른쪽 / 뒤돌아 쿼리가 주어지고, 최종 보는 방향이 어디인지 출력하는 문제였다. 대회 때 압박감 때문인지 쿼리에 대한 출력을 딕셔너리로 하드코딩하느라 시간이 더 걸렸다. 다행히 구현미스는 없어서 바로 정답을 받아냈다.

K. 세미나 배정

14분 AC(+2)

다른 문제를 보느라 정신이 팔려있던 사이에 @delena0702가 K가 풀만하다고 이야기했고, 금방 해결했다. 아직 풀이는 모른다.

I. 자석

24분 AC(+)

@delena0702가 K번부터 훑고 내려오더니 I번도 밀어버렸다. 대회가 끝나고 나서 문제를 한 번 봤는데, 우아한 풀이법이 있었다.

문제에서 구해야 하는 것은 배열 $a$에 대해서, $a_i -\ a_j -\ K \times |i-j|$의 최댓값이다. 절댓값을 풀면 아래와 같은 두 가지 식이 나온다.

$$a_i-a_j-K\times(i-j) = (a_i-Ki)-(a_j-Kj)$$ $$a_i-a_j-K\times(j-i) = (a_i+Ki)-(a_j+Kj)$$

구해야하는 값을 찾았으니, $a_i \pm Ki$ 를 저장하는 두 개의 배열을 만든 뒤에 왼쪽에서부터 $max$, $min$을 갱신하면서 답도 함께 찾아주면 $O(N)$에 문제를 해결할 수 있다.

D. 더 흔한 타일 색칠 문제

34분 AC(1+)

A번을 풀고 나서, 바로 가운데 문제들을 분석해보기로 했다. D가 브루트포스처럼 풀 수 있을 것 같아서 잡았다.

$K\times K$로 나눈 뒤 바꿔야하는 최소 타일과 바꾼 뒤 타일들을 출력하는 것이었다. 단순하게 타일 하나를 잡고 모든 다른 타일과 비교하는 바보같은 짓을 하고 있었다… TLE를 받고 나서 @delena0702가 타일의 각 위치별로 가장 많이 나온 알파벳으로 바꾸는 방법으로 구현해서 AC.

C. 차량 모듈 제작

159분 AC(3+)

네 문제를 해결하고 나서 진전이 없었다. 나는 B번을 계속 보고 있었고, @lixflora 형은 C, @delena0702는 F 디버깅이 한참이었다. 이미 F는 다섯 번 WA를 받았고 C도 예제가 맞았지만 제출 후 WA를 받아서 다같이 C를 붙잡았다.

풀이를 공유하고 나니 단순 $1000$ 개의 정점에서 MST를 돌리는 문제임을 알았다. 단순한 MST에 기하를 섞어서 예시 그림만 봐도 어지러웠다… 우선순위 큐에 모든 기어 쌍 벨트 길이를 넣어 두고 꺼내면서 UF를 사용했다.

기하는 어렵다. 벨트 길이는 피타고라스 정리와 호의 길이를 사용해야 하는데, 호의 길이를 구하기 위해서 중심각을 구할 때 $cos^{-1}$를 사용한다.

풀고 보니 처음에 @lixflora 형이 짠 코드와 거의 비슷했는데, 어떤 부분이 틀렸는지는 아직 모르겠다.

F. 응원단

178분 AC(6+)

@delena0702가 마지막에 반례를 찾아서 극적으로 버저비터급 AC를 받아냈다. 홀짝성에서 찾을 수 있는 멋있는 오프라인 쿼리, 빡구현을 해냈다. 처음에는 단순 링크드리스트/덱 문제인 줄 알았는데 행/열에 대해서 진행한다는 점, 두 원소의 위치를 바꿔야하는 점이 장벽이었다.

홀짝 행/열에 대해서만 움직이니 바뀌지 않는 것을 캐치했고, 이를 기반으로 여러 디버깅 끝에 문제를 맞혔다. 이 문제를 푸는 동안 @lixflora 형은 팔찌 문제를 보고 있었는데, 진작 이 문제를 봤다면 풀 수 있었을 것 같다고 했고, 실제로 풀이도 에디토리얼과 얼추 맞아서 정말 아쉬웠다.

B. 물류창고

문제를 계속 들여다보면서 Max MST인 것 같다는 생각을 했다. 트리 형태가 되니깐 간선 기준으로 개수를 곱해주면 되지 않을까? 라는 접근만 이뤄졌고, 특별한 진전은 없었다.

에디토리얼을 보니 작은거큰거 문제였다. 어떻게 많은 팀들이 문제를 해결했을까.. 싶었다.

마무리 🎈

대회가 끝나고 나서는 학교 근처에서 예선을 치렀던 @nayounsang1, @creampuffshu, @gmtmoney2357과 함께 문제에 대해서 이야기를 나눴다. 계속 이 팀의 스코어보드를 예의주시했었는데, 프리즈되고 나서 여러 문제들에 주황불이 들어와서 긴장했었다. 좋은 방향으로 서로에게 자극이 된 것 같아서 재미있었다!

예선은 222팀 중에서 64팀으로 마무리했고, 6솔이라는 괜찮은 성적을 내서 지역균형(?) 으로 본선에 갈 수 있을 것이라고 생각했다. 작년에도 5솔 학교인원 본선을 갔기 때문에 거의 확실시됐다고 넘겨짚었다…

60팀이 갔었던 2022 본선과는 달리 올해에는 44팀밖에 본선에 진출하지 못했고, 아쉽게 예선에서 탈락했다. 7문제를 푼 팀중에서 상위 팀이 진출한 것으로 보여서 더더욱 아쉬웠다.

작년 UCPC 본선에서의 좋은 기억들이 너무나도 많았다. 비록 실제로 본선에서 겨룰 실력은 되지 않았지만, 다양한 학교의 사람들이 한데 모여서 같은 관심사를 두고 경쟁했던 경험은 좋은 자극이 됐었다. 실제로 이런 대회에 많은 학교 인원이 참여하지 않았던 게 아쉬워서 동아리를 만들었던 것도 있었다.

내년에는 마지막 도전이 되겠지만 그만큼 후회없었으면 좋겠다 🦆