UCPC 2025 예선

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

 

신청 마감 3일전에 팀이 결성됐다. 팀은 겨울방학 때 코포 공부를 같이 했던 gs25와 sharaelong의 소개로 이어진 gina님이었는데, 예선 때 gina님께서 시간이 안된다고 하셔서 예선은 나와 gs25 둘이서 진행했다. 둘이서 예선을 통과할 수 있을지 애매하다고 생각했는데 생각보다 대회 당시 풀이를 금방금방 떠올려서 22위로 무난하게 예선을 통과했다. 초반 한시간 정도는 gs25가 A~F, 내가 G~K를 보고 각자 문제를 풀다가 이후에는 스코어보드를 보면서 같이 생각하면서 풀었다.

 

A (+, 0:03)

gs25가 풀어왔다.

 

B (+, 0:07)

gs25가 풀어왔다.

 

C (+, 2:17)

G를 풀고 C로 넘어왔다. gs25가 나누어 놓은 케이스들을 보고 내가 보관된 구간과 쿼리 구간을 양 끝점 좌표의 합으로 정렬하고 오프라인 쿼리로 처리하면 될 것 같다는 의견을 냈고, gs25가 오프라인 쿼리를 펜윅트리를 써서 처리하면 될 것 같다는 의견을 냈다. 두 의견을 합치니 금방 풀이가 나왔고 gs25와 같이 구현해서 맞았다.

 

D (+1, 0:42)

gs25가 풀어왔다.

 

E (+, 0:16)

gs25가 풀어왔다.

 

F

C를 풀고 F와 J 중 F를 풀기로 했다. $dp$를 쓰면 될 것 같다는 것과 $a$의 누적합을 $A$, $b$의 누적합을 $B$라고 했을 때  $dp[i]= \underset{i<j,A_j\leq A_i, B_j\geq B_i}{\mathrm{max}}dp[j]+x_i$라는 것을 활용하여 좌표압축과 세그 최적화로 문제를 풀 수 있을 것 같았으나 최적화를 하는데 실패했다. 최적화를 위해 필요한 관찰인 $j<i$일 때 $B_j-A_j<B_i-A_i$인 것을 관찰하지 못했다.

 

G (+2, 1:53)

스코어 보드를 보고 G를 같이 생각하기 시작했다. $n\leq 500$, $m\leq 500$인 것을 보고 $O(n^2m)$의 복잡도까지는 돌아가겠다는 생각으로 풀이를 찾았다. 1차원에서 풀이를 먼저 생각했고, 2차원 누적합을 활용하면 $O(n^2m)$의 시간복잡도로 1차원 문제를 2차원으로 확장 가능하다는 것을 생각했다. 이것까지 생각한 뒤 최댓값 갱신을 세그먼트 트리로 하자고 내가 제안했고, $O(n^2m\mathrm{log}n)$풀이를 제출했으나 시간초과를 받았다. 이후 다시 생각을 해보니 $dp[i][j][k]$를 $i$번째 행부터 $j$번째 행까지 활용한 직사각형 중 $k$번째 열을 포함하는 직사각형 범위 합의 최댓값이라고 정의하면 $ans[x][y]=\underset{i\leq x, j\geq y}{\mathrm{max}}dp[i][j][k]$이기 때문에 누적 최댓값을 활용할 수 있다는 것을 gs25가 관찰했고 내가 이를 구현해서 맞았다.

 

H (+, 0:31)

우선 $a<b$라고 가정하고 문제를 풀기 시작했다. $b-a=1$인 경우와 아닌 경우를 나누어서 생각했다. $|a-b|>1$인 경우 $1$과 $a$, $b$와 $n$ 사이의 모든 점들을 지나고 $a$ 또는 $b$로 가야하고 $a$ 또는 $b$로 간 뒤에는 $2^{b-a-2}$를 곱해주면 되고, $b-a=1$인 경우에는 우선 $a$와 $b$를 묶어서 생각하고 묶어서 생각할 경우 $a$와 $b$를 마지막에 방문할 경우 $a$와 $b$의 순서에 따라 경우가 2배가 되므로 $a$와 $b$를 마지막에 방문하는 경우의 수를 한 번 더 더해주었다.

 

I (+, 0:16)

최댓값은 모두 띄어놓으면 자명하게 $n$이고 최솟값도 모두 붙여놓는 것이 좋다는 생각을 했다. 최솟값을 구할 때에는 bfs를 활용했는데 $x$좌표를 설정할 때 $y_i\geq y_{i+1}$일 때 x를 증가시켜야 하는데 $y_i>y_{i+1}$일 때 증가시키는 것으로 실수를 해 2번의 WA를 받았다.

 

J

F를 푸는데 실패하고 대회가 끝난 뒤 같이 J에 대해 생각을 해보았다. 이상하게 $t$가 작다는 것으로부터 $2^{20}$으로 나눈 나머지를 가지고 그래프를 만들면 쉽게 풀린다는 것을 생각했고 구현해 제출해보니 맞았다.