Educational Codeforces Round 148 (Rated for Div. 2)
Educational Codeforces Round 148 (Rated for Div. 2)
A. New Palindrome
$s$가 팰린드롬이므로 $\lvert s \rvert / 2$ 개의 문자만 봤을 때, 모두 같다면 바꿀 수 없고, 그렇지 않다면 적절히 swap해서 다른 팰린드롬을 만들 수 있다.
$s$가 팰린드롬이란 제한을 못봐서 오래걸렸다.
B. Maximum Sum
수를 정렬하고 앞에서 두 개씩, 뒤에서 한개씩 미는 방식으로 투 포인터를 관리하면 쉽게 풀 수 있다.
C. Contrast Value
단조적으로 비감소하거나 비증가하는 부분들을 양 옆 두 개만 남기고 중간에 있는 것들을 모두 삭제한다.
나머지 것들을 지울 순 없다. 그럼 $\lvert a_i - a_{i+1} \rvert$ 의 합이 무조건 작아지기 때문이다.
D1. Red-Blue Operations (Easy Version)
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)
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 << ' ';
}
}
}
}
Comments