UCPC 2025 예선 후기
7월 13일에 UCPC 2025 예선이 있었습니다.
결론부터 말하자면 47등 전 처음으로 본선진출에 성공했습니다!
팀 구성
이번 년도까지 같은 동기였던 팀원들이 군대에 가있는 상태고 저도 휴학중이었기에 팀원이 없어 고민했는데, 때마침 같은 학교 선배분인 skeep194 코포 퍼플 고수분이 팀원을 찾고 계시길래 팀원이 되었습니다. 이후에 skeep194 선배분이 같은 알고리즘 동아리인 고리에서 holmane333 선배분을 데려와 skeep원정대 (we12223,skeep194,holmane333) 팀이 완성되었습니다.
팀명은 "skeep원정대" 로 정했습니다. skeep 선배분이 학교에서 네임드이시기도 하고 월파에 갔다오신 분이셨기에 정말 좋은 팀명인것 같습니다. (저는 사실 skeep 문자열 문제를 만들정도로 팬이기도 합니다.)
대회 과정
예선 대회는 경북대학교 근처 스터디카페에 3명이 다함께 모여 진행했습니다.
대회시작전 저는 A번을 보기로 하고 skeep194 선배님은 B번을 보기로 했습니다.
holmane333 선배님은 나머지 문제를 봤습니다.
A (00:01) AC
가장 쉬운 문제가 A번이기에 지문을 빠르게 봤는데, 남은 거리를 300초 안에 갈 수 있는지 여부를 판단하는 간단한 사칙연산 문제였습니다.
바로 코드 짜서 AC
B (00:05) AC
저는 A번을 풀고 B로 넘어왔는데, skeep194 선배분이 B가 간단한것 같아 코드를 짜신다고 해서 AC
이후 스코어보드를 보니 E번과 I번을 푼팀이 좀 있었습니다.
그래서 저와 holmane333 선배님은 E번을 보고 skeep194 선배님은 I번을 봤습니다.
I (00:24) AC
저는 E번을 계속보고 있었는데
skeep194: 그냥 그리디인데?
하시면서 바로 풀이를 짜서 풀어오셨습니다.
E (00:38) AC
이 문제는 N개의 방음벽이 나열되어 있을 때 특정 방음벽 사이에 소음이 있는 콘서트가 열려 양쪽으로 소음이 흡수 되면서 각 쿼리 마다 특정 방음벽에 흠수된 소음을 출력하는 문제였습니다.
이 문제를 저와 holmane333 선배님 보고 있었는데, 제가 딱 보면서 느낀건 Q가 최대 20만이고 쿼리 마다 구간에 대해서 업데이트를 해줘야했습니다.
그리고 한가지 관찰한건 소음이 퍼질 때 min(dc,x) 여서 퍼지는 끝지점 전까지는 지금 원소를 더한 값이고 마지막만 다르게 더해주면 된것 같았습니다. 일단 뭔가 이분 탐색으로 마지막으로 소음이 흡수되는 지점을 구하고 하떨별 문제 같은 레이지 세그를 쓰는 레이지 세그 + 이분탐색 문제인것 같았습니다. 이에 holmane333 선배님도 그런것 같다고 하셔서 그런것 같았는데 막상 스코어보드를 보니 이 정도 난이도에 많이 풀리는 건 아닌것 같아서 다른 풀이를 계속 생각하고 있었습니다.
때마침 I 번을 풀고 달려온 skeep194 선배님이 "이거 그냥 계속 2배로 업데이트 되면 log(n) 만에 되서 나이브 돌아갈듯" 이 한마디로 바로 푸셨습니다. (역시 퍼플은 다르다)
그후 저와 holmane333 선배님은 D번을 잡았고 skeep194 선배님은 H번을 잡았습니다.
D +1
이 문제는 지문이 조금 난해했는데, 문제 자체는 명확했습니다. N개의 구간이 주어지는데, 각 쿼리 마다 비어있는 구간에 새로운 구간인 T를 둘 수 있는 개수를 찾으면 되는 문제 였습니다. 이 문제에 대해 holmane333 선배님과 생각하던 중 스위핑, 구간합을 쓰는 것 같다에서 힌트를 얻어 저는 바로 1 과 -1를 이용한 imos로 빈 구간을 찾아줬고 빈 구간의 길이를 구간합에 넣고 이분탐색으로 구하는 풀이를 짰는데 하필 이분탐색할때 놓을 수 있는 구간이 없는 경우를 체크를 안해서 한번 틀렸습니다.
D (00:58) AC
코드를 보던 중 이분탐색 도중 예외 처리를 안한걸 발견하여 수정 후 제출 AC
이제 스코어보드를 봤는데 G번과 H번이 좀 풀려있었습니다.
이 당시 H번을 skeep194, holmane333 선배님이 보고 계셨는데 도대체 어떤 방식으로 접근 해야하는지 부터 문제를 겪고 있었습니다.
그리디, dp, 조합론 중 무엇을 해야하는지 아이디어 싸움을 하고 계셨습니다. 그래서 전 H를 이때 잠깐 봤는데 이건 딱봐도 수학 능지 문제 느낌이라 일단 G를 잡았습니다.
G
G는 문제자체는 정말 간단했습니다. N <= 500, M <= 500 정도의 2차원 배열이 주어지면 각 원소를 포함하는 최대 직사각형 부분합을 출력하면 되는 문제였습니다. 생각하다가 n ^ 4 풀이를 떠올렸는데 그 이상의 해결점이 보이지 않았습니다. 흠 이게 dp인가.. 아니면 세그? 인가 하면서 생각을 해봤는데 아무리 봐도 안될것 같아 난해하던 H번에 합류했습니다.
H (02:15) +2 AC
거의 1시간 넘게 이 문제를 3명에서 함께 보고 있었는데 holmane333 선배님이 조합론 식을 설명하시면서 답을 찾아냈고 이걸 칠판에 적어가면서 skeep194, holmane333 분이 서로 토론하시면서 식을 완성했습니다. 식이 좀 이상해서 이게 될까 싶었지만 결국 holmane333님이 풀어내셨고 6솔에 성공했습니다.
G
시간이 남아 그나마 만만한것 같은 G번 문제를 다 같이 봤습니다.
뭔가 dp를 쓰는 문제 같은데 어떻게 접근해야하는지 잘 떠오르지가 않았습니다.
G번을 보며 머리를 싸매고 있다가 대회가 끝났습니다.
이번 대회는 제가 처음으로 UCPC 본선에 진출한 해이기에 정말 뜻깊은 경험이었습니다.
대회를 치루면서 제 실력이 많이 부족하다는걸 느꼈고 수련을 좀 해야할 것 같습니다.