UCPC 2022 예선 후기

들어가며

올해 대회는 작년 UCPC 팀원 그대로 참여하였다. 팀원 두 명(stabilizer_h, harinboy)은 모두 같은 서울대학교 18학번으로, 군대에서 만났다. 작년에는 싸지방에서 팀원 셋이 옹기종기 모여 앉아 쳤었는데, 1년 후에는 세 명 다 밖에 나와서 대회를 칠 수 있게 되었다. 시간이 참 빠르다.

작년에 놀랍게도 예선 1등을 차지하였다. 어떻게 한 건진 잘 모르겠다. 아무튼 그래서 올해 팀명을 예선 일등 딱대라는 뜻으로 "예일대" 라고 지었는데, 결론부터 말하면 아쉽게도 하지 못 했다. 그래도 3등 정도면 상당히 잘 한 거기 때문에 만족한다. 그리고 1, 2등 팀은 ICPC에 참가하지 못 하는 팀이기 때문에 사실상 1등이라고 할 수 있다.

과거의 영광

"ICPC 참가 가능 팀 중 1등" 도르 수상

 

대회 타임라인

나랑 stabilizer_h는 학교에서 만나서 같이 대회를 치고, harinboy는 집에서 치기로 했다. 도서관 그룹스터디룸에 도착하고 나서 세팅 좀 하고 나니까 시간이 훅훅 갔다. 팀 이름을 괜히 저렇게 지어 놓아서 평소보다 좀 더 긴장이 되는 듯 했다. 문제 배분은 항상 하던 대로 코딩이 제일 빠른 내가 A부터 풀고, stabilizer_h가 E부터, harinboy가 H부터 풀기로 했다.

대회가 시작이 되고, 백준 서버가 잠시 불안한 듯 보였으나 다행히도 금방 돌아왔다. A를 딱 읽었는데 매우 쉬운 문제여서 제출창에 바로 Python으로 코딩하기를 시전했다. 뚝딱 짜서 냈는데 RTE를 받았다. A번을 틀렸다는 사실에 충격을 금치 못하며 코드를 봤는데, 나눗셈을 할 때 슬래시(/)를 2개 써야 했는데 1개만 쓴 거였다. 눈물을 머금고 고쳐서 AC (1min).

그 다음에 B를 열어서 봤는데, 뭔가 바로 떠오르지는 않았다. 그래서 C랑 D도 열어서 봤다. B로 일단 돌아오기로 했다. 다시 보니 그냥 쉽게 생각하면 되는 것 같아서 후루룩 짜서 냈다. 다행히 한 번에 AC (9min).

B를 푸는 동안 누가 J를 풀었길래 슥 봤는데 바로 떠오르지는 않아서 그냥 담당 팀원(harinboy)을 믿기로 하고 돌아왔다. C는 좀 어려워 보이고, D는 그나마 풀만한 듯 해서 정리를 좀 해 보았다. 풀이는 금방 나왔는데, 구현을 할 때 order_of_key를 지원하는 set 자료구조가 필요해서 구글링을 좀 했다. 이름을 까먹어서 시간이 좀 걸렸지만 뭐 어쨌든 찾아서 짰다. 그러는 사이에 팀원이 J를 AC (18min). 믿고 있었다구~

D 코드를 다 짜고 내니까 TLE가 떴다. 코드를 보니까 ios::sync_with_stdio(false); cin.tie(nullptr); 이걸 안 써서 그런 거였다. 그걸 고쳐서 내니까 이번엔 WA를 받았다. 식에서 부호를 하나 잘못 쓴 걸 발견해서 고쳐서 내니까 또 WA를 받았다. 알고 봤더니 multiset을 써야 하는 자리에 set을 쓴 거였다... multiset으로 바꿔서 내니까 AC (32min). 여기서 초반 시간 버린 게 좀 아쉽다.

곧바로 stabilizer_h도 F를 AC (33min). 그 다음에 뭘 풀지 좀 보다가, E가 그냥 구현 문제라길래 내가 풀기로 했다. 날짜-시간을 잘 파싱하면 되는 문제였는데, Python에 있는 datetime 모듈을 이용하면 좀 편할 것 같아서 또 열심히 구글링하면서 짰다. 나중에 풀이 슬라이드 보니까 내가 한 뻘짓을 한 큐에 해주는 함수가 있던데, 나는 그걸 찾지 못해서 손이 좀 고생했다. 아무튼 내가 이러고 있는 사이 harinboy가 H도 AC (38min) 내주고, E를 다 짜서 내니까 다행히 한 번에 AC (46min)가 나왔다.

그리고 나서는 stabilizer_h가 G 풀이가 나왔다고 해서 들어본 뒤, 역시 내가 짜기로 했다(?). 풀이 자체는 그냥 머리 좀 굴리면 되는 그리디였는데, 짜서 내니까 또 WA가 나왔다. 아무리 봐도 맞는 코드라 한참을 보다가, 예제를 이것저것 넣어보다 보니 남은 블록들을 붙이는 부분에서 이상하게 처리한 거였다는 것을 발견했다. 고쳐서 내니까 AC (69min).

이제 남은 게 C랑 I였는데, I를 읽고 보니 뭔가 IOI 2016 Day 1에 나온 Roller Coaster Railroad라는 문제와 상당히 비슷해 보여서 바로 검색에 들어갔다. 최고의 블로그 글에 들어가니 solution이 딱 적혀 있었다. 그걸 읽고 대충 비슷하게 짜서 냈는데 WA가 떴다. 로직에 약간의 문제가 있음을 발견하고 고쳐서 냈는데 이번에는 RTE. 역시 코딩에서 약간의 실수를 발견하고 또 고쳐서 내서 AC (115min). 어째 한 번에 맞는 게 없냐..

그리고 나서 C를 봤는데, 다른 문제를 다 풀기 전에는 아무리 봐도 모르겠던 게 갑자기 풀이가 떠올랐다. 풀이 자체는 어느 정도 전형적인 형태의 트리DP 였는데, 답 역추적 부분이 상당히 구현하기 귀찮았다. 그냥 아무렇게나 찍어도 알아서 잘 채점해주면 참 좋았을 텐데... 입력에서 들어온 순서대로 이쁘게 찍어주어야 해서 코드를 열심히 갈아엎었다. (그래도 첫 제출 전에 알아채서 다행이지 아니었으면 한 2번 더 틀렸을듯 ㅋㅋ) 뭐 쨌든 열심히 고쳐서 냈는데 어김없이 WA. 다행히도 금방 로직 오류 하나를 찾아서 다시 냈는데 또 WA. 알고 보니 답 역추적을 잘 고쳤다고 생각했는데 잘못 고친 거였다. 눈물을 머금고 pii를 pair<int, pii>로 고쳐 가면서 스파게티 코드를 연성한 끝에 AC (155min).

 

소감

우선 문제를 다 풀었고, 페널티도 아주 좋진 않았지만 막 나쁘지도 않아서 나름 괜찮은 결과를 얻은 것 같다. 물론 원래 하던 것보다는 좀 많이 틀린 듯 하다.. 사실 최근 들어서 갑자기 이상한 실수로 틀리는 경우가 급격하게 많아졌는데 아마 연습 부족으로 인한 현상인 듯 하다. PS 좀 더 열심히 해야지..

그거와는 별개로 문제 퀄리티는 Very good이었다. 사실 출제+검수진 라인업을 보았을 때 퀄리티가 나쁠 거라는 생각은 안 했는데 역시 기대를 저버리지 않았다. 난이도 곡선도 이 정도면 상당히 좋았던 듯 하다.

지금까지 UCPC 본선을 3번 나가서 4등/4등/6등으로 3등상만 3번을 탔는데, 올해는 1등상은 솔직히 에바고 2등상을 목표로 열심히 해야겠다.

 

(내가 푼) 문제별 풀이

전체 솔루션은 https://static.ucpc.me/files/2022/ucpc22-prelim-solutions.pdf 참고. 내가 푼 방식을 간단하게 첨언하는 형태로 써 보았다.

A

print('long ' * (int(input()) // 4) + 'int')

 

B

뭔가 일찍 고를수록 가중치에 붙는 계수가 커지기 때문에 가중치 오름차순 순서대로 고르는 게 가장 좋겠다는 생각을 할 수 있고, 실제로 그게 맞다. 정답은 문제에서 주어진 과정을 그대로 시뮬레이션하면서 구해도 크게 어렵지 않게 구할 수 있다.

입력이 "세 점이 한 직선 위에 있는 경우가 없도록" 친절하게 주어지기 때문에 선분 교차 판정을 대충 짜도 되어서 좋았다.

 

C

내가 정의한 DP값이 풀이 슬라이드에 나온 것과 정확히 동일해서 약간 신기했다. 다만, DP 값을 구할 때 파라메트릭 서치를 굳이 할 필요는 없고 DP값이 음수인 친구들을 "abs(DP) 값이 큰 것부터" 그리디하게 매칭해주는 식으로 하면 (최대 1개가 매칭이 안 되고 남을 수 있도록) 자연스럽게 최적인 값이 구해지게 된다.

풀이 슬라이드에서 언급한 대로 역추적을 짜는 것이 상당히 귀찮은데, 출력 형식에 제한이 좀 걸려 있어서 좀 더 귀찮았다. 그나마 쉽게 짜는 방법은 각 DP값마다 "그 DP값의 출발지에 해당하는 정점"을 같이 들고 다니는 것이다. 매칭을 시켜 줄 때 DP값이 양수인 쪽 정점에서 길이를 맞춰주기 위해 정점을 이동해야 할 필요가 있는데, 그냥 부모로 한 칸씩 올라가면서 naive하게 구해 주어도 충분하다.

 

D

일단 케이스를 열심히 나눠주고 보면 결국 문제를 "자료구조에 점 추가 / X가 주어지면 X 왼쪽(오른쪽)에 있는 점 갯수 세기" 의 두 쿼리를 처리하는 것으로 바꿀 수 있다. Segment Tree를 사용하기 위해서는 노드를 동적으로 할당하도록 하거나, 미리 쿼리를 한 번 훑는 등의 추가 작업이 필요해서 PBDS를 쓰는 것에 비해 좀 더 귀찮다.

추가되는 점이 a/b와 같이 유리수 꼴인데, 이것을 잘 구현하기 위해서는 함수값의 부호를 물어볼 때 무조건 정수 점만 물어본다는 사실을 이용하여 정수가 아닌 유리수는 모두 쩜오(.5) 로 생각한 뒤 값을 두 배로 해주면 편하게 처리할 수 있다.

 

E

C++보단 Python이 좀 더 편할 거다. 아마도...?

datetime 모듈을 열심히 갖고 놀다 보면 어떻게든 풀 수 있다.

 

G

풀이 슬라이드에 나온 대로 한 게 전부...

심지어 마지막 부분에 나온 "주의가 필요한 부분"까지 잊지 않고 걸려 넘어져 주었다.

 

I

풀이 슬라이드에서 설명한 풀이가 Roller Coaster Railroad 어쩌구보다 훨씬 간결하다. 물론 간결하다 != 쉽다.