SUAPC 2023 Winter 후기

여기에서 말하는 시간 개념은 대회 시작 후 경과한 시간으로 나타내었다.

 

 

K. 시계 맞추기

https://www.acmicpc.net/problem/27532

27532번: 시계 맞추기

체감 난이도: Silver ~ Gold

알고리즘 분류: 브루트포스

 

처음에 팀원 3명$ ( $본인 포함$ ) $끼리 문제를 나눠서 문제 알고리즘 체크를 하였는데, 다른 팀원이 이 문제를 dp나 그리디일 것으로 예상하여 보류한 상태로 그나마 자신있던 수학문제인 L번을 풀고 있었다. 하지만 접근방식을 고민하다가 너무 안 풀려서 K번을 보는데 브루트포스로 충분히 풀릴 것 같아 45분 경부터 풀기 시작하였다.

 

우선 입력 시간 $ N $은 낮과 밤의 구분이 없다고 하니 00:00 ~ 11:59 즉 12 * 60 = 720 가지의 경우의 수가 존재한다. 따라서 HH:MM으로 나타내져 있는 시간을 분으로 환산하여 0 ~ 719로 나타낼 수 있다.

입력된 $ N $을 분으로 환산한 값들을 $ N\textit{}_{1}, N\textit{}_{2}, \cdots N\textit{}_{M} $ 이라고 했을 때, 모든 시간을 $ R $분마다 기록하고 난 후에는

$$ N\textit{}_{1}, \ N\textit{}_{2} + R, \ N\textit{}_{3} + 2R, \ \ \ \cdots \ \ \ ,N\textit{}_{M} + (M - 1)R $$

로 표현할 수 있다. 앞서 말했듯이 환산된 분은 최대 719분까지만 가능하므로 모든 값들을 modulo 720 한다.

그리고 $ R \geq 720 $ 인 경우 또한 $ R \ \textbf{mod} \ 720 $ 한 경우와 동일하므로 $ R $이 0 이상 720 미만인 경우만 고려하면 된다.

시간복잡도는

$$ O(720M) \simeq 10^{6} $$

로 1초 안에 해결 가능하다.

 

52분에 퍼솔하였다.

 

 

L. 따로 걸어가기

https://www.acmicpc.net/problem/27533

27533번: 따로 걸어가기

체감 난이도: Diamond

알고리즘 분류: 정수론, 집합론

 

이 문제를 처음부터 잡고 계속 안 풀려서 중간중간 팀원들 반례도 찾아주고 다른 문제도 찔러보다가 120분 경에 다시 맘 잡고 본격적으로 풀기 시작하였다. 처음에는 두 토끼가 이동할 수 있는 모든 경우의 수 $ (\frac{(N+M)!}{N!M!}) ^ 2 $에서 포함-배제 원리로 빼 나가려고 접근하였으나, $ O(N ^ 2) $의 시간 초과로 인하여 다른 방법을 구상하였다.

이전에 풀었던 문제 중에 이 문제와 비슷한 문제를 Catalan number를 활용하여 푼 적이 있었는데, 이 문제를 뒤크 문자열로 변형하여 계산해보려 했으나, 뒤크 문자열 개수를 세기 위해서는 짝수여야 하는데 $ N+M $이 짝수라는 보장이 없고, 뒤크 문자열과 약간 다른 형태라고 생각하여 이 방법 또한 포기하고 다른 방법을 구상하였다. $($대회가 끝나고 해설을 보니 Catalan number를 활용한 풀이가 정해가 맞았다$)$

결국 선택한 것은 정수론을 활용한 수열의 일반항을 찾는 것인데, 대회에서 사용하기에는 매우 비효율적인 방법이었다. 하지만 운이 좋게도 예상보다 금방 구해져서 다행이었다고 생각한다.

 

우선 경우의 수를 $ f(N, M) $이라고 하자.

$ N = 2 $ 또는 $ M = 2 $인 경우 $ f(N, M) = 2 $이다. 이는 서로 경로를 바꾸는 것 이외에는 경우의 수가 없다.

이를 초항으로 잡고 나머지 수열들의 관계를 정리하여 일반항을 도출 보았더니

$$ f(N,M) = 2 \prod_{i = 1}^{M - 2} \frac{(N + i - 2)(N + i - 1)}{i(i + 1)} $$

로 나타낼 수 있었다.

시간복잡도는 분자와 분모를 modulo $10^9+7$ 하며 계산한 후 분모 값의 역원을 곱해주는 것이 되므로

$$ O(M + log(10^9+5)) \simeq 2 * 10^{5} $$

로 1초 안에 해결 가능하다.

 

225분에 AC. $($아쉽게 퍼솔은 224분$)$

 

이후 대회 풀이를 보니 조합론으로 푸는 것을 목표로 출제하셨다고 하셔서 수열을 정리해 보니

$$ f(N,M) = \frac{2}{N+M-2}\binom{N+M-4}{N-2}\binom{N+M-2}{N-1} $$

$$ = \frac{2}{N+M-2}\binom{N+M-4}{M-2}\binom{N+M-2}{M-1} $$

로 표현할 수 있었다.

이는 조합론에서 사용되는 Narayana number 형태이다.

 

 

후기

나머지 문제도 몇 문제 더 풀어 5 Solve하였지만, 몇개 문제에서 특정 반례의 벽을 넘지 못하고 6 Solve의 벽을 넘지 못하고 11등으로 대회를 마무리 하였다.

10등까지 수상하여 수상권 밖이지만 특별상$($수상권 제외 학교별 상위 1팀$)$은 받게 되었다.

작년 9월에는 10등을 하여 수상을 하였는데 이번 대회는 눈앞에서 수상권을 놓쳐 많이 아쉬웠고, 다른 대회들을 앞서 중상급 수준 이상 알고리즘 공부를 좀 더 해야할 듯 하다.