[Codeforces] Round 856 Div.2 후기

대회링크 : https://codeforces.com/contest/1794

 

A. Prefix and Suffix Array

문제 : 접두사와 접미사 목록을 주었을 때 원래 문자열이 팰린드롬인지 판단

 

원래 문자열의 길이가 n 일때

길이가 1인 경우에는 접두사와 접미사가 같은지 판단

길이가 2이상인 경우에는 길이가1인 문자열 2개와 길이가 n-1인 문자열 2개 저장하고

두 문자열을 조합했을 때 서로 같은 경우 해당 문자열이 기존 문자열 이므로

그 문자열이 팰린드롬인지 판단

 

 

B. Not Dividing

문제 : 주어진 배열을 조작하여 해당원소가 이전의 원소로 나누었을 때 정수로 떨어지지 않게 만들기

1번의 조작으로 특정 원소의 값을 1 증가 시킬 수 있으며 최대 2n번 까지 가능하다

 

주어진 원소에 모두 1을 더하고

다시 두 번째 원소 부터 보며 그 이전원소로 나누어 질 경우 1을 더해줌으로서 해결

 

 

C. Scoring Subsequences

문제 : 주어진 배열에서 각 원소마다 최대 점수를 만드는데 필요한 최대 비용 출력

 

에디토리얼은 O(nlogn)의 풀이가 있지만 O(n)으로 푸는 방법이 존재한다.

이 문제에서 블럭을 하나 씩 놓았을때 최대로 만들 수 있는 정사각형 크기와 같다

또한 각 원소는 모두 오름차순 이므로 그 이전에 만든 값보다 항상 비용이 크다

따라서 해당 원소에서 더 큰 정사각형을 만들 수 있는 경우에는 정사각형의 크기를 1 크게 하고

그렇지 않다면 그냥 넘어가면서 비용을 출력 하면 된다.

 

 

D. Counting Factorizations

문제 : 주어진 배열을 조합하여 식에 맞는 수를 만들고 중복되지 않은 수 의 개수를 출력

 

이 문제는 궁금해서 에디토리얼을 찾아보았다.

 

기본적으로 2n 까지의 팩토리얼과 역팩토리얼을 미리 계산 해 둔다.

역팩토리얼(inverse)의 경우 pow(n,p-2) % p 로 구해준다.

 

이제 주어진 원소를 소수가 아닌 것과 소수 인 것으로 분리 하고

소수인 경우에는 해당 소수를 사용할 경우와 사용하지 않는 경우로 나누고 해당 값을 더 한다.

이때 dp를 이용해 계산 된 값을 메모이제이션 해주는게 핵심이었다.

 

계산할 때 n개중 p가 a개, q가 b개 r이 c개 일경우 n!/(a!b!c!) 이 되며

이것을 역팩토리얼 계산한것을 이용해 n! * inverse(a) * inverse(b) * inverse(c) 로 치환

치환하여 나머지 계산해도 같은 값을 얻을 수 있다.

 

 

E.  아직 실력 부족으로 접근하지 못 하였다.