Codeforces Global Round 24

https://codeforces.com/contest/1764

 

PS를 아마도 접기 전에 레드를 박제해놓고 싶어서 (이전에 레드를 찍었지만... 언레당함) 열심히 해야한다.

F에 시간을 쏟다가 포기하고 G1의 풀이를 알아냈지만 구현에 문제가 있는지 wa를 받아서 5솔

그나마 E를 좀 빨리 풀어서 퍼포는 좋게 나와주었다.

 

A. Doremy's Paint

핵심관찰은 그냥 전체구간을 선택하는 것이 제일 이득이라는 것이다.

c(L, R)은 L이 작아지거나 커진다면 1이 커질수도 있고 안 그럴수도 있지만 R - L은 항상 증가하기 때문이다.

 

처음에 문제를 잘못이해하여 '같은 숫자인 구간'이 답이 될거라 생각하여 시간소모가 조금 있었다.

그 다음에 살짝 패닉해서 [x, n]이 제일 최대라고 생각했고, [x, n]들에 [1, n]이 포함되어 있어서 다행이다.

 

B. Doremy's Perfect Math Class

유클리드 호제법이 어떻게 이루어지는지 생각한다면, 모든 원소의 GCD를 만들 수 있음을 알 수 있다.

그러면 이 GCD값을 이용하면 (배열의 최댓값)보다 작거나 같으면서 GCD의 배수인 숫자는 모두 만들 수 있다.

 

C. Doremy's City Construction

두 개의 그룹 (큰 그룹)과 (작은 그룹)으로 나누어주는 것이 최대이다.

하지만 이게 아닌 경우가 단 하나 존재하는데 그것이 바로 모든 숫자가 같은 경우이다.

이러면 n / 2개로 이어주면 된다.

 

D. Doremy's Pegging Game

이것이 말 그대로의 조합문제였다.

마지막에 처음으로 원의 중심에 닿는 순간에 남은 점의 수를 x라 했을 때 경우의 수를 전부 세주었다.

O(n^2)으로 했는데 잘 고민해보면 더 빠르게 하는 것이 가능할 수도 있고....

 

E. Doremy's Number Line

일단 차례대로 따져나가보자.

1) k <= a[1] 이면 바로 1으로 색칠하고 YES

편의를 위해서 나머지 숫자(색깔)들을 2, 3, 4...이라고 부르자.

2) k - b[1] <= a[1] && k - b[1] <= max(a[2], a[3], a[4], ...)이라면 YES

3) k - b[1] <= a[1] && k - b[2] - b[1] <= a[2] && k - b[2] - b[1] < = max(a[3], a[4], ...)이면 YES

...

이를 반복해서 언젠가 조건을 만족하면 된다..

claim) 맨처음을 제외하면 그냥 {a[i] + b[i], -a[i]} 가 최대인 색을 다음 색으로 고르면 된다.

max(a)값은 최대한 유지해가며 a[i] + b[i] + b[i - 1] + ... + b[1] 값이 제일 커지기 때문이다.

따라서 {a[i] + b[i], -a[i]} 가 최대인 색을 다음 색으로 골라가면서 가능하면 가능하다고 하고 끝내고, 끝까지 안되면 NO.

 

F. Doremy's Experimental Tree

하나만 관찰하면 끝난다.

X-Y 간선이 일단 존재한다면 F(X, Y)값은 X-Y가 포함된 다른 cycle의 F(x, y)값보다 더 크다

따라서 F이 큰 값부터 mst를 만들듯이 dsu하며 트리를 만들어주면 된다.

 

G. Doremy's Perfect DS Class

 

K = 2인 쿼리를 이용한다면, 2/2 = 3/2, 4/2 = 5/2 ... 이므로 N이 홀수라면 모두 페어링된다.그러면 1만 혼자 남기 때문에 [1, X, 2], [X + 1, N, 2]에서 1의 위치를 알아낼 수 있고 이분탐색하면 20번이다.G1의 경우 30번의 쿼리가 허용되기에 [1, X, N]으로 N의 위치를 10번만에 찾으면 된다.

 

G3는 20번만의 쿼리를 써야하는데 현실적으로 앞쪽의 20번을 줄이기는 쉽지 않아보이고 N을 찾는 10번을 줄여야 한다.-> N이 짝수더라도 [1, X, 2], [X + 1, N, 2]를 하고 나면 1과 N이 서로 구분은 안가지만 각 구간에 몇개 존재하는지는 안다.-> 따라서 만일 둘 다 같은 구간에 있으면 그냥 그 구간으로 이동하고, 따로 존재하면 [1, X, N]으로 확인해주면 된다.-> 따라서 이는 홀수에서 필요한 20번의 쿼리에 딱 한번만 더 있으면 된다.

 

여전히 쿼리를 단 한번 더 줄여야한다.-> 이는 마지막에 1이 있는 구간이 [L, L + 1]일 때에는 실제로 한 번의 쿼리만 더 필요하다는 점으로 줄일 수 있다고 한다.