SCPC 2023 Round 1 후기와 풀이

 

SCPC 2023 Round 1에 참가했습니다. 간단히 후기와 풀이를 적어보려고 합니다.

 

올해는 Round 1의 모든 문제에서 만점, 총 900/900점을 받았습니다. 작년 Round 1에서 1번 문제 100/100점, 2번 문제 10/140점, 3번 문제 0/140점, 4번 문제 35/190점, 5번 문제 12/230점으로 총 157/800점을 받은 것에 비하면 장족의 발전입니다.

 

이 글에서 소개하는 풀이는 모두 제 풀이입니다. 정해와 다를 수 있습니다.

 

문제 1 : 증강현실 배달 안경

$Ax + By = N$을 만족하는 음이 아닌 모든 정수 $x, y$에 대해 $\max(x + y)$를 구하는 문제입니다. $x$를 기준으로 순회하면 $\mathcal{O}(N / A)$ 시간에 답을 구할 수 있습니다.

 

코드 : https://github.com/manoflearning/cp-codes/blob/main/SCPC/SCPC%202023/Round%201/1.cpp

 

문제 2 : 딸기 수확 로봇

태그 : 그리디 알고리즘, 시뮬레이션

 

로봇이 출발한 이후에 로봇의 이동 방향은 변경하지 않거나, $1$번 변경하는 것이 최적입니다. 로봇의 이동 방향을 변경하지 않는 경우, 원점에서 좌로 이동하는 경우와 우로 이동하는 경우가 있습니다. 로봇의 이동 방향을 $1$번 변경하는 경우, 딸기들의 좌표 중 한 곳에서 변경하는 것이 최적입니다. 절댓값이 $D$ 미만인 각각의 딸기의 좌표에서 이동 방향을 변경할 수 있습니다. 모든 경우에 대해 수확하는 딸기의 개수를 구하고, 그 중 최댓값을 출력합니다.

 

코드 : https://github.com/manoflearning/cp-codes/blob/main/SCPC/SCPC%202023/Round%201/2.cpp

 

문제 3 : 장난감

태그 : 애드 혹

 

먼저 $\sum A_i \ge N$인 경우 답은 $1$입니다. 충분히 쇠구슬을 이동시키고 나면 모든 $A_i$ 값이 $1$ 이상이고, 따라서 장난감의 상태는 변하지 않습니다. 또한 $\sum A_i = 0$인 경우 역시 답은 $1$입니다.

 

이제부터 $0 < \sum A_i < N$이라고 가정하겠습니다. $A = \{ 0, 0, 2 \}$인 경우를 관찰해 봅시다. 이는 $A = \{ 0, 1, 1 \}$인 경우와 동치입니다. 일반화하여 $A = \{ 0, 0, \dots, x \}$인 경우를 관찰해 봅시다. $A = \{ 0, \dots, 0, 1, \dots, 1 \}$($1$의 개수는 $x$개)인 경우와 동치입니다. 또한 $A = \{ 0, 0, 1, 2 \}$인 경우는, $A = \{ 0, 0, 2, 1 \}$인 경우와 동치입니다. 이렇게 $2$ 이상인 $A_i$ 값이 존재하는 상태를, 모든 $A_i$가 $0$ 또는 $1$인 상태로 치환할 수 있습니다. 이제 모든 $A_i$가 $0$ 또는 $1$인 경우의 답을 구해야 합니다.

 

모든 $A_i$ 값이 $0$ 또는 $1$인 경우 답은 $N$의 약수 중 하나입니다. $N$의 모든 약수 $t$에 대해, 현재 장난감의 상태와 $t$초 후 장난감의 상태가 일치하는지 검사하여 답을 구할 수 있습니다. 모든 약수를 $\mathcal{O}(\sqrt{N})$ 시간에 구할 수 있고, 약수의 개수를 $D$라 할 때 $\mathcal{O}(D N)$ 시간에 모든 약수 $t$에 대해, 현재 장난감의 상태와 $t$초 후 장난감의 상태가 일치하는지를 검사할 수 있습니다. 따라서 $\mathcal{O}(\sqrt{N} + D N)$ 시간복잡도로 문제를 해결할 수 있습니다. (또는 라빈 카프 알고리즘으로 풀 수도 있습니다. 비트 문자열 $A$가 매 초마다 한 칸씩 cyclic shift할 때 초기 상태와 같아지는 가장 빠른 시간 $t$가 답입니다.)

 

코드 : https://github.com/manoflearning/cp-codes/blob/main/SCPC/SCPC%202023/Round%201/3.cpp

 

문제 4 : 최적의 프로세스 수행 순서

태그 : 동적 계획법, 라빈 카프 알고리즘, 이분 탐색, 세그먼트 트리

 

먼저 $O(N^2)$의 시간 복잡도를 가지는 동적 계획법 풀이를 생각할 수 있습니다. $dp[i]$는 조건에 맞게 $R[i \dots N]$을 나눌 수 있는 부분의 개수의 최솟값입니다. 만약 $R[i \dots N]$를 조건에 맞게 나눌 수 없다면, $dp[i] = \infty$입니다.

 

$R[i \dots N]$과 $P$의 최대 공통 접두사의 길이가 $l$이라고 할 때, $dp[i] = 1+ \begin{align*} \min_{i < j , j \leq i + l}(dp[j]) \end{align*}$입니다. 최대 공통 접두사의 길이 $l$을 구하는데 $\mathcal{O}(N)$, $dp[i]$를 구하는데 $\mathcal{O}(N)$의 시간이 필요합니다.

 

(이 문단의 풀이는 정해와 다릅니다.)

$R[i \dots N]$과 $P$의 최대 공통 접두사를 이분 탐색으로 구해 봅시다. 이분 탐색의 각 탐색마다, $m := \lfloor (l + r) / 2 \rfloor$에 대해서 $R[i \dots i + m]$과 $P[0 \dots m]$이 일치하는지 검사합니다. 이때 라빈 카프 알고리즘으로 전처리를 해두면, $R[i \dots i + m]$과 $P[0 \dots m]$의 일치 여부를 $\mathcal{O}(1)$ 시간에 검사할 수 있습니다. 따라서 최대 공통 접두사의 길이를 $\mathcal{O}(\log N)$ 시간에 구할 수 있습니다.

 

이제 $dp[i]$를 구해야 합니다. 점화식을 잘 살펴보면, 배열의 연속된 구간에서 가장 작은 값을 구하는 꼴이라는 것을 알 수 있습니다. 따라서 세그먼트 트리로 해결할 수 있습니다. $\mathcal{O}(\log N)$ 시간에 해결할 수 있습니다.

 

따라서 전체 과정을 $\mathcal{O}(N \log N)$ 시간에 해결할 수 있습니다.

 

코드 : https://github.com/manoflearning/cp-codes/blob/main/SCPC/SCPC%202023/Round%201/4.cpp

 

문제 5 : 타이젠

태그 : 컨벡스 헐 트릭

 

각각의 수행 구간에서의 소비 전력량은 $p_1 \times (d_i - r_i)$입니다.

 

각각의 수면 구간에서의 소비 전력량은 $\min(p_j \times (r_{i+1} - d_i) + (w_j - w_1))$입니다. 이는 $m$개의 일차 함수 $y = p_j x + (w_j - w_1)$가 주어질 때 $x(= r_{i+1} - d_i)$ 좌표에서 $y$의 최솟값을 구하는 문제로 생각할 수 있습니다. 따라서 컨벡스 헐 트릭을 사용하여 문제를 풀 수 있습니다.

 

답은 각각의 수행, 수면 구간에서의 소비 전력량의 합입니다.

 

개인적으로 컨벡스 헐 트릭 유형에 능숙하지는 못했는데, 우연히 대회 시작 직전에 컨벡스 헐 트릭과 리차오 트리를 공부했었습니다. 덕분에 쉽게 문제를 풀 수 있었습니다.

 

코드 : https://github.com/manoflearning/cp-codes/blob/main/SCPC/SCPC%202023/Round%201/5.cpp