UCPC 2022 예선 후기

캐티님, 빙하님과 [투어리스트의 올바른 가르침.] 팀으로 UCPC 2022에 참가했습니다. 팀원들은 PS 경험이 꽤(사실, solved.ac Diamond 티어를 달성했을 정도로 상당히) 있는 분들로서 이전에 포켓몬 배틀 씬에서 만난 분들입니다. 팀이 결성되었던 4월 초 당시 저의 티어가 Silver III이었던 걸로 기억하는데, 막 PS를 시작하는 단계였던 저를 믿어준 팀원들에게 무한한 감사를 전합니다.

 

시간을 맞춰 대회 셋을 푸는 팀 연습은 5월부터 6번 정도 한 것 같습니다. 저희 팀은 팀원 간의 실력차가 큰 편이기 때문에 제가 스코어보드를 따라가며 많이 풀린 문제를 맡고, 나머지 두 분이 적게 풀린 문제를 맡는 식으로 연습했습니다. (Codeforces Gym에서 연습하면 스코어보드를 실시간으로 확인할 수 있습니다)

 

개인적으로도 준비인지 그냥 공부인지 모를 문제풀이를 꽤 한 편이고 티어를 8단계 올려 Platinum V가 되었습니다. (저에게 많은 도움을 준 초록책 그리고 solved.ac의 개발자님과 BOJ 단계별로 풀어보기 관리자님 사랑합니다)

대회 당일의 흐름

예선 당일에는 1시간 정도 일찍 스터디룸에 모여 빙하컵 이야기를 하다가 대회가 시작되었습니다.

 

우선 A번을 읽고 ‘작년 기출보다 10배는 쉬운데?’라고 당황하며 제가 3분 만에 솔브.

 

다음으로 저는 B번을 잡고, 빙하님과 캐티님은 J번을 잡았습니다. B번이 아직 공부하지 않은 선분 교차 관련 기하 문제여서 당황한 제가 캐티님에게 도움을 요청했고, 캐티님이 선분 교차 판별 함수 코드를 알려주신 덕분에 28분에 B번 솔브. J번도 같은 시간에 솔브되었습니다(페널티 +2).

 

다음으로 저는 캐티님의 조언에 따라 F번, 빙하님은 E번, 캐티님은 D번을 잡았습니다. 다행히 F번은 별다른 알고리즘 지식을 요구하지 않는 일명 빡구현 문제였고 실수 없이 구현하면서 59분에 솔브합니다.

 

빙하님이 잡은 E번은 날짜/시간 문자열 파싱 문제여서 구현 시간이 길어졌고, 캐티님이 어려운 문제였던 D를 솔브하는 동안 저는 G번을 살펴봤습니다. 제 실력으로 혼자 풀 수 있는 문제는 아니라는 생각이 가장 먼저 들었지만, 1번 블록은 BLOCK으로 주어져야 한다는 기본적인 관찰을 하고 CHAIN을 어떻게 구성해야 할지 고민했습니다. 그 동안에 D번이 92분에 풀리고(페널티 +3), E번이 101분에 풀립니다(페널티 +3).

 

1시간 20분이 남은 시점에서 팀의 성적은 6솔브로, 스코어보드에서 나쁘지 않은 위치를 차지하고 있었습니다. 스코어보드에서 거의 풀리지 않았던 C와 I를 제외하고, G와 H 중 하나를 풀면 조금 불안하게 예선 통과, 둘 다 풀면 확실히 통과할 것이라는 이야기를 주고받았습니다.

 

우선 G번의 풀이를 논의했는데, CHAIN 구성이 그리디하게 가능할 것이라고 의견이 모였습니다. 그리고 블록들을 세그먼트 트리로 관리하기로 합니다. 그 시점부터 저는 풀이를 이해하기 어려웠기 때문에 H번을 보기로 합니다.

 

G번은 약간 더 논의한 뒤에 세그먼트 트리를 이용한 구현을 빙하님이 하기로 하고, 캐티님과 저는 H번을 관찰하기 시작했습니다. 우선 제가 삼항 연산자를 개발에 사용한 경험이 많았기 때문에(?) 간단히 문제를 설명하고 예제를 살펴보면서 ‘올바른 괄호 문자열’ 문제와 비슷한 것 같다는 의견을 냈습니다. 그러자 캐티님이 잠깐 고민한 끝에 카탈란 수를 계산하는 문제인 것 같다고 말했습니다. 그리고 곧바로 구현에 들어가서, 163분에 AC를 받습니다(페널티 +1).

 

G번의 구현은 저희의 예상보다 오래 걸렸습니다. 세그먼트 트리는 제가 아직 잘 모르기 때문에 캐티님과 빙하님의 대화 내용은 기억하지 못하고, 제가 할 수 있는 일은 AC받지 못한 코드에 혹시 기초적인 오류가 있지는 않은지 살펴보면서 구현이 잘 되기를 기도하는 것 뿐이었습니다. 10분이 남은 상황에서 마지막 풀 수 있는 1문제가 늦어지는 것이 분명히 좋은 상황은 아니었지만… 세그먼트 트리를 배우지 않은 자신이 살짝 마음에 들지 않게 되기도 하고… 아무튼 그렇게 시간이 지나가다가 4분이 남았을 때쯤 두 분이 거의 동시에 코드의 오류를 발견하고 급히 수정하고 1분이 남은 상태에서 각자 제출을 했습니다.

 

그런데 BOJ 서버가 터지고 저희의 심장도 터졌습니다. 2분이 경과하고 나서 화면에 뜬 맞았습니다!!를 본 저희는 하이파이브 하며 예선 종료(179분에 AC, 페널티 +1).

 

페널티는 조금 너덜너덜했지만 총 8솔브로 27위, 여유롭게 본선 진출에 성공했습니다!

조금 이른 시간이었지만 저녁 식사로 피자를 함께하며 하루를 기쁘게 마무리지었습니다.

업솔빙

제가 자력으로 푼 문제는 사실상 A와 F뿐이었기 때문에, 나머지 6문제에 대해 업솔빙을 진행하였습니다.

 

업솔빙 내용은 글 아래쪽에서 확인하실 수 있습니다.

본선까지 저의 목표

• 세그먼트 트리 공부하기
• Platinum III 달성
• CLASS 6 취득

앞으로도 PS 열심히 하겠습니다.