Codeforces Round #508 (Div. 2) 후기

Codeforces Round #508 (Div. 2)

A. Equality
글자가 나온 위치는 상관이 없기 때문에, 가장 적게 나온 알파벳 개수만큼 다른 알파벳들도 추가할 수 있다.

#include <bits/stdc++.h>
 
int cnt[26];
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0;i < n;++i) {
        char c;
        scanf(" %c", &c);
        cnt[c - 'A']++;
    }
 
    int ans = 1e8, acnt = 0;
    for (int i = 0;i < k;++i)
        ans = std::min(ans, cnt[i]);
    for (int i = 0;i < k;++i)
        if (cnt[i] >= ans)
            acnt++;
 
    printf("%d", ans * acnt);
 
    return 0;
}

B. Non-Coprime Partition
우선, 1과 2일 때는 나누는 것이 불가능하다.
여러 방법이 있겠지만, \(n\)까지의 합(\(\frac{n(n+1)}{2}\))이 짝수라면, \(2\)와 나머지로 나누었을 때 최대공약수는 2이므로 가능하다.
그리고 \(n\)까지의 합이 홀수라면, \(n\)과 나머지로 나누었을 때 최대공약수는 적어도 1보다 크다.
왜냐하면, 그렇게 나누었을 때 첫 그룹의 합은 \(n\)이 되고 둘째 그룹의 합은 \(\frac{n(n-1)}{2}\)이다. 그리고 \(n\)이 홀수라면 최대공약수는 적어도 \(n\)이 되고, 짝수라면 최대공약수는 적어도 \(\frac{n}{2}\)이므로 가능하다.

#include <bits/stdc++.h>
 
int main() {
    long long n;
    scanf("%lld", &n);
    if (n <= 2)
        printf("No");
    else if (n * (n + 1) / 2 % 2 == 0) {
        printf("Yes\n1 2\n%lld 1 ", n - 1);
        for (int i = 3;i <= n;++i)
            printf("%d ", i);
    }
    else {
        printf("Yes\n1 %lld\n%lld ", n, n - 1);
        for (int i = 1;i <= n - 1;++i)
            printf("%d ", i);
    }
 
    return 0;
}

C. Gambling
자신의 가장 큰 원소와 상대의 가장 큰 원소 중에 더 큰 것을 고르면 된다. 상대 점수를 없애는 것이 내 점수를 얻는다는 느낌이라 가능한 것 같다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<long long> a, b;
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0;i < n;++i) {
        long long u;
        scanf("%lld", &u);
        a.push_back(u);
    }
    sort(a.begin(), a.end());
    for (int i = 0;i < n;++i) {
        long long u;
        scanf("%lld", &u);
        b.push_back(u);
    }
    sort(b.begin(), b.end());
 
    long long ap = 0, bp = 0;
    for (int i = 0;i < n;++i) {
        if (b.empty() || !a.empty() && a.back() > b.back()) {
            ap += a.back();
            a.pop_back();
        }
        else
            b.pop_back();
 
        if (a.empty() || !b.empty() && b.back() > a.back()) {
            bp += b.back();
            b.pop_back();
        }
        else
            a.pop_back();
    }
 
    printf("%lld", ap - bp);
 
    return 0;
}

D. Slime
대회 끝나고나서 추가된 데이터 때문에 틀렸다 ㅠㅠ
슬라임이 인접해야 된다는 조건은 무시하고, 먹히지 않을 슬라임만 정하면 나머지는 이득이 되는 방향(절댓값)으로 조절할 수 있다.

#include <bits/stdc++.h>
 
int main() {
    int n;
    long long tot = 0, mn = 1e9 + 1;
    bool chp = false, chn = false;
    scanf("%d", &n);
    if (n == 1) {
        long long u;
        scanf("%lld", &u);
        printf("%lld", u);
 
        return 0;
    }
    for (int i = 0;i < n;++i) {
        long long u;
        scanf("%lld", &u);
        if (u > 0)
            chp = true;
        if (u < 0)
            chn = true;
        tot += abs(u);
        mn = std::min(mn, abs(u));
    }
 
    if (chp && chn)
        printf("%lld", tot);
    else if (chp && !chn)
        printf("%lld", tot - mn * 2);
    else if (!chp && chn)
        printf("%lld", tot - mn * 2);
    else
        printf("0");
 
    return 0;
}