Educational Codeforces Round 148 (Rated for Div. 2)

https://codeforces.com/contest/1832

 

A. New Palindrome

 

s[0] ~ s[n / 2]가 모두 동일한 경우에만 YES이다.

만일 아니라면, 저 안에서 순서를 바꾸면 새로운 palindrome이 된다.

 

B. Maximum sum

 

이게 그리디가 될 거라 생각했는데, 안돼서 뇌정지가 왔었다.

아무튼 정렬을 해둔다면 prefix sum으로 모든 경우의 수를 다해볼 수 있다.

즉, 첫 operation을 i번, 두 번째를 k - i번 한다고 가정한다면, psum[n - (k - i)] - psum[i * 2] 정도를 모두 계산해보면 된다.

 

C. Contrast Value

 

만일 |a[i] - a[i + 1]| + ... + |a[j - 1] - a[j]| = |a[i] - a[j]|이려면, a[i]부터 a[j]까지 단조증가거나 단조감소여야 한다.

따라서 기울기가 바뀌는 순간만 잘 따져주면 된다.

이거도 모두 같은 경우에는 답이 1이 되므로 조심해야 한다.

 

D. Red-Blue Operations

 

우선, 당연하게도 맨 마지막에 전부 red를 blue로 바꿔가면서 숫자들을 키우는게 이득임을 알 수 있다.

그 전에는 반드시 -(뭐시기)가 생겨나게 되는데, i번째와 (i + 1)번째를 같은 곳에 하여 -1을 주는게 이득이다.

따라서 단순하게 k, k - 1, ... k - n + 1까지는 전부 숫자를 더하고, 남은 (k - n) / 2는 잘 -1을 분배해주면 된다.

다만, k와 n의 기우성이 서로 다를 경우에는 k - n + 1을 사용하지 못함에 주의하고, -1이 (k - n) / 2 + 1개가 된다.

 

당연히 숫자를 더하는 것은 a를 정렬 했을 때 제일 작은 수부터 제일 큰 수를 더해주는 것이 이득이다.

-> 숫자를 빼주는 것은 이제 제일 큰 애부터 빼주면 된다.

-> 하지만 이렇게 빼는 것은 너무 느리다.

-> 더했을 때 최소 원소를 mini라고 하였을 때 (모든 원소의 합) - (mini * n)번의 -1은 전혀 영향을 끼치지 않는다

-> 따라서 (k - n + 1) / 2 - {(모든 원소의 합) - (mini * n)} = m이라고 하자. (남은 -1의 횟수를 의미)

-> 그러면 모든 원소들이 지금 mini로 맞춰졌으므로, 순서대로 돌아가면서 -1을 빼주면 된다.

-> 따라서 mini - (m - 1) / n - 1이 답이 된다.

 

가만히 보고 있으면 대충 항상 a[i]에는 k - i와 비슷한 숫자가 더해짐을 알 수 있다.

그래서 적당히 a[i] - i를 이용하여 미리 계산을 해두면, 모든 k에 대해 적용시킬 수 있음을 알 수 있다.

따라서 k < n인 경우, k와 n의 기우성이 다른 경우, k와 n의 기우성이 같은 경우 각각에 대해 필요한 계산을 해두면 된다.

 

어떻게 operation을 하는지 정확히 이해했다면, editorial의 풀이가 더 짧은 것 같으니 그것을 참고하자.

 

E. Combinatorics problem

 

대충 숫자들을 써보면 파스칼의 삼각형에서 보던 숫자들임을 알 수 있다.

즉, b1, b2 같은 것들이 누적합이라는 것이다.

그냥 a값 : a1, a2, a3, a4, ....

k = 0 : a1, a1 + a2, a1 + a2 + a3, ...

k = 1 : a1, (2a1 + a2), ...

-> 따라서 단순히 누적합을 k + 1번 계산해주면 답을 얻을 수 있다.

 

F. Zombies

 

솔직히 전혀 감도 안 잡혀서 virtual이 끝나는 즉시 풀이를 열어봤다.

풀이가 웬일로 친절하게 적혀있었다.

 

핵심관찰 1) 각 generator의 작동시간이 [Li, Ri)로 정해져 있다고 가정하자

-> 만일 새로운 entrance [lj, rj)가 있다면, abs(Li + Ri - lj - rj)값이 최소인 generator i를 고르는 것이 이득이다.

-> 따라서 각 entrance들은 lj + rj에 대해 정렬된 순서대로 generator들에 대응되고, 묶인다

 

-> 그러면 적당히 흔한 그룹으로 묶는 dp들처럼 O(N^3) 정도로 dp[i][j] = (i번까지 j개 그룹의 최댓값)을 계산가능하다

핵심관찰 2) 그럼 적당히 흔한 dp최적화인 DnC optimization이 가능하다

-> 엄밀히까지 가지 않더라도, 대충 단조성이 보이기 때문이다.

 

핵심관찰 3) 이제 그러면 cost(i, j)를 계산하는 일만 남았다.

-> 이때 opt(i, j - 1)과 opt(i + 1, j) 사이에 opt(i, j)가 있다는 점을 이용하여 knuth와 유사하게 optimizaiton이 된다.

 

물론 핵심관찰 1을 보지 못한게 크다지만, DP optimization을 꽤 많이 봐왔는데 감도 못 잡았다는게 슬프다