A. Array Balancing
Problem
https://codeforces.com/contest/1661/problem/A
Problem - A - Codeforces
codeforces.com
Tutorial
$a_1$과 $b_1$은 그대로 둔 상태에서, $2 \le i \le n$인 모든 i에 대하여 $|a_{i-1} - a_i| + |b_{i-1} - b_i|$가 최소가 되도록 $a_i$와 $b_i$를 바꿔주면 된다. $a_{i-1}$과 $b_{i-1}$의 위치가 서로 바뀌더라도 위치만 바뀌고, 값은 바뀌지 않기 때문에 단순히 기존 수열에서 $sum(min(|a_{i-1} - a_i| + |b_{i-1} - b_i|, |a_{i-1} - b_i| + |b_{i-1} - a_i|))$을 구하여 답을 구할 수 있다.
Solution
#include <bits/stdc++.h>
using namespace std;
int a[30], b[30];
int main()
{
int t, n, i;
long long ans;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> n;
for(i=0; i<n; i++) cin >> a[i];
for(i=0; i<n; i++) cin >> b[i];
ans = 0;
for(i=1; i<n; i++){
ans += min(abs(a[i]-a[i-1])+abs(b[i]-b[i-1]), abs(a[i]-b[i-1])+abs(b[i]-a[i-1]));
}
cout << ans << '\n';
}
return 0;
}
B. Getting Zero
Problem
https://codeforces.com/contest/1661/problem/B
Problem - B - Codeforces
codeforces.com
Tutorial
이 문제의 경우 딱 봤을 때, 전처리를 해주면 좋겠다는 생각이 든다.
v가 0일 때는 답이 0이며, v를 거꾸로 계산하면서 모든 v들에 대하여 v가 0이 될 때까지 걸리는 작업의 최소 횟수를 bfs로 구해주면 된다. 이때 주의해야 할 점은 v = 2*v에서 모듈러 연산이 들어가기 때문에 거꾸로 계산하면 v = v/2와 v = (v+32768)/2를 둘 다 해줘야 한다는 것이다.
Solution
#include <bits/stdc++.h>
#define MAX 32768
using namespace std;
int ans[MAX];
queue<int> que;
int main()
{
int n, i, a, v, cnt;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
for(i=0; i<MAX; i++) ans[i] = -1;
que.push(0);
que.push(0);
while(!que.empty()){
v = que.front(); que.pop();
cnt = que.front(); que.pop();
if(ans[v] != -1) continue;
ans[v] = cnt;
que.push((v-1+MAX)%MAX);
que.push(cnt+1);
if(v%2 == 0){
que.push(v/2);
que.push(cnt+1);
que.push((v+MAX)/2);
que.push(cnt+1);
}
}
cin >> n;
for(i=0; i<n; i++){
cin >> a;
cout << ans[a] << ' ';
}
return 0;
}
C. Water the Trees
Problem
https://codeforces.com/contest/1661/problem/C
Problem - C - Codeforces
codeforces.com
Tutorial
처음에 무조건 제일 높은 나무에는 물을 주지 않고 모든 나무를 가장 높은 나무의 높이에 맞춰야 한다고 생각하였다. 그러나 코드를 보면 알 수 있듯이(막판에 코드를 복붙 해서 코드가 더럽다 ㅜㅜ) 마지막에 가장 높은 나무의 높이 + 1로 맞췄을 때의 최솟값도 같이 구한 후, 두 값의 최솟값을 출력하게 하니깐 답을 맞힐 수 있었다. (아직 이러한 경우가 무엇인지 알아내지 못했다 ㅜㅜ 알려주세요 ㅜㅜ)
우선 만들고자 하는 높이 H를 정한다. 모든 나무들에 대하여 해당 높이가 되기 위해 필요한 높이들을 구해준다. 그리고 우리는 1, 2를 번갈아 사용하며, 필요한 높이들을 전부 만들어야 한다. (이렇게 1, 2를 이용해서 숫자를 만드는 문제 어디서 푼거 같은데.... 무슨 계란 옮기는 문제였던 거 같은데 잘 기억이 안 난다 ㅜㅜ)
이를 해결하기 위해 필요한 높이들을 3으로 나눈 나머지로 나무들을 나눈다. 물을 연속으로 뿌려주면 3의 배수를 만들 수 있기 때문에 우리의 목표는 모든 나무들이 필요한 높이가 3의 배수가 되도록 하는 것이다. 이렇게 되면 (필요한 높이)/3*2 가 해당 나무를 목표 높이로 만드는데 필요한 일수이기 때문이다.
또한 나머지가 1인 나무들과 나머지가 2인 나무들의 개수가 같다면 홀수날은 나머지가 1인 나무에, 짝수날은 나머지가 2인 나무에 물을 뿌려 이들을 전부 필요한 높이가 3의 배수가 되도록 만들 수 있다. 그러면 우리의 2번째 목표는 이것이 된다. 이를 달성하면 첫번째 목표를 달성할 수 있다.
두번째 목표를 달성하려면 어떻게 해야 될까? 더 많은 쪽 나무를 2개의 나무로 가정함으로써 이를 해결할 수 있다. 나머지가 1인 나무의 필요한 높이를 h라고 할 때 이 나무를 필요한 높이가 2인 나무와 필요한 높이가 h-2인 나무로 가상으로 나누고, 나머지가 2인 나무는 필요한 높이가 1인 나무와 필요한 높이가 h-1인 나무로 가상으로 나누는 것이다. 이렇게 하면 두 나무의 수의 차이를 줄일 수 있다. 그러나 이때 주의해야 할 점은 나머지가 1인 나무들이 전부 필요한 높이가 1인 경우이다. 이 경우 필요한 높이를 나눌 수 없기 때문에 필요한 높이가 3의 배수인 나무들을 3개로 쪼개야 한다. 필요한 높이가 3인 배수가 없는 경우에는 그대로 둔다.
위의 작업이 끝났으면, 이제 계산만 해주면 된다. 필요한 높이가 3의 배수인 나무들에 대하여 (필요한 높이/3*2) 만큼의 일수가 필요하며, 필요한 높이의 나머지가 1인 나무와 2인 나무를 쌍으로 묶으면, (필요한 높이의 합/3*2) 만큼의 일수가 필요하게 된다. 이후 쌍이 맺어지지 않는 나무들만 따로 계산해주면 된다. (아마 1이 여러개 남거나 나머지가 2인 나무만 남을 텐데, 1이 여러 개 남으면, (남은 나무*2-1) 만큼 일수를 더하고, 나머지가 2인 나무가 남으면 (필요한 높이/3*2+1)을 해주면 될 것이다.)
Solution
#include <bits/stdc++.h>
using namespace std;
int h[300010];
priority_queue<int> que[3];
int main()
{
int t, n, i, maxi=0, x, y;
long long ans, ans_;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> n;
maxi = 0;
for(i=0; i<n; i++){
cin >> h[i];
maxi = max(maxi, h[i]);
}
for(i=0; i<n; i++){
x = maxi-h[i];
if(x == 0) continue;
que[x%3].push(x);
}
ans = 0;
while((int)que[1].size() - (int)que[2].size() > 1){
x = que[1].top();
if(x == 1) break;
que[1].pop();
que[2].push(x-2);
que[2].push(2);
}
while((int)que[1].size() - (int)que[2].size() > 1){
if(que[0].empty()) break;
x = que[0].top();
if(x == 3) break;
que[0].pop();
que[2].push(x-4);
que[2].push(2);
que[2].push(2);
}
while((int)que[2].size() - (int)que[1].size() > 1){
x = que[2].top(); que[2].pop();
que[1].push(x-1);
que[1].push(1);
}
while(!que[1].empty() && !que[2].empty()){
x = que[1].top(); que[1].pop();
y = que[2].top(); que[2].pop();
ans += (x+y)/3*2;
}
while(!que[0].empty()){
x = que[0].top(); que[0].pop();
ans += x/3*2;
}
if(!que[1].empty()){
x = que[1].top(); que[1].pop();
ans += x/3*2 + 1;
}
if(!que[2].empty()){
x = que[2].top(); que[2].pop();
ans += x/3*2 + 2;
}
while(!que[1].empty()){
x = que[1].top(); que[1].pop();
ans += x/3*2 + 2;
}
ans_ = ans;
while(!que[0].empty());
while(!que[1].empty());
while(!que[2].empty());
// ------------------------------------------------
for(i=0; i<n; i++){
x = maxi-h[i]+1;
que[x%3].push(x);
}
ans = 0;
while((int)que[1].size() - (int)que[2].size() > 1){
x = que[1].top();
if(x == 1) break;
que[1].pop();
que[2].push(x-2);
que[2].push(2);
}
while((int)que[1].size() - (int)que[2].size() > 1){
if(que[0].empty()) break;
x = que[0].top();
if(x == 3) break;
que[0].pop();
que[2].push(x-4);
que[2].push(2);
que[2].push(2);
}
while((int)que[2].size() - (int)que[1].size() > 1){
x = que[2].top(); que[2].pop();
que[1].push(x-1);
que[1].push(1);
}
while(!que[1].empty() && !que[2].empty()){
x = que[1].top(); que[1].pop();
y = que[2].top(); que[2].pop();
ans += (x+y)/3*2;
}
while(!que[0].empty()){
x = que[0].top(); que[0].pop();
ans += x/3*2;
}
if(!que[1].empty()){
x = que[1].top(); que[1].pop();
ans += x/3*2 + 1;
}
if(!que[2].empty()){
x = que[2].top(); que[2].pop();
ans += x/3*2 + 2;
}
while(!que[1].empty()){
x = que[1].top(); que[1].pop();
ans += x/3*2 + 2;
}
cout << min(ans_, ans) << '\n';
while(!que[0].empty());
while(!que[1].empty());
while(!que[2].empty());
}
return 0;
}
마치며...
최근에 계속 D번을 못 풀어 아쉬운 마음이 있었는데, 이번 시험에서는 C번까지도 10분 남기고 겨우 풀어 내 실력에 회의감을 느꼈다. 최근 새로운 알고리즘을 공부하지도 않았고, 알고리즘에 집중할 시기가 아니라고 애써 변명을 해보고 있지만 코드포스를 치르는 2시간을 온전히 집중하지 못할 만큼 바쁘지는 않다는 게 사실이다. 좀 더 시간을 효율적으로 관리하며 살아야겠다는 반성을 하게 되는 대회였다. (갑자기?)
'Algorithm > Codeforces' 카테고리의 다른 글
| Codeforces Round #782 (Div. 2) (0) | 2022.04.19 |
|---|---|
| Codeforces Round #781 (Div. 2) - D (0) | 2022.04.16 |
| [Codeforces] Codeforces Round #781 (Div. 2) (0) | 2022.04.12 |
| [Codeforces] Codeforces Round #780 (Div. 3) - B (0) | 2022.04.08 |
| [Codeforces] 1658D - 388535 (0) | 2022.03.29 |
