코드포스 Educational Codeforces Round 126 풀이 (A ~ C)

오늘 Codeforces에서 contest가 있길래 잠깐 풀어봤습니다.

Contest명은 Educational Codeforces Round 126 (Div 2)이고, 문제는 C번까지만 풀었습니다.

Div 2 대회라서 D~E 정도까지는 풀었어야 된다고 생각을 하는데 시간이 난다면 뒤의 문제들까지도 풀어보고 정리해보겠습니다.

 

 

A. Array Balancing

 

수열 a와 b가 있을 때, a_i와 b_i는 서로 교체가 가능하다고 할 때 주어진 수식의 최솟값을 구하는 문제입니다.

이 때 주어진 수식이란 a는 a끼리, b는 b끼리 서로 인접한 항의 차의 절댓값들의 합을 말합니다.

 

조금 생각해보면 수열에서 어떤 규칙을 발견할 필요없이 첫 항부터 뒤로 가면서 a_i와 b_i를 swap한 것과 하지 않은 것 중 절댓값의 합이 더 작은 쪽을 선택해나가면서 swap의 여부를 선택하는 그리디 문제임을 알 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
 
    int T; cin >> T;
 
    while(T--) {
        int N; cin >> N;
 
        vector<long long> a(N), b(N);
        for(int i=0; i<N; i++) cin >> a[i];
        for(int i=0; i<N; i++) cin >> b[i];
 
        long long sum = 0;
        for(int i=0; i<N-1; i++) {
            long long val1 = abs(a[i] - a[i+1]) + abs(b[i] - b[i+1]);
            long long val2 = abs(a[i] - b[i+1]) + abs(a[i+1] - b[i]);
 
            if(val1 < val2) sum += val1;
            else sum += val2;
        }
 
        cout << sum << "\n";
    }
}

 

문제에서 항의 개수는 최대 25개이고, 각 항은 최대 10^9까지 입력이 들어올 수 있으므로 overflow를 피하기 위해 long long 자료형을 사용해주었습니다.

 

 

B. Getting Zero

 

수열의 한 항 v에 대해 +1 또는 ×2라는 연산의 두 가지 선택지가 있다고 할 때(물론 mod 32768 내에서), a_i를 0으로 만들기 위한 최소 연산 횟수를 구하는 문제입니다.

이 문제는 백준에서 많이 나오는 BFS 문제이기 때문에 간단하게 구현할 수 있었습니다.

 

 

#include <bits/stdc++.h>
#define MOD 32768
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
 
    int T; cin >> T;
 
    while(T--) {
        int N; cin >> N;
 
        int dp[MOD] = {};
        bool visit[MOD] = {};
 
        queue<int> Queue;
        Queue.push(N);
        visit[N] = true;
 
        while(!Queue.empty()) {
            int v = Queue.front();
            Queue.pop();
 
            if(v == 0) break;
 
            if(!visit[(v+1)%MOD]) {
                Queue.push((v+1)%MOD);
                visit[(v+1)%MOD] = true;
                dp[(v+1)%MOD] = dp[v] + 1;
            }
 
            if(!visit[(v*2)%MOD]) {
                Queue.push((v*2)%MOD);
                visit[(v*2)%MOD] = true;
                dp[(v*2)%MOD] = dp[v] + 1;
            }
        }
 
        cout << dp[0] << " ";
    }
}

 

dp[i]는 i까지 도달하기 위한 최소 연산 횟수로 정의하여 풀이하였고, visit[i]는 i까지 연산을 통해 도달하는 방법이 발견되었나를 의미합니다.

BFS로 연산하기 때문에 어떤 수에 최초로 방문하면, 이후로는 dp 값을 갱신할 필요가 없습니다. (그 다음에 방문했을 때는 무조건 더 많은 횟수의 연산을 해야하기 때문)

 

 

C. Water the Trees

 

N개의 나무의 크기가 주어졌을 때, 홀수 번째 날에는 나무 하나를 선택하여 1만큼 자라게 할 수 있고, 짝수 번째 날에는 나무 하나를 선택하여 2만큼 자라게 할 수 있다고 할 때 모든 나무의 크기를 동일하게 만들 수 있는 최소 날의 수를 구하는 문제입니다.

 

우선 가장 처음에 해볼 수 있는 생각은 최대 길이를 가진 나무에 맞추어 다른 나무들도 성장시키는 방법입니다.

최대 길이를 가진 나무의 길이에서 나머지 나무들의 길이를 뺀 길이의 차들을 구하고, 이들을 최대한 1과 2의 개수가 비슷하게끔 나누어주어야 합니다.

 

그러기 위해서 일단 2를 최대한 많이 남기고 1은 길이의 차를 2로 나눴을 때 나머지가 1이 남는 어쩔 수 없는 경우만 제외하고는 최대한 줄여줍니다.

그 다음 2를 1과 2의 개수가 최대한 비슷하게 두 개의 1로 나누어줍니다. (저는 1:2 내분점을 생각하여 나눈 뒤 반올림을 해주는 방법을 택했습니다.)

 

그러면 이제 1과 2의 개수를 짝지어서 각각 홀수 날에는 1만큼, 짝수 날에는 2만큼 나무를 자라게 하면 되고, 어쩔 수 없이 남는 1 또는 2에 맞추어 날짜를 처리해주면 됩니다.

 

 

그런데 사실 아직 예외가 남아있습니다.

예를 들어 나무의 길이들이 4, 4, 4, 4, 4, 4, 5와 같이 1이 굉장히 많이 남게 된다면 날짜의 소모가 굉장히 많아져 비효율적인 답이 얻어집니다.

따라서 이런 경우에는 모든 나무의 길이를 6으로 만들어주는 것이 더 빨리 끝날 수 있습니다.

그렇기 때문에 Max를 1 증가시킨 상황에서 구한 답까지 비교해서 최종 답을 얻어줄 수 있도록 하면 모든 테스트케이스에 대해서 정답 처리를 받을 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
 
    int T; cin >> T;
 
    while(T--) {
        int N; cin >> N;
 
        vector<long long> tree(N);
        long long Max = 0;
        for(int i=0; i<N; i++) {
            cin >> tree[i];
            Max = max(Max, tree[i]);
        }
 
        long long one = 0, two = 0;
        for(int i=0; i<N; i++) {
            one += (Max - tree[i]) % 2;
            two += (Max - tree[i]) / 2;
        }
 
        if(one < two) {
            long long div = round(((double)two - one) / 3.0);
            one += div * 2;
            two -= div;
        }
 
        long long temp = min(one, two);
        long long ans = temp * 2;
 
        one -= temp;
        two -= temp;
 
        if(one > 0) ans += one*2 - 1;
        else if(two > 0) ans += two*2;
 
        long long ans1 = ans;
 
 
        Max++;
        one = 0, two = 0;
        for(int i=0; i<N; i++) {
            one += (Max - tree[i]) % 2;
            two += (Max - tree[i]) / 2;
        }
 
        if(one < two) {
            long long div = round(((double)two - one) / 3.0);
            one += div * 2;
            two -= div;
        }
 
        temp = min(one, two);
        ans = temp * 2;
 
        one -= temp;
        two -= temp;
 
        if(one > 0) ans += one*2 - 1;
        else if(two > 0) ans += two*2;
 
        long long ans2 = ans;
 
        cout << min(ans1, ans2) << "\n";
    }
}

 

(저는 사실 코드를 간결하게 짜기가 귀찮아서 그냥 복사/붙여넣기 해서 코드의 길이가 길어졌는데, 아마도 높은 확률로 아주 간결한 풀이가 있을 것입니다.)

 

D번 이후의 문제들의 풀이에 대해서는 시간이 난다면 다룰 수 있도록 하겠습니다.