Codeforces Round #760 A부터 D까지 업솔빙

Codeforces Round #760 A부터 D까지 업솔빙

알고리즘 놓은지 1달이 되서 다시 잡은 코드포스이다. 내가 코드포스에서 나오는 문제 유형을 잘 못하는걸로 결론을 내렸다. 하지만 내가 잘 못하는 것을 계속 손 놓고 있으면 그 분야는 계속 못하게 된다. 잘 몰라도 계속 붙잡는것이 필요한 순간. 언젠간 성장하겠지.

A. Polycarp and Sums of Subsequences (*800)

접기/펼치기

문제 설명
3개 양의 정수로 이루어진 배열 $a$가 주어진다. 이 배열로 만들 수 있는 모든 비어있지 않은 subsequence들의 원소의 총 합을 다른 배열에 적는다. 그리고 이 배열을 오름차순으로 정렬한다. 그러면 $7$개의 원소로 이루어진 배열 $b$가 만들어진다.

배열 $b$가 주어졌을 때, $a$를 구하라.

문제 해설
처음에 문제를 풀때는 제한 조건이 너무 널널하기에 그냥 3중 for문 완전탐색으로 풀었다. 이 방법도 컴퓨터에서는 매우 중요한 접근이기 때문에 이런 방법도 있다고 생각만 하자.
정해는 다음과 같다.
일단 $b$배열이 오름차순으로 이루어져 있기 때문에 $a$의 원소를 $[a_1, a_2, a_3]$이라고 하고, $(a_1 \le a_2 \le a_3)$라고 할 때, $b$의 맨 앞에 두 원소는 무조건 $a_1$, $a_2$이다. $b$배열은 원소들을 더해서 만들어지는 배열이기 때문에 뒤에 있는 원소는 무조건 많은 원소를 더해서 만든 값이기 때문이다. 따라서 맨 앞에 있는 두 원소 까지는 무조건 구할 수 있다. 그리고 $b$의 맨 마지막 값은 무조건 세 수를 더해서 만들어진 원소이기 때문에 앞에서 구한 두 원소를 빼면 답이 나온다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int a[7];
        for(auto& x : a) cin >> x;
        cout << a[0] << " " << a[1] << " " << a[6] - a[0] - a[1] << "\n";
    }
    return 0;
}

B. Missing Bigram (*800)

접기/펼치기

문제 설명
"A missing bigram"이라는 게임이 있다.

bigram은 한 문자열에서 두 인접한 문자끼리 이어 붙여서 만든 단어이다.

이 게임은 다음과 같이 진행한다. 소문자 'a'와 'b'로만 이루어진 단어 하나를 생각하고 칠판에 bigram이 나타난 순서대로 이 단어에서 나올 수 있는 모든 bigram을 적는다. 그리고 그중에 하나를 지운다.

내가 해야할 것은 이 bigram들을 보고 원래 이 사람이 생각했던 단어를 맞추는 것이다.

답이 여러개 있다면 그중에서 하나만 출력해도 된다.

문제 해설
쉽게 푼 문제이다. 일단 모든 bigram이 순서대로 적혀있기 때문에 그대로 이어 붙이면 되는데, $i$번째 bigram이 있을 때, $i - 1$번째 bigram의 경우를 확인해야 한다. $i$번째 bigram을 $a$, $i - 1$번째 bigram을 $b$라고 하면 $a$의 뒤쪽이 $b$의 앞쪽과 같다면 일단 붙이고 본다.

모든 단어가 붙여졌다면 주어진 단어의 수 보다 반드시 1개 문자가 부족한 단어가 생길것이다. 그러면 그냥 맨 뒤에 'a'를 쓰고 이 단어라고 우기면 된다.
만약 1개의 단어가 붙여지지 않았다면 그냥 그 단어를 뒤에 추가한다. 그리고 반드시 답은 존재한다고 했기 때문에 그 뒤에 있는 단어들은 모두 붙여질 것이고 그냥 답을 출력하면 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        string ans = "";
        for(int i = 0; i < n - 2; i++){
            string s; cin >> s;
            if(i == 0) ans = s;
            else{
                if(ans.back() == s.front()) ans += s.back();
                else ans += s;
            }
        }
        if(ans.size() != n) ans += 'a';
        cout << ans << "\n";
    }
    return 0;
}

C. Paint the Array (*1100)

접기/펼치기

문제 설명
양의 정수 $n$개로 이루어진 배열 $a$가 주엊인다. 양의 정수 $d$를 선택하고 모든 원소를 두 숫자로 색칠해야 한다. 각 원소가 $d$로 나누어 떨어진다면 빨간색으로, 그렇지 않으면 파란색으로 칠한다.

배열에서 인접한 원소가 같은 색으로 색칠하지 않은 쌍이 하나도 없으면 그 색칠은 아름답다고 한다. 아름다운 색칠을 만들 수 있는 값 $d$를 찾거나 불가능 하다는 것을 알아내야 한다.

문제 해설
간단한 문제이고 노트에 푸는 방법까지 다 적어놨는데 왜 구현을 못했지? 일단 서로 인접한 원소가 같은 색깔이면 안되기 때문에 짝수번째와 홀수번째로 나누어야 한다. 그리고 각 원소가 들어간 집합의 최대 공약수를 구한다. 왜냐하면 최대 공약수는 이 집합에 존재하는 모든 원소를 나눌 수 있는 공약수 중에서 최대값을 구한 것이고, 이 값이 1이면 이 집합의 공약수가 존재하지 않기 때문에 이 집합에서는 답을 찾을 수 없다.

따라서 두 집합의 최대공약수를 각각 구하고 홀수 집합이면 짝수 집합에서 구한 최대공약수로, 짝수 집합이면 홀수 집합에서 구한 최대공약수로 다른 집합의 모든 원소를 나눠봤을때 한번이라도 나누어 떨어지면 최대공약수의 약수들 또한 나누어 떨어지기 때문에 색깔을 아름답게 칠할 수 없다. 이 작업을 코드로 구현하면 답이다.

두 경우 모두 답이 없다면 0을 출력하면 되고 답이 있는 경우는 그 경우를 출력하면 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        ll a[n]; 
        ll x = 0, y = 0;
        for(int i = 0; i < n; i++){
            cin >> a[i];
            if(i % 2 == 0) x = gcd(x, a[i]);
            else y = gcd(y, a[i]);
        }
        ll d = 0;
        bool c1 = true, c2 = true;
        for(int i = 0; i < n; i++){
            if(i % 2 == 0){
                if(a[i] % y == 0 || y == 1) c1 = false;
            }else{
                if(a[i] % x == 0 || x == 1) c2 = false;
            }
        }

        if(c1) d = y;
        if(c2) d = x;
        cout << d << "\n";
    }
    return 0;
}

D. Array and Operations (*1300)

접기/펼치기

문제 설명
정수 $n$개가 있는 배열 $a$가 주어진다. 그리고 $2k \le n$ 인 정수 $k$이 주어진다.

이 배열에 정확히 $k$번의 연산을 수행해야 한다. 한 연산에서 배열에서 두 원소를 선택하고 배열에서 제거한다. 그리고 내 점수에 $[\frac{a_i}{a_j}]$ 를 더한다.

처음에 내 점수는 $0$이고 정확히 $k$번 연산을 진행한 후 배열에서 남은 원소를 전부 점수에 더한다.

얻을 수 있는 최소 점수를 구하라.

문제 해설
일단 먼저 큰 수를 골라야 한다는 사실은 자명하다. 왜냐하면 수 2개를 더할것을 수 1개만 더하면 되기 때문이다. 그러면 문제에서 $2k \le n$이기 때문에 배열 $a$를 먼저 정렬을 하고 맨 뒤에서 부터 $2k$개 원소를 고른다. 그리고 나머지 원소는 점수에 더한다.

이제 $k$번의 연산을 통해서 점수를 계산해야 하는데, 최대한 서로 다른 숫자를 골라서 제거해야 최적의 해가 나올 수 있다. 서로 다른 숫자를 고르면 무조건 이 $[\frac{a_i}{a_j}]$ 점수가 0이 되기 때문이다. 그것을 고르는 방법을 찾는 것이 이 문제의 핵심인데 그것은 다음과 같다.

원소 개수가 $2k$개인 배열에서 가장 많은 개수를 가지고 있는 원소를 찾는다. 그러면 그 원소와 나머지 원소를 짝지으면 그 원소 개수 만큼 0이 만들어 질 것이다.
그런데 그 원소의 개수가 $k$보다 크다면 모두 0이 만들어지지 않는다. 그러면 일단 서로 다른 수 끼리 짝짓고 나서 남은 원소는 모두 한가지 원소로만 이루어져 있을 것이다. 그 원소들을 선택해서 점수를 구하면 가장 많이 등장한 원소의 빈도수를 $p$라고 하면 $max(0, p - k)$만큼의 점수가 등장하고 이전에 더했던 점수에 이 값을 더하면 답이 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, k; cin >> n >> k;
        int a[n]; 
        for(auto& x : a) cin >> x;
        sort(a, a + n);

        int mx = 0, ans = 0, idx = n - 2 * k;
        for(int i = 0; i < idx; i++) ans += a[i];

        map<int, int> mp;
        for(int i = idx; i < n; i++){
            mp[a[i]]++;
            mx = max(mx, mp[a[i]]);
        }

        cout << ans + max(0, mx - k) << "\n";
    }
    return 0;
}