대회후기: Codeforces Global Round 7

벌써 네번째 퍼플 진입이다.

다섯번째는 필요 없기를 바란다.

---

A: Bad Ugly Numbers

혼자 생각을 너무 많이하고 어렵게 푼 것 같다.

7분에 AC

---

B: Maximums

정의대로 하면 된다.

13분에 AC

---

C: Permutation Partitions

주어진 permutation을 $k - 1$개의 칸막이를 설치함으로써 각각 perumutation에서 연속된 $k$개의 partition으로 나눠야 한다.

이때, 각 partition의 max값의 총합을 최대화하고자 한다.

최댓값은 무엇이며, 최댓값을 갖는 분할의 경우의 수는 몇가지인가?

 

어려운 문제인 듯 했으나, 최댓값을 최대한 키우기 위해서 어떻게 분할해야 좋을지 생각하는 순간 해답이 보였다.

최댓값을 키우기 위해서는 각 partition마다 최대한 큰 값을 넣어야 한다. 그런데 생각해보면 permutation 전체에서 제일 큰 $k$개의 값을 각각의 partition에 넣어줄 수 있다.

 

따라서 최댓값은 제일 큰 $k$개 값의 합이다. 분할의 경우의 수는 trivial해진다.

23분에 AC

---

D1: Prefix-Suffix Palindrome (Easy version)

주어진 문자열의 prefix와 suffix를 concatenate해서 만들 수 있는 palindrome중 제일 긴 문자열을 찾는 문제이다. 단, 결과로 나오는 문자열은 처음에 주어진 문자열보다 길 수 없다(i.e. prefix와 suffix는 겹치지 않는다).

 

우선, 처음 주어진 문자열의 양쪽 끝이 같은 동안 계속 양끝을 pop해서 greedy하게 prefix와 suffix를 만들면 된다.

이후 남은 문자열에 대해, 제일 긴 prefix palindrome 혹은 suffix palindrome을 찾는 것으로 문제가 회귀된다.

여기까지는 easy version과 hard version에서 동일하다. 이후:

 

Easy version은 $O(n^2)$으로 가능하기 때문에 naive하게 전탐색을 진행해 빠르게 제출하였다.

37분에 AC

 

D2: Prefix-Suffix Palindrome (Hard version)

Hard version은 이 게시물을 참고하여 KMP로 구현하였다. 원래 문자열 s에 대해 t = s + '*' + s[::-1]라고 정의하고 t에 대해 KMP를 수행하여 해결하였다. KMP 공부를 미루고 있었는데, 대회 시간에 급하게 처음 구현해보았다.

1시간 8분에 AC

---

E: Bombs

얘는 못풀었는데, 시도 과정에서 작성한 세그트리 코드가 왜 터지는지 도저히 모르겠다. 분석 필요.

 

UPD) 코드의 세그트리 부분에 문제가 있던 것이 아니라, 크기가 n인 std::vector에 1에서 n까지의 1-base index를 사용해서 발생한 오류였다. 다만 오류가 터지는 부분이 문제의 vector를 사용하는 부분이 아닌 세그트리 코드 내부에서였기 때문에 버그의 원인을 특정짓기까지 너무나 오래 걸렸다. 아니 도대체 C++은 왜 엉뚱한 부분에서 오류를 띄우지???

---

총평

KMP 공부하기.

세그트리 코드 분석하기.

 

레이팅 변화 1872 + 101 = 1973

My Performance: ★★★★☆

 

연습지

없다 ㅎ