Codeforces Round 955 (Div. 2, with prizes from NEAR!)

https://codeforces.com/contest/1982

 

전체적으로 난이도가 평소보단 조금 쉬워보인다.

버추얼 다 끝내고 이걸 작성하면서 E에 추가제출을 했더니 패널티가 안좋아졌다. 흠...;;

 

A. Soccer

 

(x1 > y1) == (x2 > y2)를 확인해주면 된다.

 

B. Collatz Conjecture

 

일단 K가 만약에 엄청나게 크다면, 결국 x는 (1, 2, ... y - 1)을 반복하는 지경에 이를 것이다.

만일 저 상태에 이른다면, 그냥 K %= (y - 1)처리를 해주어도 문제가 안 될 것이다.

 

divide by y가 되는 순간은 cnt = (y - x % y)번 operation을 실행한 다음이다.

0) x = 1이라면 우선 위에서 설명한 것처럼 K %= (y - 1) 처리를 해준다.

1) K >= cnt라면 x = (x + cnt) / y, K -= cnt를 해주면 됨

2) K < cnt라면, 덧셈만 K번 이루어지므로 x += K를 하고 모든 operation을 끝낸다.

이때 1)을 할 때마다 x가 빠르게 작아지기 때문에 1)의 계산은 몇 번 이루어지지 않으니 시간 내에 통과.

 

C. Boring Day

 

쉽게 떠올릴 수 있는 dp가 있다.

dp[x] = (x장 사용하였을 때 Egor가 최대로 얻을 수 있는 점수)

dp[x] = MAX(dp[y] + (L <= a[y] + a[y + 1] + ... + a[x - 1] <= R))

이때 (L <= a[y] + a[y + 1] + ... + a[x - 1] <= R)가 성립하는 y의 범위는 투 포인터로 관리할 수 있다.

그리고 어떤 범위 [l, r]에 대해서 dp[i]의 값의 최댓값은 그냥 dp[r]이다.

-> dp[x] = max(dp[r - 1] + 1, dp[x - 1])로 구할 수 있다.

 

D. Beauty of the mountains

 

어떤 K * K에 C개씩 추가했을 때 w/ cap과 w/o cap의 총 height 차이 변화를 보면

-> (총 with의 height) - (총 without의 height) += C * ((K * K내 with 개수) - (K * K네 without 개수)를 하는 것과 같다.

베조의 등식으로 정해진 a, b에 대해서 ax + by는 gcd(a, b)의 배수를 모두 표현할 수 있음이 알려져 있다.

또한 prefix_sum을 이용하여 모든 K * K 내의 (With caps) - (Without caps)를 구할 수 있다.

따라서 우리가 차이를 gcd((w/ caps) - (w/o caps))의 배수만큼 변화시킬 수 있다.

그러니 (처음 w/, w/o의 차이)가 gcd로 나누어지는지 확인하면 된다.

 

E. Number of k-good subarrays

 

근본적으로 [0, N)이라는 범위는 [0, 2^x), [2^x, N)으로 나눌 수 있다. (단, x는 2^x < N인 최대 x)

그러면 뒤쪽 [2^x, N)이라는 범위에서는 x번째 비트를 제거하고 n' = N - 2^x, k' = k - 1을 푸는 것과 동일해진다.

-> 즉, solve(N, K)를 solve(2^x, K) + solve(N - 2^x, K - 1) + (두 구간 사이의 subarray 수)로 볼 수 있다.

solve(N, K) = solve(2^x, K) + solve(N - 2^x, K - 1) + ([2^x, 2^x + 2^(K - 1))의 subarray의 수) - solve(2^(K - 1), K - 1)

-> 마지막에 빼준 것은 두 번 이상 센 subarray의 수와 동일 (이들은 [2^x, N)에도 동시에 포함된다)

-> 2^x - 1은 워낙 켜진 비트가 많기 때문에 [0, 2^x)에서는 겹치는 subarray가 생기지 않는다.

따라서 위의 solve(N, K)를 재귀로 구해주면 된다.

 

하지만 이를 그냥 단순하게 진행하면 결국 [0, 1), [1, 2), ...에 대해 모두 해보는 꼴이 되어 복잡도가 O(N)이 되어버린다.

이때 solve(2^x, K)와 사실 y - 2^x도 대략 2^(K - 1)임을 확인할 수 있다.

즉, 실제로는 solve(p, q)에 들어가는 (p, q)쌍이 별로 많지 않다는 뜻이다.

따라서 map 등으로 한 번 계산한 solve(p, q)를 다시 안 계산하는 장치를 넣어주면 통과된다.

 

사실 조금 더 고민을 해보면, 매우 이쁘게 코드를 만들 수 있다.

여전히 계산 횟수가 의심된다면, 아주 멋진 이 풀이를 확인하도록...

 

F. Sorting Problem Again

 

우선 다음과 같은 set을 관리하자

-> s = {x0 = 0, x1, x2, ... xk = n}, 이때 [x[i], x[i + 1])은 정렬되어 있는 상태이다.

이 set의 관리는 매우 간단하다

-> a[pos] = val로 바꾼다면, 일단 set에 pos와 pos + 1을 넣어본다.

-> a[pos - 1] <= a[pos]라면 pos를 삭제하고, a[pos] <= a[pos + 1]이라면 pos + 1을 삭제한다.

 

s를 이용하여 다음과 같은 L, R을 구할 수 있다.

-> L은 [0, L)이 정렬된 제일 작은 L, R은 [R, n)이 정렬된 제일 큰 R

세그트리와 L, R 값을 이용하여 다음과 같은 mini와 maxi를 구할 수 있다.

-> mini = [L, R]에서 제일 작은 숫자, maxi = [L, R]에서 제일 큰 숫자.

 

만일 [0, L) 사이에 있는 모든 수들이 mini 이하라면 답이 되는 l = L이 될 것이다

-> 만일 아니라면 upper_bound(a.begin(), a.begin() + L, mini)로 mini를 넘는 제일 작은 index를 구할 수 있다.

    이 경우 l = index가 될 것이다

비슷한 방식으로 만일 [R, n) 사이에 있는 모든 수들이 maxi 이상이면, r = R - 1이 될 것이다.

-> 만일 아니라면 lower_bound(a.begin() + R, a.end, maxi) - 1로 maxi 미만의 제일 큰 index를 구할 수 있다.

    이 경우 r = index가 될 것이다.