[알고리즘] UCPC 2022 예선 후기

제가 패널티 140분을 까먹었습니다 ㅠㅠㅠ

건국대학교에서 만난 훌륭한 실력을 가진 팀원들과 함께 UCPC를 참가하였다.

다들 실력이 좋으셔서 5솔이라는 좋은 성적을 거두었다.

팀원 : riroan, aru0504, kth990303

 

Before Contest

예비소집 문제에서 최근 UCPC에서 A번이 가장 쉽다는 힌트를 주었다. 그래서 올해도 A가 가장 쉬울 것으로 예상해서 누가 A를 풀지 정해야 했는데 kth990303님이 풀겠다고 했다. 어려운 문제도 붙잡고 있는 스타일이어서 확실하게 풀 수 있는 A를 빠르게 풀고 그동안 나와 aru0504님이 다른 문제를 보기로 했다.

나는 대회에서 문제를 딱 보고 10초 안에 풀이가 떠오르지 않으면 넘기는 성격이라 모든 문제 파악하는게 더 좋았는데 잘 된것같다.

 

00:01 A solve!

대회 시작 후 몇초동안 입장이 안됐었다.

계속 광클을 하고 kth990303, aru0504님이 들어가자마자 풀이를 바로 말해주셔서 1분만에 해결했다. 나는 B번부터 봐서 끝날때까지 무슨 문제인지 몰랐었다. ㅋㅋ

퍼솔 ㄷㄷㄷ

 

00:22 E solve!

모든 문제를 파악하고 나는 E로 돌진했다.

solved.ac의 티어산정 시스템을 구현하는 문제였다.

날짜 계산과 무지성 구현문제이기 때문에 python이 해결하기 좋은 문제였고 내가 풀기 시작했다.

그런데 몇번 실수를 해서 패널티 좀 받은 다음에 맞왜틀 좀 하다가 해결했다. (날짜계산 실수ㅠㅠ)

다른 분들은 B, F를 풀고 있었고 J번이 코포 스타일이라고 하셔서 내가 바로 J를 풀기로 했다.

 

00:47 B, F solve!

스코어보드를 봤을 때 B,F,J가 많이 풀려있어서 이 문제들은 꼭 풀었어야 했다.

B, F를 거의 동시에 해결했다.

B번은 아무리 봐도 선분교차판정인데 생각보다 많은 사람이 풀어서 다른 풀이가 있는 문제인가 하며 잠깐 길을 잃었었다고 한다.

47분에 kth990303님이 선분교차판정으로 해결하고 웰노운이 되었다.

F번은 aru0504님이 해결했다.

단순 구현문제였는데 E보다 지문이 길고 읽기도 힘들었다.

aru0504님이 잘 분별하셔서 다행이다. (내가 풀었으면 문제 읽는데만 오래걸렸을텐데..)

 

01:48 J solve!

내가 E를 풀고 J를 풀기로 했는데 진짜 코포스타일이어서 신기하고 문제가 재밌었다.

$AB$가 제곱수이고 $BC$가 제곱수일때 $AC$도 제곱수라는 사실을 이용하는 문제였다.

그런데 제한이 $10^{18}$이어서 곱하면 $10^{36}$까지 나올 수 있었다.

루트하고 제곱하는 방식은 수가 너무 커서 정밀도 오류가 났다.

그 후 얼마전에 골랜디할 때 푼 문제가 생각나서 이분탐색으로 제곱근을 구현했는데 TLE가 나왔다.

그렇게 소인수분해의 유혹을 계속 받아서 폴라드로를 쓸까 생각했는데 복잡도 계산상 안됐다. ($O(N \max(A_iA_j)^{\frac{1}{4}})$)

그러다 isqrt가 pypy버전 상 된다는 사실을 깨닫고 isqrt를 사용하여 해결했다.(정해는 gcd로 나눠서 제곱수를 구하는 문제)

https://www.acmicpc.net/board/view/80577

글 읽기 - 도데체 어떻게 attributeerror 가 뜨는거죠?

전에는 백준 pypy로 isqrt가 불가능했는데 대회 pypy는 버전이 높아서 가능했었다고 한다.

첫 제출이 35분이었던걸 보면 꽤나 오랫동안 헤맨 문제였던거 같다.

 

03:00

그렇게 나와 aru0504님은 D를 보고 kth990303님은 G, H를 보고 있었다.

D의 대략적인 풀이가 떠올라서 남은 약 40분여 시간동안 구현을 시도하고 있었다.

그때 생각났던 풀이가 오프라인쿼리 + 레이지 세그 + 좌표압축 + 이분탐색 이라는 해괴망측한 풀이였는데 해결하진 못했다.

나중에 풀이를 보니 많이 간단해보였다.

pbds라는 처음 듣는 자료구조를 사용한다고 하고 실제로 출제 의도도 pbds라는 자료구조를 널리 알리기 위해서 출제했다고 한다.

kth990303님도 G를 해결하는데 실패하셨다고 한다.

C, I는 프리즈 될 때까지 아무 팀도 풀지 못해서 바로 포기했었다.

 

후기

대회에서는 제출하고 퍼센트 올라가는게 보이지 않아 많이 답답했었다.

틀렸습니다가 나오면 평소보다 더 절망스러웠지만 맞았습니다가 나오면 훨씬 더 감격스러웠다.

긴장해서 그런지 평소에 잘 안하던 실수도 자주 나온것 같다. (이것도 실력이겠지)

4학년이기 때문에 올해가 마지막 UCPC가 되겠지만 좋은 팀원들과 많은 문제를 풀 수 있어 재밌었고 아쉬움이 남지 않았다.

 

저희 본선가요

다행히 학교 1등 추가선발 조건을 만족하여 본선에 진출하게 되었다!

본선때 재밌고 좋은 추억 만들고 와야겠다. (1솔은 할 수 있으려나?)