Codeforces Global Round 7 후기

A. Bad Ugly Numbers

n = 1일 때 -1을 출력하고

나머지는 23, 223, 2233, 22223, 222223, 2222233, ....

n-1개의 2와 1개의 3으로 채우는데 수의 합이 3의 배수가 되면 3의 갯수를 한개 늘린다.

 

B. Maximums

b_i = a_i - x_i이고 b1 = a1이므로

모든 b_i에 대해서 a_i = 최댓값 + b_i이며

b_i < 0 이면 a_i가 최댓값보다 작고

b_i > 0 이면 a_i가 최댓값보다 크므로 최댓값을 갱신한다.

 

 

C. Permutation Partitions

1...k번째 최댓값은 무조건 포함하도록 segment를 나눠야한다.

그래서 1...k번째 최댓값을 m_1, m_2, ... , m_k라고 하고

 m_i와 m_i+1 사이의 경계를 x_i라고 하면

각 segment는 [1, x_1], [x_1+1, x_2], ... , [x_k-1+1, n]이다.

따라서 각 x_i의 후보의 갯수를 구하고 모두 곱하면 된다.

 

 

D. Prefix-Suffix Palindrome

D1은 easy 버전으로 문자열의 길이의 합이 5000이고

D2는 hard 버전으로 문자열의 길이의 합이 10^6이다.

 

qwabbaxyzyxwq로 예를 들어보자.

 

1. 일단 대칭을 이루는 prefix, suffix의 최대 길이를 구한다. (그리디하게 최대길이를 구해도 되는 이유는 곧 설명한다.)

최대 길이 대칭인 prefix와 suffix를 각각 L, R이라 하고 중간 string을 S'라 하자

그럼 S = L + S' + R이다.

 

 

2. 그리고 S'의 맨 앞 / 맨 뒤에서 최장 팰린드롬을 구한다.

둘 중에 제일 긴게 답이다.

 

 

3. 정당성

생각하는게 쉬울지도 모른다. 그림으로 보면 당연하다.

아래는 대칭 prefix suffix의 범위, 그리고 팰린드롬의 범위를 그림으로 나타낸 것이다.

정리1. 대칭인 prefix와 suffix를 최대로 늘리지 않을 때의 해는 최대로 늘렸을 때의 해보다 작거나 같다.

증명. 각 경우에 대해서 최대로 늘리지 않은 경우를 생각해보자.

 

i) 최대 대칭인 prefix와 suffix가 팰린드롬의 중심을 포함하지 않는 경우

보면 위 그림과 비교해보면 바로 알지 모르겠지만

대칭인 prefix와 suffix의 길이가 k만큼 줄면 팰린드롬의 반지름도 k만큼 늘어난다.

따라서 이 경우 대칭인 prefix와 suffix의 길이가 줄어도 최대 대칭인 prefix와 suffix의 해와 길이가 같다.

 

ii) 대칭인 prefix와 suffix가 팰린드롬의 중심을 포함하는 경우

 

대칭 prefix와 suffix가 팰린드롬의 중심을 가장자리에서 포함할 때 길이가 같고

대칭 prefix와 suffix가 팰린드롬의 중심보다 k만큼 클 경우 팰린드롬을 포함한 것보다 2k만큼 더 크다.

따라서 이 경우 팰린드롬을 포함한 해는 최대 대칭인 prefix와 suffix의 해보다 길이가 작다.

 

 

 

 

마지막으로 2번에서 말한 S'의 맨 앞 / 맨 뒤에서 최장 팰린드롬을 구하는 방법은 4가지가 있다.

 

1. 2차원 동적계획법

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

10942번: 팰린드롬?

위 문제처럼 i부터 j까지 팰린드롬인지 2차원 dp테이블을 채우면 된다.

N^2이므로 hard version에서는 TLE다.

 

2. KMP

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

 

문자열 X와 X를 reverse한 문자열을 X'라고 하자. 팰린드롬을 reverse해도 팰린드롬이기 때문에

 

1. X의 preffix와 X'의 suffix가 일치하면 X의 preffix는 팰린드롬이다.

2. X의 suffix와 X'의 preffix가 일치하면 X의 suffix는 팰린드롬이다.

 

이 때 위 1번, 2번을 완전 탐색을 하면 O(N^2)이므로 KMP를 써서 O(N)으로 시간을 줄이자.

3. 마나커 알고리즘 (Manacher's Algorithm)

https://www.crocus.co.kr/1075

Manacher 알고리즘(Manacher's Algorithm)

이런 알고리즘이 있는데 O(N)안에 모든 부분 문자열이 팰린드롬인지 알 수 있다.

 

4. 해싱

많은 사람들이 해싱을 써서 푼다고 하고

코드포스 문제 태그에도 해싱이 달렸는데

나는 모르겠다.

 

 

 

못 푼 문제 : E F G

E, F부터는 푼 사람 거의 없고 G는 아무도 못 풀었다.

 

 

 

 

 

 

370등부터 2000등까지 5솔브 빨리풀기였고 내가 거의 막바지다. 푸는 속도를 늘려야..