Codeforces Round 856 (Div.2)

우선 시작이 오전 3시인줄 알았는데, 알고보니 2시 35분 시작이라 약 30분가량 날려버리고 Round를 진행하였다.

 

A. Prefix and Suffix Array

https://codeforces.com/contest/1794/problem/A

Problem - A - Codeforces

알고리즘 분류: 브루트포스, 문자열

 

처음 이 문제 제목을 보고 접미사 배열과 lcp 배열$ ( $Suffix array & Lcp array$) $를 떠올렸다. 그리고 코딩을 시도해보던 중 10분 정도 지난 후 문득 든 생각은 lcp 배열을 사용할 경우 문자열 > 접미사 배열로 만들게 되는데 지금 문제는 접미사 배열 > 문자열로 변환하는 것이므로 시도 방법 자체가 잘못되었다는 것을 깨달았다.

그리고 다시 보던 중 생각해낸 알고리즘은 입력되는 prefix들이 문자열의 suffixes이기 때문에 문자열의 길이를 $ L $이라고 하면 길이가 $ L - 1 $인 문자열 2개를 비교해서 원래 문자열을 찾을 수 있다는 것이다.

길이가 $ L - 1 $인 문자열을 각각 $ A, B $라고 하고 $ A, B $를 아래와 같이 정의하면

$$ A := a_{1} a_{2} \cdots a_{L - 1} $$

$$ B := b_{1} b_{2} \cdots b_{L - 1} $$

원래 문자열은 $ Ab_{L - 1} = a_{0}B $인 경우 또는 $ Ba_{L - 1} = B_{0}A $ 경우 둘 중 하나이다.

원래 문자열을 구하였으므로 펠린드롬 체크를 하여 결과를 출력하면 된다.

AC$ ($00:59$ )$

 

B. Not Dividing

https://codeforces.com/contest/1794/problem/B

Problem - B - Codeforces

알고리즘 분류: 그리디 알고리즘

 

문제를 귀납적으로 접근해보면 $ a_{1} \sim  a_{i} $가 문제 조건에 맞게 변형되었다면, $ a_{i + 1} $를 변형하여도 $ a_{1} \sim  a_{i} $는 그대로 조건에 부합하다는 것을 알 수 있다.

따라서 $ a_{1} $ 부터 그리디하게 접근하면 $ a_{i + 1}\ \equiv \ 0 \ (mod \ a_{i}) $인 경우 $ a_{i + 1} $를 1 증가시킨다 $ ( $-1 WA$ ) $

 

다시 한번 생각해보니 $ a_{i} $가 1인 경우 $ a_{i + 1} $를 아무리 변형하여도 $ a_{i + 1}\ \equiv \ 0 \ (mod \ a_{i}) $이기 때문에 이 경우 $ a_{i} $ 를 1 증가시킨 후 다시 한번 판별한다. $ ( $-2 WA$ ) $

$ 1 \ 1 \ 3 $와 같은 입력이 주어지면, $ a_{1} $가 $ 1 $이므로 $ 2 \ 1 \ 3 $가 된다. $ a_{2} $는 $ a_{1} $로 나누어 떨어지지 않으므로 그대로 진행한다. $ a_{2} $가 $ 1 $이므로 $ 2 \ 2 \ 3 $이 된다. 이 때 전에 탐색했던 $ a_{2} $가 a_{1}로 나누어 떨어지게 되어 문제가 발생한다. 따라서 모든 입력을 받을 때 $ 1 $인 경우 모두 $ 2 $로 변경한다. 그리고 만약 $ a_{i + 1} $이 $ a_{i} $로 나누어떨어지면 $ 1 $ 증가시킨다. 이러면 각 $ a_{i} $마다 최대 $ 2 $ 증가하므로 최대 $ 2n $ 번 증가한다.

AC$ ( $01:20$ ) $

 

C. Scoring Subsequences

https://codeforces.com/contest/1794/problem/C

Problem - C - Codeforces

알고리즘 분류: 그리디 알고리즘

 

$ [a_{1}, a_{2}, \ \cdots \ a_{k}] $ 중 최댓값을 가지는 구간을 $ [a_{i}, a_{i + 1}, \ \cdots \ a_{j}] $라고 하자. 그러면 $ a_{i} \ \leq \ a_{k + 1} $이기 때문에 $ j = k $이고,

구간 $ a_{i}, a_{i + 1}, \ \cdots \ a_{k}] $의 최댓값 $ \leq $ 구간 $ [a_{i + 1}, a_{i + 2}, \ \cdots \ a_{k + 1}] $ 이다.

따라서 queue에 $ a_{k + 1} $ 값을 넣고 front부터 뺐을 경우와 안 뺏을 경우를 비교하여 빼지 않은 경우가 더 큰 경우까지 반복한다.$ ( $그리디$ ) $

AC$ ( $01:52$ ) $

 

최종 3634등으로 마무리하였다. 30분 일찍 모든 문제를 풀었다고 계산했을 때 1500등 정도 될수 있었으니, 약간 아쉬운 Round였다.