Educational Codeforces Round 148 (Rated for Div. 2)

A. New PalindromePermalink

A. New Palindrome

$s$가 팰린드롬이므로 $\lvert s \rvert / 2$ 개의 문자만 봤을 때, 모두 같다면 바꿀 수 없고, 그렇지 않다면 적절히 swap해서 다른 팰린드롬을 만들 수 있다.

$s$가 팰린드롬이란 제한을 못봐서 오래걸렸다.

B. Maximum SumPermalink

B. Maximum Sum

수를 정렬하고 앞에서 두 개씩, 뒤에서 한개씩 미는 방식으로 투 포인터를 관리하면 쉽게 풀 수 있다.

C. Contrast ValuePermalink

C. Contrast Value

단조적으로 비감소하거나 비증가하는 부분들을 양 옆 두 개만 남기고 중간에 있는 것들을 모두 삭제한다.

나머지 것들을 지울 순 없다. 그럼 $\lvert a_i - a_{i+1} \rvert$ 의 합이 무조건 작아지기 때문이다.

D1. Red-Blue Operations (Easy Version)Permalink

parity도 고려해야하고 여러 케이스를 고려해야하고 애초에 그리디적인 아이디어가 어려운 문제이다. 에디토리얼을 참고해서 작성했다.

D1. Red-Blue Operations (Easy Version)

숫자들을 오름차순 정렬한다.

$k \le n$ 일 때는 가장 작은것에 $+k$, 그 다음 작은 것에 $+k-1\cdots$ 처럼 진행해서 수들을 증가시켜주는 것이 최적임을 알 수 있다.

$k > n$ 이라고 하자.

$k ~\%~ 2 = n ~\%~ 2$ 라면 항상 모든 수를 증가시킬 수 있다.

$n$개를 모두 증가시킨 뒤에 $(k-n) ~\%~ 2 = 0$ 여서 어떤걸 잡고 계속 (감소 - 증가 - 감소 - 증가) 를 반복할 수 있어서이다.

$k ~\%~ 2 \ne n ~\%~ 2$ 이면 모두 증가시킬 순 없고, 정확히 한 개만 감소시킬 수 있다.

최대한 수 감소를 적게하고 싶다고 해보자. (증가 - 감소)를 이어서하면 정확히 $1$이 감소하는데, 이 (증가 - 감소) 이어진 연산을 동일한 것에 해야 최소($1$)로 감소한다.

그렇지 않다고 하면 예를 들어, $a_1$에 $1$증가, $4$감소를 하고 $a_2$에 $2$증가, $3$감소를 했다고 하자.
$a_1$을 $1$증가 $2$감소, $a_2$에 $3$증가 $4$ 감소를 하면 $a_2$는 변함없고 $a_1$만 더 증가하기 때문에 그리디가 성립한다.

$\therefore$ (증가 - 감소) 연산은 인접한 수로 동일한 숫자에 해야 최적이다.

이제 연산들을 다음과 같이 두 가지로 생각해보자.

• (증가, 감소) 처럼 인접한 수들로 이루어진 pair 연산들 ($1$번 연산)
• 한 원소에 최대 한 번 적용될 수 있는 일련의 증가 연산들 ($2$번 연산)

$1$번 연산은 수에 무조건 $-1$ 의 영향을 미치므로 $2$번 연산들만 정답에 영향을 미친다.

명백히 우리는 $2$번 연산들에 쓸 값을 증가시킬 수 있는 가장 큰 숫자인 $k$ 부터 시작하게 해야한다.

그리고 $2$번 연산은 $n$번이나 $n-1$ 번이 적용되어야 한다. $k ~\%~ 2 = n ~\%~ 2$ 인 경우에는 $n$ 번이고 그렇지 않다면 $n-1$ 번이다.

결국 정답은 다음과 같이 구해진다.

$k - n \equiv 0 \pmod 2$

$+k$ 를 가장 작은것, $+k-1$ 를 두 번째로 작은것, $\dots$ $+k-n+1$ 을 가장 큰 것

$k - n \equiv 1 \pmod 2$

$+k$를 가장 작은것, $+k-1$ 를 두 번째로 작은것, $\dots$ $k-n+2$ 를 두 번째로 큰 것

이렇게 먼저 적용을 시킨 다음에,

이제 남은 $1$번 연산을 처리해줘야 한다.

$-1$을 감소시켜야 하는 횟수는 $k-n \equiv 0 \pmod 2$ 라면 $(k-n)/2$ 번이고, $k-n \equiv 1 \pmod 2$ 라면 $(k-n+1)/2$ 번이다.

D1 문제에서는 이걸 simulate해서 직접 처리할 수 있다.

배열을 정렬하고 일단 $2$번 연산을 적용하고 $-1$ 를 적용해야 할 횟수를 얻는다.

$a'=\left[ a_1+k,a_2+k-1,\dots \right]$ 라고 하면

$s=\sum_{i=1}^n (a_i'- \text{min}~ a_i')$ 라고할 때 처음 $s$ 번의 $-1$ 연산은 최소를 변화시키지 않는다.

이제 나머지 $\dfrac {k-(n-(n-k) ~\%~ 2)}2 - s$ 번의 연산들은 $n$ 개의 수들에 대해서 고르게 분포시킨다면 minimum이 줄어드는 횟수를 특정할 수 있고, 이는 $\left\lceil \dfrac {\text{max}\left( 0, \dfrac {k-(n-(n-k) ~\%~ 2)}2 - s \right)}n \right\rceil$ 이 감소한다.

이것의 시간복잡도는 아래 코드는 naive하게 구현했으므로 $O(n \log n+qn)$ 이다.

void solve() {  
   int n, q, k;  
   cin >> n >> q;  
   vi a(n);  
   fv(a);  
   sort(all(a));  
   while (q--) {  
      cin >> k;  
      if (k <= n) {  
         vi b = a;  
         for (int i = 0; i < k; i++) b[i] += (k - i);  
         cout << mine(b) << ' ';  
      } else {  
         int parity = (n + k) % 2;  
         vi b = a;  
         // apply operation 2 first  
         for (int i = 0; i < n - parity; i++) {  
            b[i] += (k - i);  
         }  
         // apply operation 1 with greedy  
         ll remain_op = (k - n + parity) / 2;  
         ll s = 0;  
         int mn = mine(b);  
         for (int i = 0; i < n; i++) {  
            s += b[i] - mn;  
         }  
         remain_op -= s;  
  
         int decrease = max(0ll, (remain_op + n - 1) / n);  
         cout << mine(b) - decrease << ' ';  
      }  
   }  
}

D2. Red-Blue Operations (Hard Version)Permalink

D2. Red-Blue Operations (Hard Version)

아이디어는 동일하고, 이제 연산만 최적화해서 Hard version을 풀 수 있다.

$k>n,~~n+k \equiv 0 \pmod 2$ 인 상황만 고려해보자. 나머지도 비슷하다.

$2$번 연산만 먼저 적용해보면, 최소는 $\text{min}_ { i = 0}^{n-1} ~ a_i + k - i = k + \text{min}_{i=0}^{n-1} ~ a_i - i$ 이다.

뒤에 있는 식을 보면 $k$에 상관없이 $i,a_i$ 만 존재하므로 쿼리 전에 전처리를 할 수 있다.

구간 최소값 연산을 왼쪽에서부터 쿼리할 수 있게 만들고 $M_i$ 를 $M_i=\text{min}_{j=0}^i ~ a_j-j$ 라고 하자.

$k \le n$ 인 쿼리가 들어왔을 때 정답은 $\text{min}(k+M_{k-1}, a_k)$ 이다.

왜냐면 $a$는 정렬되어있기 때문에 $2$번 연산이 적용되지 못하는 첫 수인 $a_k$가 적용되지 못하는 범위에서 가장 작은 수이고 연산이 적용되는 범위에서 가장 작은 수는 $k+M_{k-1}$ 이기 때문이다.

$k=n$ 일땐 $a_k$ 가 존재하지 않는다.

이제 $k>n$ 라고 하자.

D1 과 동일하게 $-1$을 해줘야 하는 횟수는 $p=(n+k) ~\%~ 2$ 라고 할 때, $(k-n+p)/2$ 이다.

$p=0$ 이라면 모든 수에 $2$번 연산을 적용시키므로 최소는 $low=M_{n-1}+k$ 이고 $s=kn+\left( \sum_{i=0}^{n-1} ~ a_i-i \right) - n \cdot low$ 이다.

$p=1$ 이라면 가장 큰 수를 제외하고 $2$번 연산을 적용시키므로 최소는 $low = \text{min}\left( M_{n-2}+k,a_{n-1} \right)$ 이고

$s=k(n-1)+\left( \sum_{i=0}^{n-2} a_i-i \right) - n \cdot low$ 이다.

따라서 동일하게 연산해줄 수 있고 $n=1$ 이나 $n=k$ 같은 예외는 따로 처리를 해주는게 헷갈리지 않는다.

void solve() {  
   ll n, q, k;  
   cin >> n >> q;  
   vector<ll> a(n);  
   fv(a);  
   sort(all(a));  
   vector<ll> M(n), S(n);  
   M[0] = a[0] - 0;  
   for (int i = 1; i < n; i++) M[i] = min(M[i - 1], a[i] - i);  
   S[0] = a[0];  
   for (int i = 1; i < n; i++) S[i] = S[i - 1] + a[i] - i;  
   while (q--) {  
      cin >> k;  
  
      if (n == 1) {  
         int ret = a[0] - k / 2;  
         if (k % 2) ret += k;  
         cout << ret << ' ';  
      } else if (k == n) {  
         cout << k + M[n - 1] << ' ';  
      } else if (k < n) {  
         cout << min(k + M[k - 1], a[k]) << ' ';  
      } else {  
         int parity = (n + k) % 2;  
         ll op1 = (k - n + parity) / 2;  
  
         if (parity == 0) {  
            ll minimum = M[n - 1] + k;  
            ll s = S[n - 1] + k * n - minimum * n;  
            op1 -= s;  
            ll dec = max(0ll, (op1 + n - 1) / n);  
            cout << minimum - dec << ' ';  
         } else {  
            ll minimum = min(M[n - 2] + k, a[n - 1]);  
            ll s = S[n - 2] + k * (n - 1) + a[n - 1] - minimum * n;  
            op1 -= s;  
            ll dec = max(0ll, (op1 + n - 1) / n);  
            cout << minimum - dec << ' ';  
         }  
      }  
   }  
}

E. Combinatorics ProblemPermalink

E. Combinatorics Problem

F. ZombiesPermalink

F. Zombies