이번 팀연습이 UCPC 전에 하는 마지막 팀연습이 될 거 같아서 이번에는 ‘UCPC 본선과 난이도가 유사한 12문제셋’을 뛰기어 보기로 했습니다. 여태까지 UCPC 본선 셋은 하나같이 난이도가 상당히 높았기 대문에, 이번 팀연습은 난이도 높은 셋을 뛰기로 했고, 그 결과 SNUPC 2019 div1이 연습 셋으로 채택되었습니다.
여태까지 플래티넘 이하 문제 위주로 구성된, 상대적으로 쉬운 셋만 뛰어온 만큼, 이번 팀연습은 어려운 셋에서 당황하지 않고 쉬운 문제들을 빠르게 풀 수 있는지 확인해 볼 수 있는 기회가 될 것으로 보입니다.
연습 초반(~90분)
시작부터 제대로 말렸습니다. 시작하자마자 kyaryunha는 B, 저는 C, jame0313님은 다른 문제들 천천히 읽겠다고 하셨고, C가 쉬운 그리디문제인 것 같아서 제가 잡겠다고 했습니다. B도 쉬운 문제였는지, kyaryunha도 이 문제 자기가 잡겠다고 하더군요. 그런데, 막상 C가 쉬운 문제인 거 같다고는 했지만 막상 까고보니 풀이 구체화가 잘 안되더군요.. 당시 아침이라 정신이 몽롱한 것까지 더해져 그대로 1시간 가까이 뇌절했습니다.
팀원들도 상황은 마찬가지였는지, 1시간 내내 팀원들의 제출 소식도 들려오지 않았습니다. 1시간쯤 지난 후 팀원들 상황을 봤는데, kyaryunha는 E, jame0313님은 B를 잡고 뇌절중이었습니다. C를 구현할 자신이 없었던 저는 팀원들에게 C 문제 설명을 하고, B번과 E번을 읽어봤습니다.
B번은 사각형 구간 내의 가중치 합을 최대화하는 문제로, 보자마자 금광이 생각나는 문제였습니다. 그런데 차이점은, 구간이 직사각형이 아니라는 것. 심지어 사각형의 제약사항에 대한 언급이 전혀 없어, 오목한 사각형 등 다양한 형태의 사각형도 가능한 게 아닌가? 하는 생각에 빠졌습니다. B 풀이는 전혀 감도 안 잡혀서, E번으로 넘어갔습니다.
E번은 자신의 중간순위와 이후 참가자들의 중간순위가 주어졌을 때, 가능한 가장 높은(1등에 가까운) 순위와 낮은 순위를 구하는 문제였습니다. 최소 순위는 동점자 발생 시 항상 순위가 밀리도록 하면 쉽게 구할 수 있고, 최대 순위는 현재 순위와 동점자 수를 같이 관리하면 될 것 같아, E번을 제가 잡겠다고 했고, 금방 구현해서 제출했지만 WA를 받았습니다. B 잡고 있을 때 kyaryunha가 WA를 2번 더 냈기 때문에, 총 3WA. 이후 순위를 내릴때, 동점자수가 1이 아닐 수 있음에도 1로 고정시키고 있었다는 것을 발견하고, 고쳐서 99분만에 드디어 첫 AC를 받았습니다.
연습 중반(~180분)
제가 E를 짤 동안, 나머지 두 팀원은 C를 잡고 있었고, 저는 B가 감이 전혀 안잡혀서, 다른 문제를 읽어봤는데, 하나같이 어려워 보였습니다. 그나마 스코어보드상으로 많이 풀린 것 같은 F는 하필 싫어하는 확률론 문제고 L은 간단한 오일러 경로인 줄 알았으나, 경로 추적도 추적이지만, 화단의 한 변을 지날 때마다 이동 방향을 바꾸라는 조건때문에 만만치 않은 문제라는 걸 알게 되었습니다. 결국 돌고 돌아 결국 B를 잡아야 한다는 결론이 나왔고, 다시 B를 잡기 시작했습니다. 이때쯤 jame0313님이 112분 경에 C를 AC받았고, 셋이서 다같이 B에 대해 고민하기 시작했습니다.
이쯤되니 다들 ‘금광 상위호환 문제인데 왜 이렇게 많이 풀렸지?’ 하는 반응이었고, 이대로 한 시간을 더 뇌절하다 보니 문제를 잘못 읽은게 아닐까 하는 의문까지 들었습니다. 그래서 문제를 다시 꼼꼼히 읽어봤더니, 그것이 실제로 일어났습니다. ‘각 변에서 꼭짓점을 제외한 정수 좌표 위치에 기둥을 하나씩 세운다’ 라는 내용을 놓쳤었더군요. 이것도 모르고 다같이 기둥이 울타리 내부에 있어도 되는 줄 알았던 겁니다;; 이게 UCPC 본선이 아닌게 천만다행이었네요..
연습 후반(~300분)
그런데 문제 해석을 바로잡고도 여전히 풀이는 쉽게 떠오르지 않았습니다. 한 10분정도 더 고민하고서야 마주보는 변의 두 점을 고정시키고, n^2가지 경우에 대해 나머지 두 점을 각각 O(n)에 구하여, 총 시간복잡도 O(n^3)에 해결하는 풀이를 찾았습니다. 그런데 제 풀이에 누적합으로 전처리하는 부분이 구현이 좀 빡셀 것 같아서 jame0313님에게 코딩을 넘겼고, 30분정도 더 지난 뒤 229분에 AC를 받았습니다.
남은 70분동안은 F와 K 가지고 열심히 뇌절했는데, F는 결국 끝날때까지 풀이에 대한 감조차 전혀 잡지도 못했고, K는 케이스가 생각보다 많아서 생각하다 시간이 끝났습니다.
이번 팀연습은 여러모로 아쉬운 점이 많았습니다. 우선 초반 컨디션 난조로 인해 거의 1시간동안 아무것도 못 했다는 점이 그 첫번째입니다. 비슷한 경험이 아예 없었던 것은 아니지만, 고난이도 셋에서는 더더욱 컨디션 난조로 인한 뇌절이 더 심하다는 것을 깨닫게 되었고, 대회 당일의 컨디션 조절의 중요성을 깨닫게 되었습니다.
둘째는 당연히 해석실수입니다. 이번 해석 실수는 이거 때문에 한 1시간 반정도는 날렸다고 봐도 될 정도로 치명적인 실수였던 것 같습니다. 이런 실수를 미리 경험했으니 UCPC 본선때는 최대한 실수 없도록 해야겠습니다.