Codeforces Round 877 (Div. 2)

A. Blackboard list

 

만일 음수가 있다면 당연히 operation으로는 나올 수 없으니 처음부터 존재한다.

만일 양수만 있다면 최댓값이 처음부터 존재하는 숫자이다.

 

B. Minimize Permuation Subarrays

 

1과 2 사이에 n이 들어가 있으면 무조건 {1}, {1, 2, ...}만 가능하다.

모든 경우에 대해 1과 2 사이에 n을 박아주는 코드를 짜면 된다.

 

C. No Prime Differenes

 

만일 n, m 중 하나라도 소수가 아니라면 그냥 그 방향으로 1, 2, 3..를 배열하면 되므로 쉽다.

 

이제 n, m이 소수더라도 먹히는 방식을 떠올리자.

다음과 같은 방법이 있다

for(int i = 0; i < n; i++) for(int j = i; j < m + i; j++) cout << j % m + i * m

이렇게 하면 양옆으로의 차이는 무조건 1이나 m - 1이고, m은 4보다 큰 소수이므로 m - 1은 무조건 짝수이다.

위아래로의 차이 또한 m + 1이나 1이기 때문에 가능하다.

 

또다른 방법으로는 그냥 순서대로 박는데, 한 줄씩 건너뛰면서 박는 방식이다. (editorial)

이외에도 아주 많은 방법이 있을 것이다.

 

D. Bracket Walk

 

다음과 같은 관찰을 할 수 있다

-> bracket의 prefix sum이 -1인 부분이 2인 부분보다 먼저 나오면 불가능하다.

-> 뒤에서 부터 보았을 때 prefix sum이 -1인 부분이 2인 부분보다 먼저 나오면 불가능하다

pf)

1) -1도, 2도 안나오면 ()()()...이므로 무조건 가능

2) -1이 앞에서 먼저 나오면 당연히 이 부분을 통과하는 방법이 없으니 불가능

3) -1이 뒤에서 먼저나오면 마찬가지로 이 부분을 통과하는 방법이 없으니 불가능

4) 앞뒤 모두 2가 먼저나오면, 그 구간에서 '(', ')'를 무한으로 추가할 수 있으니 무조건 가능

 

일단 나는 segtree를 이용해서 저 지점들을 찾아냈다.

하지만 이건 너무 비효율적이고 다음과 같은 set을 생각할 수 있다.

-> s = { i | i가 홀수인데 s[i] = '(' OR i가 짝수인데 s[i] = ')' }

-> 만일 s가 비어있으면 위의 1)과 같은 상황이 되므로 가능

-> 만일 s의 제일 작은 원소가 짝수면, 그 지점에서 psum = -1가 되므로 불가능

-> 마찬가지로 s의 제일 큰 원소가 홀수면, 그 지점에서 뒤에서부터 psum = -1이므로 불가능

 

E. Count Supersequences

 

sol1)

수열 b는 다음과 같은 배열 pos를 유일하게 가진다.

-> pos[i] = (a[i - 1]값 다음에 a[i]값이 처음으로 나타나는 위치)

그렇다면 정해진 pos에 대해서 각각의 b의 개수를 생각해보자.

 

그러면 pos[i - 1] ~ pos[i] 사이에는 절대로 a[i]이 나오면 안되니 k - 1 종의 숫자가 올 수 있다.

또한 pos[n] 이후의 뒤에는 어떤 값들이 와도 되므로 k종류의 숫자가 올 수 있다.

-> 따라서 pos[n] = x라면 b의 개수는 C(m - 1, x - 1) * (k - 1)^(x - n) * k ^ (m - x) 가 된다.

다만 x값은 n부터 m까지 가능하기에 이 풀이는 O(m)이라서 naive하게 굴릴 수가 없다.

다음과 같은 식을 이용하여 생성함수로 어쩌구 저쩌구 잘 계산하면 답이 나올 것이다.

 

sol2)

위의 풀이를 보면 알겠지만 a값이 전혀 상관없다.

따라서 a[i] = 1이라고 그냥 여겨도 아무 상관이 없다.

따라서 문제를 m 길이에서 n개 이상의 1이 있는 수열의 개수를 구하는 것과 다를 것이 없다.

당연히 여집합을 구하는게 쉽고, k^m - sum( (k - 1)^(m - x) * C(m, x) )가 된다.

C(m, x) = C(m, x - 1) * (m - x + 1) / x 라는 점을 이용하여 빠르게 combination를 구할 수 있다.

modinv를 빠르게 하는 방법이 있는진 모르겠지만 그냥 MOD - 2승으로 계산하면 O(NlgMOD)