Codeforces Round 942 (Div. 1)

https://codeforces.com/contest/1967

 

훨씬 잘할 수 있었던 라운드.

까고보면 솔직히 그렇게 어려운 라운드도 아니다.

 

A. Permutation Counting

 

일단 당연히 제일 많은 카드부터 놓는게 이득이다. (1이 제일 많을 때 1, 2, 3, 1...로 두는게 이득)

따라서 우선 카드들을 모두 정렬시켜놓고, 모든 카드의 개수가 최소 P개가 되게 했다고 하자.

그리고 k개의 코인 중 남는 걸 이용하면 i - 1까지의 숫자는 P + 1개 이상, 그 이후는 P개 이상이 되는 최대의 i가 존재한다.

그러면 답은 n * P + i - (n - 1)이 된다.

한 번씩 나열해서 총 길이 n * P + i의 수열을 만들 수 있고, 여기서 아무 n개의 연속한 subarray를 잡으면 되기 때문이다.

적당한 P값은 이분탐색으로 찾으면 된다.

N = 2e5, A = 1e12이니 long long이 터지지 않게 조심하자.

 

B1. Reverse Card (Easy Version)

 

gcd(a, b) = g라고 하자. (a = ga1, b = gb1)

그렇다면 g * (a1 + b1)는 g^2 * b1의 배수가 되어야 한다.

이때 b1은 (a1 + b1)과 서로소이므로 b1 = 1이 성립한다.

이를 대입하면 g * (a1 + 1) = g^2 * k 이므로 a1 = gk - 1

a = g^2 * k - g, b = g이므로 a = b^2 * k - b이면 된다.

모든 b값에 대해서 가능한 a값의 개수를 세주면 된다.

b^2 + b <= n이 성립해주어야 하므로 각 테스트 케이스당 O(sqrt(n))이면 충분하다.

 

B2. Reverse Card (Hard Version)

 

g^2 * b1이 g * (a1 + b1)의 배수여야 한다.

이러면 또 gcd(b1, a1 + b1) =1이므로 g ^ 2 * b1 = g * (a1 + b1) * b1 * k가 성립한다.

따라서 g = (a1 + b1) * k가 성립.

a = (a1 + b1) * k * a1, b = (a1 + b1) * k * b1이다.

따라서 a + b = x^2 * k가 성립하면서 동시에 a, b가 모두 x의 배수가 되는 쌍의 개수를 세면 된다.

 

모든 x에 대해서 그냥 진행해보면 된다.

단, 만일 x ^ 2 * k가 다른 방식으로, 즉  y ^ 2 * k'으로 표현가능하다면 겹치게 된다.

따라서 k가 제곱수의 배수가 아닌지 확인하여 그럴 경우에만 세주면 된다.

뭐 mu함수 같은걸 쓸 수도 있지만, 그냥 모든 제곱수에 대해서 배수를 미리 확인해두면 충분하다.

기본적으로 x ^ 2 * k <= n + m이기 때문에 모든 (x, k) 쌍이 많지 않아 시간 내에 충분히 돌아간다.

대충 복잡도를 때리면 O(sqrt(n + m) lg(n + m))으로 될 것이다.

 

C. Fenwick Tree

 

i = 2p + 1일 경우 : 그냥 무조건 k가 몇이든 간에 b[i]가 유지된다는 것을 알 수 있다.

i = 4p + 2일 경우 : 이러면 b[i] - b[i - 1] * k가 답이 됨을 알 수 있다.

i = 8p + 4일 경우 : b[i] - b[i - 1] * k - b[i - 2] * k + k * (k - 1) / 2 * b[i - 3]이 답이 됨을 알 수 있다.

...

 

이제 조금 반대로 b[1]이 어떤 원소들에 어떻게 영향을 주는지 살펴보자.

b[1] : b[1]은 그냥 쭉 b[1]으로 유지된다.

b[2] : b[2]에서는 - b[1] * k가 이루어진다.

b[4] : b[4]에서는 b[2]가 계속해서 빠지기 때문에 + k * (k - 1) / 2 * b[1]이 이루어진다.

b[8] : b[8]에서는 b[4]가 계속해서 빠지기 때문에 - k * (k - 1) * (k - 2) / 6 * b[1]이 이루어진다.

b[16] : b[16]에서는 b[8]가 계속해서 빠지기 때문에 + k * (k - 1) * (k - 2) * (k - 3) / 24 * b[1]이 이루어진다

...

 

이제 규칙이 잘 보인다.

따라서 각 숫자에 대해서 이 숫자가 어떤 원소들에 영향을 주는지 확인하여 더해주거나 빼주면 된다. 

 

D. Long Way to be Non-decreasing

 

비록 N, M = 1e6이지만 무조건 이분탐색일거라 접근했었다.

그러니 mid일 때 가능한지 불가능한지를 확인하여 답을 구할 수 있다고 생각했다.

mid일 때 가능한지 확인하는 방법은 간단하다.

a[1] -> a[1]에서부터 mid번 이하로 변환하여 제일 최소의 숫자로. 이 값을 aa[1]이라 하자.

a[2] -> a[2]에서부터 mid번 이하로 변환하여 aa[1] 이상의 제일 최소 숫자로. 이 값을 aa[2]라 하자.

a[3] -> a[3]에서부터 mid번 이하로 변환하여 aa[2] 이상의 제일 최소 숫자로

...

즉, 매번 a[i]에서부터 mid번 이하로 변환하여 aa[i - 1] 이상의 최소 숫자를 구하면 된다고 생각했다.

 

하지만 알고보니 aa[i - 1] 이상의 최소 숫자로 바꿀 필요가 없고 그냥 aa[i - 1]로 도달 가능한지 확인하면 된다.

만일 불가능하면 aa[i - 1] + 1을 확인하고, aa[i - 1] + 2를 확인하고, ...

그렇게 해서 aa[i - 1] + k가 도달 가능한 최초의 숫자면 aa[i] = aa[i - 1] + k가 되는 것이다.

그래프의 모양을 고려하면 어떤 x에서 y까지의 거리 정도는 O(1)에 구할 수 있다.

따라서 O(NlgM)으로 할 수 있다. 

시간이 2000ms 정도 나오는데 정상인 것 같다.