[PS] UCPC 2022 예선 후기

대회 종료 1시간 전 프리즈 스코어보드. 최종 스코어보드가 아님.

UCPC 2022 예선에 출전했다!

 

이번에는 현재 건국대 솔브드 기준 1등이자, 코포의 왕이신 백준 핸들명 riroan님,

항상 백준 대회에서 우수한 성적을 거두신 건국대 컴공 에이스 백준 핸들명 aru0504님이랑 함께 참여했다.

우리 셋 다 건대생이기 때문에 '일감호는우리가지킨다' 라는 팀명으로 출전했으며, riroan님이 건덕이, aru0504님이 건구스, 내가 만쥬(건대 대표 귀여운 고양이이다^^) 라는 팀원명으로 출전했다.

 

목표는 본선 진출이다.

A, B, E, F, J를 해결함으로써 5솔을 하였다!

만족스러운 성적이지만, 5솔 이상 한 팀이 꽤 많을 것으로 예상돼서 본선 진출 여부는 어떻게 될 지 모르겠다 ㅎㅎ... ㅜㅜ

 

학교 1등 팀 추가선발 15팀 이내에 해당돼서 추가선발이 되거나, 아니면 스코어보드 상으로 본선 진출 컷에 걸리길 기원한다.

 

해결한 문제: A,B,E,F,J

aru0504님이 그래프 쪽에 강하고, riroan님이 코포 스타일적인 구성적, 수학, 애드혹 쪽에 강하고, 나는 dp, 그래프 쪽을 좋아한다.

이 점을 참고해서 건대 근처 스터디룸에서 각자 파트를 한번 정리해두고, 예선을 참여하기 시작했다.

---

예선 타임라인

~00:01 A AC

예비소집일 때 A번이 계속 쉽게 나오고 있다는 스포 아닌 스포를 접한 덕분에, 이번 ucpc에서도 A를 가장 먼저 살펴보기로 했다. A는 내가 풀기로 했는데, 내가 내 스스로 문제 난이도를 잘 분별하지 못하고 무조건 들이대는 면이 있다고 생각했기 때문이다. 그래서 자진해서 풀겠다고 했다.

 

A는 N/4번만큼 long을 붙여주고, 그 뒤에 띄어쓰기와 함께 int를 출력해주면 되는 굉장히 쉬운 문제였다. 1분만에 빠르게 제출하고 AC. first solve이긴 하지만, 무려 약 30팀 정도가 1분만에 A번을 해결해버렸기 때문에 크게 의미없는 퍼솔... 

---

~00:47 E AC

이후에 각자 해결할 수 있어보이는 문제들을 찾아 보기 시작했다. riroan님은 E번이 빡구현이지만 조금만 열심히 하면 풀 수 있겠다고 하셔서 E로 바로 돌진하셨다. 나는 E 문제 비주얼이 너무 극혐스러워서 아예 보지도 않고 다른 문제로 패스. (riroan님이 풀어주시겠지~~) 이후에 aru0504님이 B, 나는 H를 보기 시작했다. 

 

일단 H는 dp 또는 분할정복 느낌인데, 사람이 풀 만한게 아닌 것 같았다. 이후에 J로 넘어갔는데, 10^18의 범위에, 두 수를 곱하는 내용이 있어서 python 유저인 riroan님과 aru0504님께 패스 (...) 다행히 riroan님이 E 4맞왜틀 후에 47분째에 AC를 받으셔서 바로 J를 봐주시기로 했다. 나는 아직도 E가 무슨 문제인지 모르는 중... 아마 나중에도 안 볼 것 같다..

---

~ 01:07 B, F AC

aru0504님이 B번을 제출하셨다가 WA를 받고, dp 또는 그리디같다는 말씀을 해주신 후에 나한테 바톤 터치 후, F로 넘어가셨다. 내가 선분 교차 ccw가 기억이 나지 않았기 때문에 해당 부분은 aru0504님과 내 ccw 템플릿을 활용하였다. 즉, 이제 내가 B, aru0504님이 F, riroan님이 J를 봐주는 중인 것.

 

B가 스코어보드를 보아하니, A 다음으로 많이 풀려 있길래 '어렵지 않다... 어렵지 않다' 를 되새기면서 풀었다. 조금 생각해보니, 순서 상관 없이 wi가 작은 순대로 베기만 해주면 최솟값이 나오는 그리디적인 문제임을 파악했다. O(N^2) 풀이도 충분히 돌아가는 N 범위여서 빠르게 제출하고 67분에 B AC. 이와 동시에 aru0504님이 F를 AC받으셨다. aru0504 피셜, F는 구현이라고 한다. 재밌다고 한다. 골드 같다고 한다. 난 문제가 기억이 안난다ㅋㅋ (aru0504님이 잘 해결했겠지~)

 

~01:47 J AC

riroan님이 J를 계속 붙잡고 있었고, 나랑 aru0504님은 스코어보드를 참고하여 다른 문제를 찾아다니기 시작했다. 스코어보드 상으로 J가 꽤 풀린 편이었기 때문에 J는 풀어야 되는 문제였다. 나중에 알고보니 pypy의 sqrt 큰수 정밀도 연산 때문에 틀린거였고, 풀이 자체는 riroan님이 생각하신 게 맞았다. 그냥 배열 A를 정렬한 배열을 B라 하고, Ai * Bi가 제곱수가 아니면 NO, 모두 제곱수면 YES인 문제였다. 어차피 두 수의 곱이 제곱수이면 swap해주는 거기 때문이다. 이 풀이법을 riroan님이 굉장히 빠르게 떠올리셨다. 역시 코포 민트인 척하는 블루 riroan님이시다. 정밀도 연산을 고치고 107분에 4맞왜틀 후 J번 AC!

 

그 와중에 나는 H를 보고 있었는데... 이 문제는 아무리 생각해도 사람이 풀만한 문제가 아닌 것 같다. dp + 분할정복인 것 같은데 확실친 않다. 플레티넘 상위권 정도라 생각.

---

~03:00

이후에 riroan, aru0504님이 D를, 나는 G를 보기 시작했다. 5솔도 꽤 좋은 성적이지만, 본선 진출 여부가 불안불안했기 때문에 한 문제를 더 풀어서 안정권으로 가고 싶어서 계속 문제풀이법을 찾아보았다. D는 riroan님이 괜찮은 풀이법을 내주셨는데, 오프라인쿼리 + 레이지세그 + 좌표압축인 것 같다고 하셨다. 풀이법을 듣고 일리가 있다고 생각하여 riroan님과 aru0504님이 빠르게 구현 시작.

 

나는 G로 가서 풀이법을 찾아보기 시작했다. G는 아직 정확한 풀이법은 모르겠지만, lower_bound를 활용한 이분탐색과 queue를 이용한 구현으로 마감 4분 전에 제출했으나, WA... 그리고 D번도 아쉽게 WA를 받고 대회가 종료됐다.

---

 

일단 결과가 22시에 나온다고 하니, 기다려봐야겠다.

오늘은 우테코든 알고리즘이든 뭐든 푹 쉬고... 낼 다시 우테코 달려야될 듯.

본선 진출 기원!! 

 

 

+) 22.07.02. 22:10 추가

교내랭킹 1위 팀 추가선발로 본선 진출에 성공했다~

본선 진출 커트라인은 7솔 (...) 이라 한다... 고일대로 고인 ps판..

first solve 라는 것 자체가 인상깊어서 기록용으로..!