2022 구글 코드잼 Qualification Round 후기

4솔을 하고 71점을 먹었다.
A번만 풀고 과제하다가 자고 일어나면 시간이 끝날 거 같아서 3시까지 풀다 잤다.. 피곤해 죽을 뻔.. 30점만 먹고 자려했는데 4번 풀이가 보여서 이것만 풀고 자야지하다가 맞왜틀 박으면서 늦게까지 풀었다. 마지막 문제는 쓰윽 보고 문제가 이상하길래 그냥 안 풀고 맘 편히 잤다.

A. Punched Cards

이쁘게 출력만 하면 되는 간단한 구현문제다.

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

char arr[100][100];

void f1(int r, int c) {
    char cc[2] = {'+', '-'};
    for (int i = 0; i < 2 * c + 1; i++) arr[r][i] = cc[i % 2];
}
void f2(int r, int c) {
    char cc[2] = {'|', '.'};
    for (int i = 0; i < 2 * c + 1; i++) arr[r][i] = cc[i % 2];
}

int main() {
    int tc; cin >> tc;
    for (int _ = 1; _ <= tc; _++) {
        printf("Case #%d:\n", _);
        memset(arr, 0, sizeof(arr));
        int r, c; cin >> r >> c;
        for (int i = 0; i < 2 * r + 1; i++) {
            if (i % 2) f2(i, c);
            else f1(i, c);
        }
        arr[0][0] = arr[0][1] = arr[1][0] = '.';
        for (int i = 0; i < 2 * r + 1; i++) {
            printf("%s\n", arr[i]);
        }
    }
}

B. 3D Printing

3개의 셋에서 c, m, y, k 를 같은 수만큼 뽑아서 합이 딱 10^6을 만들면 된다.

c, m, y, k의 각각 최소를 구하고 10^6까지만 더하고 나머지는 버린다.

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

constexpr int mx = 1e6;
int arr[4][5];

int main() {
    int tc; cin >> tc;
    for (int _ = 1; _ <= tc; _++) {
        cout << "Case #" << _ << ": ";
        for (int i = 0; i < 3; i++) for (int j = 0; j < 4; j++) cin >> arr[i][j];
        
        vector<int> ans(4, 1e8);
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 3; j++) {
                ans[i] = min(ans[i], arr[j][i]);
            }
        }
        int tot = 0;
        for (auto x : ans) tot += x;
        if (tot < mx) cout << "IMPOSSIBLE\n";
        else {
            tot = 0;
            for (auto &x : ans) {
                if (tot + x > mx) x = mx - tot;
                tot += x;
                cout << x << " ";
            }
            cout << endl;
        }
    }
}

C. d1000000

A1, A2, ,,, An이 주어지고 Ai를 Ai보다 작은 수로 만들 수 있을 때, 만들 수 있는 1,2 ... , k인 최대 k를 구하면 된다.
정렬을 하고 그리디하게 뽑으면 된다.

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

int main() {
    int tc; cin >> tc;
    for (int _ = 1; _ <= tc; _++) {
        int n; cin >> n;
        vector<int> arr(n);
        for (auto &x : arr) cin >> x;
        sort(arr.begin(), arr.end());
        int ans = 0;
        for (auto x : arr) {
            if (x > ans) ans++;
        }
        cout << "Case #" << _ << ": " << ans << "\n";
    }
}

D. Chain Reactions

dfs를 순회하면서 어떤 수를 고르면 될지 잘 선택하면 되는 문제다.
문제에서 주어진 간선을 뒤집어 0번부터 시작하는 트리를 만들어 dfs를 순회한다.
트리에서 자식노드가 2개 이상 있을 때, 어떤 자식 노드부터 고르느냐에 따라 현재 노드가 어디에 속할지 정해진다.
합이 가장 크게 만들기 위해서는 값이 더 작은 노드 쪽에 속해져야 한다. 이 부분을 잘 처리하면 된다.

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

constexpr int N = 1e5 + 5;
int p[N];
vector<int> v[N];
int f[N];

int mn[N];
ll dfs(int cur) {
    if (!v[cur].size()) {
        mn[cur] = min(mn[cur], f[cur]);
        return f[cur];
    }
    ll ret = 0;
    for (auto nxt : v[cur]) {
        mn[nxt] = 1e9 + 9;
        ret += dfs(nxt);
        mn[cur] = min(mn[cur], mn[nxt]);
    }
    if (f[cur] > mn[cur]) {
        ret = ret - mn[cur] + f[cur];
        mn[cur] = f[cur]; 
    }
    return ret;
}

int main() {
    int tc; cin >> tc;
    for (int _ = 1; _ <= tc; _++) {
        for (int i = 0; i < N; i++) v[i].clear();
        int n; cin >> n;
        for (int i = 1; i <= n; i++) cin >> f[i];
        for (int i = 1; i <= n; i++) cin >> p[i], v[p[i]].push_back(i);
        mn[0] = 1e9 + 9;
        ll ans = dfs(0);
        cout << "Case #" << _ << ": " << ans << '\n';
    }
}