Codeforces Round 919 (Div. 2)

https://codeforces.com/contest/1920

 

버추얼 한 번 돌아봤다.

 

A. Satisfying Constraints

 

간단하게 a = 1, a = 2 정보로 상한과 하한을 구해두고, a = 3의 정보를 모두 제외하면 된다.

 

B. Summation Game

 

어차피 a가 모두 양수이기에 Bob은 항상 제일 큰 X개를 -1로 곱해버릴 것이다.

따라서 Alice가 작은 숫자를 지워버린다면 그냥 합만 작아지는 꼴이므로, 항상 큰 숫자만 지울 것이다.

즉, 제일 큰 i(<= k)개를 지우는 것을 모두 해보면 된다.

a를 정렬해두고 prefix_sum을 사용하면 모두 확인해볼 수 있다.

 

C. Partitioning the Array

 

partition에 쓰이는 K는 모두 N의 약수이다. 

그러면 각각의 K에 대해 모든 i에 대해서 a[i + n / k] - a[i]의 gcd 값을 구해보면 된다.

이 중 1이 아닌 개수를 모두 세면 끝.

약수의 개수는 O(N^(1/3)) 정도라고 알려져 있으니 대충 O(N^(4/3) * gcd)

 

D. Array Repetition

 

b = 2인 operation들은 아무리 많아도 60개를 넘을 수 없다.

최소한 x = 1이기 때문에 60번만 써도 2^60 > 1e18이 되어버리기에 의미가 없는 숫자이다.

따라서 전체 크기가 1e18 이하인 동안만 입력을 받으면, b = 2인 operation은 60개 이하이다.

 

b = 2인 operation이 들어올 때마다 array를 나누자.

예를 들어 예제 1의 입력은 

-> { {1, 2} * 2, {3} } * 4 와 같이 표현하고, {1, 2}와 {3}의 두 층으로 나눌 수 있다.

그러면 층을 점차 내려가면서 답을 구하면 된다.

이전 층의 크기를 sz[i - 1], 이전 층의 반복 횟수를 rep[i - 1]이라고 한다면

1) K < sz[i - 1] * rep[i - 1] : 반복되는 이전층에 존재하니 K %= sz[i - 1]

2) K >= sz[i - 1] * rep[i - 1] : 현재 층에 답이 존재하니 ans = a[i][K - sz[i - 1] * rep[i - 1]]

 

층은 아까 말한대로 60개 이하이니 O(60 * q)면 충분하다.

 

E. Counting Binary Strings

 

1들이 여러 개 있다면 그 직전의 0의 개수를 a[i]라고 하자.

예를 들어 s = 1010이라면, a[0] = 0, a[1] = 1, a[2] = 1이라고 할 수 있다.

그렇다면 이때 만들 수 있는 good substring의 개수는 (a[0] + 1) * (a[1] + 1) + (a[1] + 1) * (a[2] + 1) + ...이다.

이때 길이가 k보다 큰 good substring은 없어야 하므로 a[0] + a[1] + 1 <= k가 성립하여야 한다.

 

그러면 dp[i][j] = (현재까지의 good substring의 개수는 i, 마지막 a값은 j)라고 정의하자.

그러면 단순하게 dp[i + j * (p + 1)][p] += dp[i][j] (단, j + p + 1 <= k)로 dp를 이어나갈 수 있다.

조화수열의 합공식에 의해 복잡도는 O(NKlog)

 

F1. Smooth Sailing (Easy version)

 

상상속의 island를 현재 주어진 지도를 둘러싸서 만들자.

즉, (0, 0) ~ (n + 1, 0), ~ (n + 1, m + 1) ~ (0, m + 1) ~ (0, 0)의 island를 주위에 만들자는 뜻이다.

그렇다면, 우리의 목표는 이 밖의 땅과 안의 땅이 서로 이어지지 않도록 하는 것이다.

 

어떤 쿼리 (X, Y)가 들어왔다고 가정하자.

그렇다면 이 (X, Y)에서부터 (가능한 volcano로부터의 거리의 최솟값)에 따라 연결되는 땅이 나뉜다.

즉 chk[i] = ((X, Y)로부터 volcano로부터의 거리가 i 이상인 땅만 방문했을 때 방문 가능한 땅)이라 할 수 있다.

편의상 chk[i]의 땅들은 (i + 1) 이상인 땅만 방문하였을 때에는 방문할 수 없다고 하자.

또한 편의상 island가 있는 땅은 거리가 0인 땅으로 간주하자.

 

그러면 chk[0]부터 시작해서 8방향에 있는 땅들을 모두 merge해주자.

chk[i]까지의 땅들을 모두 주변의 땅과 merge하였을 때 밖 땅과 안 땅이 연결되면 i가 답이 된다.

왜냐하면 최소 거리가 i인 땅들까지는 모두 제거를 해주어야 밖과 안이 서로 접촉 불가능하다는 뜻이기 때문이다.

각 쿼리당 모든 땅조각을 처리해보아햐 해서 O(NMQ). 

 

F2. Smooth Sailing (Hard version)

 

위의 방식은 결국 모든 쿼리에 대해서 안 땅과 밖 땅이 연결되는지 확인하므로 독립적으로 시행할 수 없다.

Editorial을 참고하면 독립적으로 확인할 수 있는 방식이 있다.

Editorial의 방법은 방법은 안 땅으로부터 밖 땅으로 연결된 선을 그었을 때, 그 선을 지나는 횟수의 기우성을 세는 것.

즉 쿼리에서의 (X, Y, 0)에서부터 시작하여 어찌저찌 (X, Y, 1)로 연결시킬 때 volcano 거리의 최솟값을 구하면 된다.

따라서 이는 PBS를 이용하면 된다.