UCPC 2025 본선

https://www.acmicpc.net/contest/view/1531

 

 

6월 말에 UCPC를 같이 나가자고 했던 gs25와 sharaelong의 연결으로 알게 된 gina님과 나로 UCPC 팀이 결성되었다. 팀이 늦게 결성되었다 보니 예선을 나와 gs25 둘이서 쳐서 통과한 뒤 팀 연습을 두 번 하고 본선을 치르게 되었다. 최종적으로 10등 4등상을 받게 되었고 생각했던 것 보다 좋은 결과가 나와서 만족스럽다.

 

I (+, 0:09)

정렬하고 배열의 값이 모두 0이라면 0, 아니라면 $mex+1$의 값을 출력하는 문제이다. 대회 시작하고 쉬워보이길래 내가 잡았다.

 

E (+, 0:31)

스코어보드를 보니 많이 풀렸길래 gina와 gs25가 풀이를 같이 생각하고 풀었다.

 

C (+1, 1:01)

gs25가 풀이를 생각해 gina와 논의 후 맞는 방향이라는 결론을 내려 풀이를 작성하였다.

B (+, 1:54)

내가 문제를 보고 $M$이 크기 때문에  $A_i-k$의 누적 합과 이분 탐색을 써야할 것 같다는 의견을 gs25에게 전달했고 gs25가 풀이를 구체화하여 구현했다.

 

H (+3, 2:43)

gina가 처음에 이 문제를 잡았고 WA를 한 번 받았다. casework가 많은 문제여서 이후에도 WA를 2번 받았지만 결국 맞았고 이 문제를 맞은 것이 우리 상이 5등상에서 4등상으로 올라가는 데 결정적인 역할을 했다.

 

A (+1, 3:33)

내가 정답이 $ \frac{leaf+1}{2}$이고 leaf 별로 방향을 하나씩 부여하면 될 것 같다는 아이디어를 떠올렸고 이를 gina에게 설명하니 리프별 방향을 배정하는 방법을 듣고 이를 내가 구현하였다. 구현할 때 lca를 활용했는데 lca보다 그래프 탐색으로 경로를 찾는 것이 구현의 복잡성이 조금 줄어들었을 것 같다는 생각이 든다.

 

K (+3, 4:38)

내가 2차원 dp식을 만들고 세그로 최적화할 수 있지 않을까 라는 물음을 던지고 A를 구현하러 갔다. 그 사이 gina가 dp식을 새로 만들고 이를 세그로 최적화하는 풀이를 작성했다.

 

G

gina가 K를 구현하는 동안 gs25와 G의 풀이에 대해 해싱과 문자열을 활용하는 방향으로 논의를 했으나 K에서 한 번 WA를 받은 뒤 테케를 만들어보는 데 남은 시간을 사용했다. K를 맞은 뒤에는 남은 시간과 풀이 구체화 측면에서 모두 발목이 잡혀 풀지 못했다.