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_1,N_2,\cdots N_M$ 이라고 했을 때, 모든 시간을 $R$분마다 기록하고 난 후에는

$$N_1,N_2+R,N_3+2R,\cdots ,N_M+(M-1)R$$

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

그리고 $R\ge 720$ 인 경우 또한 $R\mathbf{\text{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\ast {10}^5$$

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

 

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

 

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

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

$$=\frac{2}{N+M-2}(\genfrac{}{}{0ex}{}{N+M-4}{M-2})(\genfrac{}{}{0ex}{}{N+M-2}{M-1})$$

로 표현할 수 있었다.

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

 

 

후기

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

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

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