UCPC 2024 후기

UCPC 2024에 sciencepark, jk410과 관악명강이라는 팀으로 참가했다. 이름은 각각 절대평가235오렌지도비플받는봉자구, 믿을수없는강의력과어디서본시험문제엄컴프, 컴퓨터의역사와어셈블리부터시작하는에개실로, 컴공에서 이상한 쪽으로 유명한 강의 중 각자 들은 과목을 샤라웃했다. 팀연습은 예선과 본선 전에 각각 두 번씩인가 했고, 올해 ICPC도 함께 출전할 예정이다.

 

 

예선 슼보

 

예선은 학교 도서관에서 스터디룸을 빌려 진행했다. 쉬운 문제 코딩이 아마도 빠른 내가 A~D, 박민철(sciencepark)이 E~H, 박종경(jk410)이 I~K를 풀기로 했다. 아마.

 

~0:00

내가 A의 입출력과 예제를 보고 58초에 찍어 맞췄다. 미친 속도라고 생각했는데 퍼솔은 전혀 아쉽지 않을 정도로 멀었다. 내 생각엔 처음 로딩 속도가 결정적이지 않았을까.

 

~0:34

D가 풀리길래 내가 읽었고, 풀이는 바로 나왔다. 그런데 정렬하고 답을 구하는 과정에서 인덱스를 계속 헷갈려서 대회 초반부터 3틀을 박고 맞았다. 민철이가 H가 쉽다며 제출하더니 두 번 틀려왔다.

 

~0:58

민철이가 E를 세 번의 시도 끝에 풀어왔다. 정해는 브루트포스였는데, 이보다 개선된 시복으로 파라메트릭을 하느라 어려웠다고 한다. 동시에 종경이가 C에 스택 풀이를 제출했으나 맞지 않았다.

 

~1:24

나는 그동안 J의 나이브와 함께 규칙 찾기를 하고 있었는데, 풀이가 잘 안 나와서 대충 스택 같다는 말을 하며 민철이한테 넘겼다. 그랬더니 금방 맞아왔다.

 

~1:36

종경이가 G에서 혼자 외로운 싸움을 하다가 맞았다.

 

~1:45

나는 그동안 많이 풀린 C를 고민하다가 모르겠어서 민철이한테 넘겼고, 금방 맞아왔다.

 

~1:49

내가 남는 H에 가서 케이스를 몇 개 더 떠올린 뒤 맞았다.

 

1:49~
남은 시간 동안 각자 자신 있는 문제를 하나씩 잡았다. 내가 I, 민철이는 K, 종경이가 F를 풀기 시작했다.

 

~2:41

민철이가 종경이와 K의 케이스를 열심히 정리하더니 결국 풀어냈다. 옆에서 막 심상치 않은 이야기들이 나오길래 솔직히 힘들 줄 알았다.

 

~2:56

종경이가 Z 알고리즘과 덱 디피를 한다고 해서 뭔 소린가 했는데, 진짜 그걸로 잘 풀었더라. 뭔가 되게 든든했다.

 

~3:00

I에서 구간 셋을 관리한다는 생각은 금방 했는데, 코드를 짜다 보니 예상치 못한 케이스들이 생겨서 코딩이 점점 길어졌다. 결국 한 끗 차이로 코드를 완성하지 못한 채 대회가 종료되었다. 처음에 구현량을 예상 못하고 너무 여유 부리면서 짠 것이 정말 아쉬웠고, 또 연습 때처럼 준보스 문제를 코딩 이슈로 놓친 것 같아 속상했다.

 

결과

는 전체 16등으로, UCPC인 걸 감안하면 굉장히 높은 등수여서 놀랐다. 연습을 몇 번 하면서 우리 팀이 예상보다 잘한다고 생각은 했었지만, 진짜로 수상이 가시권에 들어오니 욕심이 생겼다. 물론 나는 예선에서 문제를 읽고 넘긴 것 밖에 한 게 없다.

 

 

본선 슼보

 

이번에는 대회장에 도착한 순서대로 A~D를 종경이가, E~H를 내가, I~M을 민철이가 보기로 했다. 대회가 시작하자마자 문제 수정이 있는 H를 봤는데, 대충 봐도 내가 풀어야 하는 기하 문제임을 알고 욕이 나왔다.

 

~0:18

시작한 지 얼마 안 되어 D 솔브들이 나왔는데, 종경이가 문제 이해가 잘 안 된다고 해서 내가 읽었다. 풀이가 너무 명확해서 바로 짰고, 조금 절었지만 맞았다.

 

~0:36

솔브가 나오는 L을 둘이 얘기하더니 종경이가 슥 짜서 맞았다. 이분매칭이 이 정도로 빨리 많이 풀릴 문제인지 난 모르겠다.

 

~0:54

A가 꽤 풀리길래 읽어봤는데 쉽지 않았다. 그래도 열심히 머리를 굴리니 풀이가 나왔고, 구현도 불안했으나 다행히 한번에 맞았다.

 

~1:07

민철이가 M 이상한 풀이가 나왔다며 긴가민가 하면서 짰는데 맞았다. 삼분탐색으로 풀(뚫)었고, 정해는 그리디였다. 여기까지 페널티를 하나도 안 쌓고 잘 따라와서 순위가 상당히 높았다. 한 문제를 맞힐 때마다 7등이 되었고, 10등 안팎을 계속 유지했던 것 같다.

 

~2:06

이제 풀어둔 문제가 동나서 머신이 비었고, J의 흐르드 풀이를 종경이가 아마 이때부터 짜기 시작했다. 슼보에서 많이 풀린 E는 세 명 다 풀이를 못 내고 있었다. 나는 B를 찍먹해보다가 에바임을 깨닫고 다시 E를 잡았다. E를 계속 고민하던 중 갑자기 미친 생각이 떠올랐고, 어느 정도 확신을 가진 뒤 코딩을 시작했다. 비슷한 타이밍에 둘이 C를 의논하더니 풀이를 냈다. E의 코딩을 마쳤지만 이상하게 예제가 나오지 않아 머신을 넘겼다. 그리고 얼마 후에 변수명이 중복된 곳을 발견했고, 두 번에 걸쳐 머신을 뺏은 뒤 AC를 받았다. 나는 E가 진지하게 무지 어렵다고 생각하는데, 현재 기여를 보면 사람들은 그렇지 않았던 모양이다.

 

~2:10

민철이가 C를 계속 코딩해서 맞았다. 순식간에 두 문제를 해결하며 쭉 밀렸던 순위를 훅 끌어올렸다.

 

~3:44

이제는 기하 담당인 내가 H를 풀어야 할 때가 왔다. 그런데 H를 읽어보니 생각보다 조건이 친절하고, 요구하는 것도 간단해서 진짜로 풀 수 있을 것 같았다. 큰 틀의 풀이는 금방 잡혔고, 예외가 없는 세부 전략을 민철이와 함께 구상했다. 동시에 J의 흐르드 풀이는 코딩이 말려서 폐기하고, 비교적 쉬운 풀이를 찾기로 했다. 그래서 일단 내가 H 코딩을 시작하고, 둘이서 J의 트리 디피 풀이를 완성했다. 백준 코드를 대충 긁어놓은 팀노트를 적극 참고하면서 H를 열심히 짰지만, 틀렸다.

 

~4:08

종경이가 J를 열심히 코딩하더니 한번에 맞았다. 그동안 민철이가 H 풀이에서 로직의 오류를 짚어줬다. 또, 민철이가 F의 러프한 풀이를 냈다.

 

~4:33

해당 로직을 수정했으나 틀렸다. 머신을 F에 넘기고, 종경이까지 동원해 H의 코너 데이터를 열심히 만들었다. 결국 반례를 얻어 오류를 찾았는데, 앞에서 로직을 수정하는 과정에서 실수가 있었다. 그러나 이번에도 비슷한 퍼센트에서 틀렸다.

 

~4:57

아무리 고민해도 H에서 더 이상의 반례는 나올 수 없다고 생각했다. 그래서 이번에도 나는 마지막 문제를 못 푸는구나, 싶어 멘탈이 나갔다. 그동안 민철이가 F를 열심히 짜봤으나 엿부족이었고, 대회 종료 3분 전에 나에게 머신이 돌아왔다.

 

~4:59

코드를 맨 처음부터 보면서 고칠 만한 곳을 고쳐보려고 했다. 가장 먼저, 좌표의 절댓값의 상한을 뜻하는 상수를 백만에서 십억으로 고쳤고, 맞았다. 순간 당황스럽고 의아해서 별로 기뻐하지도 못했다.

 

~5:00

곰곰이 생각해 보니, 좌표가 이동하다 보면 스케일이 많이 커질 수도 있었다. 완전히 간과한 부분이었고, 운 좋게 발견해서 정말로 다행이었다. 여튼 어찌저찌 8솔을 해서 수상을 기대해 볼 수 있게 되었다.

 

결과

는 13등으로, 5등상을 수상했다. 한참 멀게만 느껴졌던 UCPC 수상을 하게 되어서 정말로 행복하고 기뻤다. 부상으로 받은 마이크는 대체 어떻게 써야 할지 모르겠지만, 아무렴 어떤가. 팀원들 모두 각자의 역할을 잘해주어서 고맙고, 다음 ICPC도 기대가 된다.

 

jk410, heeda0528, sciencepark