Manthan, Codefest 18 (rated, Div. 1 + Div. 2) 후기

Manthan, Codefest 18 (rated, Div. 1 + Div. 2)

A. Packets
영어가 안 돼서 문제를 이해하느라 힘들었다.
문제 내용은, 동전의 총합이 \(n\)이 되고, 그 중 몇개를 뽑아 합으로 \(1\)부터 \(n\)까지의 수를 모두 만들 수 있게 하는 동전의 최소 개수를 구하는 것이다.
동전을 선택하는 것을 비트로 생각하면, 이진수로 나타내는 것이 가장 효율적이므로 가까운 2의 제곱수를 찾으면 된다.
이해 못 하고 한 번 제출해서 틀렸었다.

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

B. Reach Median
중앙값이 특정 수로 되도록 하라는 건데, 그렇다면 만약 특정 수보다 작은 수가 \(n/2\)개 이하라면 그 수들은 바꿀 필요가 없다. 큰 수도 마찬가지다. 그리고 만약 \(n/2\)개가 넘는다면 넘는만큼 바꿔줘야 한다.

#include <bits/stdc++.h>
 
long long arr[200000];
 
int main() {
    int n;
    long long s, cnt = 0, ans = 0;
    scanf("%d %lld", &n, &s);
    for (int i = 0;i < n;++i) {
        scanf("%lld", &arr[i]);
        if (arr[i] < s)
            cnt++;
    }
    std::sort(arr, arr + n);
    if (cnt < n / 2)
        for (int i = cnt;i < n / 2;++i)
            ans += arr[i] - s;
    else if (cnt > n / 2)
        for (int i = cnt - 1;i > n / 2;--i)
            ans += s - arr[i];
    printf("%lld", ans + abs(s - arr[n / 2]));
 
    return 0;
}

C. Equalize
바꾸는 연산의 비용이 두 원소 사이의 거리인데, 반전하는 연산은 1이므로 거리가 2 이상인 원소를 바꿀 바에는 두 원소를 각각 반전하는 것이 이득이다. 그러므로 바꾸는 연산은 인접한 원소끼리만 확인하면 된다.

#include <bits/stdc++.h>
 
int a[1000000], b[1000000];
 
int main() {
    int n, cnt = 0;
    scanf("%d", &n);
    for (int i = 0;i < n;++i)
        scanf("%1d", &a[i]);
    for (int i = 0;i < n;++i)
        scanf("%1d", &b[i]);
 
    for (int i = 0;i < n;++i) {
        if (i + 1 < n && (a[i] != b[i]) && (a[i + 1] != b[i + 1]) && (a[i] != a[i + 1])) {
            cnt++;
            a[i] = b[i];
            a[i + 1] = b[i + 1];
        }
        else if (a[i] != b[i])
            cnt++;
    }
 
    printf("%d", cnt);
 
    return 0;
}

D. Valid BFS?
주어지는 방문 순서가 BFS의 방문 순서로 가능한지를 묻는 문제이다.
처음에는 단순히 깊이로 올바른지 판정하면 될 줄 알았는데, 생각해보니 앞에서 어떤 순서로 방문했는지도 중요한 문제였다.
더 효율적인 방법이 있을것 같긴 한데, 내가 한 방법은 어차피 다음 방문이 될 노드들의 개수는 정해져 있으므로 개수만큼 덩어리로 묶어서 비교하는 방법으로 풀었다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> gph[200001];
int dep[200001], arr[200001], pos[200001];
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0;i < n - 1;++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        gph[u].push_back(v);
        gph[v].push_back(u);
    }
    for (int i = 1;i <= n;++i) {
        scanf("%d", &arr[i]);
        pos[arr[i]] = i;
    }
 
    if (arr[1] != 1) {
        printf("No");
 
        return 0;
    }
 
    int cnt = 1;
    queue<int> q;
    dep[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
 
        queue<int> tmp;
        int cntt = 0;
        for (int nxt : gph[now])
            if (dep[nxt] == 0) {
                dep[nxt] = dep[now] + 1;
                tmp.push(nxt);
                cntt++;
            }
 
        while (!tmp.empty()) {
            if (pos[tmp.front()] <= cnt || pos[tmp.front()] > cnt + cntt) {
                printf("No");
 
                return 0;
            }
            tmp.pop();
        }
 
        for (int i = cnt + 1;i <= cnt + cntt;++i)
            q.push(arr[i]);
        cnt = cnt + cntt;
    }
    printf("Yes");
 
    return 0;
}

그리고 E번도 봤는데, 이분탐색인가 고민해보다가 포기했다. 이 정도는 풀어야 Div2 C번도 풀텐데...