2022 UCPC 예선 후기

우리 팀 "내 이름은 무면허 라이더 김범수 나로 말할 것 같으면" 은 9솔브, 페널티 780분으로 12위를 차지하였다. 팀명은 해당하는 팀원분이 카톡을 읽지 않아 저렇게 결정되었다. 팀명에 대한 불만이 많으신 것 같지만, 적어도 나는 스코어보드 첫 페이지에 저 팀명을 올릴 수 있게 되어서 좋다. 결과에 대한 회고는 뒤에서 하고, 우선 시간 별 진행 상황을 정리해보도록 하겠다. 문제 배분은 코포 레이팅 순대로 qjatn0120 선배가 앞 4문제, 내가 가운데 3문제, slah007 선배가 마지막 3문제를 보기로 했다.

 

~0:03

A 2분 안에 못풀면 벌금이라느니... 팀명을 첫 페이지에 올려야 한다느니.. 같은 이상한 소리를 하다 대회가 시작되었다. 서버 이슈로 인해 접속이 약간 지연되었다. qjatn0120 선배는 A가 선분 교차라고 하길래 내가 B 아니냐 했더니 머쓱해하시면서 A를 3분에 맞아왔다. 나는 E를 보고 열심히 구현 구상을 하고 있었으며, slah007 선배는 마지막 문제를 보고 폴라드로 되나? 같은 소리를 하시길래 일단 E에 집중했다.

 

~0:21

인덱스 미스 탓에 E를 한번 틀리고 맞았다. 이후 스코어보드에 B가 많이 풀렸길래 B를 보러 갔다. qjatn0120 선배는 D를 잡았다.

 

~0:29

B를 보니 선분 교차 코드만 긁어오면 약간의 그리디적 발상으로 해결할 수 있을 것 같았다. 바로 긁어서 AC. 같은 시점에 J AC도 나왔다. 나는 원래 담당이었던 F를 잡으러 갔다.

 

~0:47

이후 D의 AC가 떴다. 세그를 쓰면 상당히 구현이 복잡한 것으로 아는데 한 번에 맞아오셨다. 어떻게 했지? 그 사이 나는 F를 후딱 짜 한번 틀렸다.

 

~0:59

F를 틀릴 이유가 없어 qjatn0120 선배와 지문을 다시 읽은 결과, 아이템을 가진 상태에서는 탈출하지 못 한다는 것을 깨달았다. 고쳐서 AC. 이때까지 6솔브였다. 나는 qjatn0120 선배와 G 풀이를 대충 토론한 후, slah007 선배의 H를 도우러 갔다.

 

~1:26

G AC가 나왔다. 나는 slah007 선배와 H를 계속 잡았으나 별 진전이 없었고, I도 틈틈이 봤으나 하나도 모르겠었다. qjatn0120 선배는 C를 잡으러 갔다.

 

~2:27

C가 풀린다고 말한 qjatn0120 선배가 긴 구현 끝에 C를 맞아오셨다. 팀명의 주인공 노릇을 톡톡히 하는 순간이었다. 그 즈음, H의 풀이도 여러 뇌절을 거쳐 완성되어가는 단계였다.

 

~2:40

3명이 동시에 코딩을 한 결과, slah007 선배의 H 코드가 AC를 띄웠다. 이후 I는 풀이를 들어도 남은 시간동안 물리적으로 코딩할 수 없다는 결론을 내린 후 문제 리뷰 및 스코어보드 구경을 했다.

 

문제별 요약

A (B5, solved by qjatn0120) : A는 A다.

B (G2, solved by leo020630) : 선분의 특성 상, 가중치의 오름차순으로 처리하는 방법이 항상 유효하다. 낮은 가중치->높은 가중치로 간선을 이으면 사이클이 생길 수 없기 때문이다. 따라서, 선분 교차만 할 수 있으면 쉽게 문제를 해결할 수 있다.

C (D5, solved by qjatn0120) : 꽤 어려운 트리+그리디 문제이다. 대회 중에는 크게 생각 안하고 팀원이 풀어주어서 적당히 쉬운가보다 했는데 상당히 어려운 문제인 것 같다. 업솔빙 예정

D (P4, solved by qjatn0120) : 문제를 잘 분해하면, set에 원소를 추가하고 해당 원소보다 작은 원소의 개수를 알려주는 연산을 지원하는 자료구조가 필요함을 알 수 있다. std::set으로는 후자의 연산이 불가능하고, 따라서 오프라인+좌표압축+세그트리를 사용하거나 pbds를 알고 있었어야 한다. 우리 팀은 대회 당시에는 전자를 사용하였고, 나는 후자로 업솔빙했다.

E (S1, solved by leo020630) : 열심히 구현하면 된다. double로 되는지는 모르겠는데 나는 불안해서 long double 썼다.

F (S1, solved by leo020630) : 열심히 구현하면 된다2. 놓치기 쉬운 조건들이 있으니 잘 처리해주자.

G (P5, solved by qjatn0120) : 블럭에 항상 1이 들어옴을 캐치한다면 그리디하게 배치해줄 수 있는데, 예외 처리가 조금 필요한 것 같다. 업솔빙 예정

H (P3, solved by slah007) : 어려운 조합 문제이다. 나는 사실 아직도 풀이를 잘 모르겠는데, 사람들은 되게 많이 푼 것 같았다. 다들 너무 똑똑하다.. 업솔빙 예정

I (D4, Not solved) : 관찰을 많이 해야 풀리는 그리디 문제인 것 같다. 업솔빙 예정

J (G1, solved by slah007) : 몇 가지 관찰을 하면 쉬운 구현으로 문제를 해결할 수 있는데, 그 중 가장 어려운 관찰 단계가 _int128으로 뚫리는 것 같다. 그래서 난이도보다 솔브 팀 수가 많게 나온 것 같다.

 

내가 푼 문제는 B, E, F이다. A를 빼고 가장 쉬운 세 문제라는 점에서, 버스를 달달히도 탔다고 할 수 있다.

 

느낀 점

UCPC는 ICPC에 비해 비현역/조건 불만족 팀이 상당히 많기 때문에 12등이라는 등수는 매우 만족스럽다. 본선에서도 이 정도면 여한이 없다. 다만, 우리 팀이 원래부터 쉬운 문제의 풀이를 뽑아내는 실력과 어려운 문제를 푸는 실력의 차이가 큰 팀이라는 점과, 솔브 수 차이가 비교적 적고+틀리기 쉬운 문제들이 많은 본선에서는 페널티 관리를 오늘보다도 더 못할 가능성이 있다는 점을 감안하면 연습이 더 필요할 것 같다. 결과와 별개로도, UCPC 본선은 굉장히 오랜만의 오프라인 PS 대회라 떨린다.. (대학 오고는 처음이다) 팀명에 누가 되지 않도록 남은 기간도 열심히 해야겠다 ^^