Google Code Jam 2018 Round 1A

토요일에 GCJ Round 1A를 치기 전에 부랴부랴 2018 기출을 풀어봤다. A, B는 쉬운데 C는 특히 Large가 어려워서 고생했다.

Waffle Choppers
Bit Party
Edgy Baking

Waffle Choppers

R x C 크기의 직사각형 격자(와플)를 가로로 h번, 세로로 v번 잘라서 각 잘린 조각에 들어있는 @(초코칩) 의 개수가 같도록 만들 수 있는지 확인하는 문제이다.

풀이는 간단하게 가로와 세로에 대해 자를 부분을 따로 찾을 수 있다는 것을 이용하면 된다. 가로로 자른 각각의 부분은 초코칩을 (v+1) x (조각 별 초코칩 수) 개 가지고 있어야 한다. 마찬가지로 세로의 경우에도 각 조각이 (h+1) x (조각 별 초코칩 수) 개의 초코칩을 가지고 있어야 한다.

이렇게 자를 부분을 따로 구하고 나면 실제 조각들이 몇 개의 초코칩을 갖게 되는지 알 수 있으므로 마지막 체크만 하면 쉽게 해결할 수 있다.

#include<cstdio>
#include<vector>
using namespace std;
using ll = long long;
const int MAXN = 111;
inline void invariant(bool x) { if (!x) throw x; }

int n, m, h, v, d[MAXN][MAXN];

vector<int> get_cuts(int stake, bool transpose=false) {
    int m = (transpose ? ::n : ::m),
        n = (transpose ? ::m : ::n),
        cuts = (transpose ? v : h),
        div = (transpose ? h : v) + 1;

    vector<int> res(cuts);
    for (int k = 0, i = 1; k < cuts; k++) {
        int choco = 0;
        while (i <= n && choco < div * stake) {
            choco += transpose? (d[m][i] - d[m][i-1]) : (d[i][m] - d[i-1][m]);
            ++i;
        }

        res[k] = i - 1;
        invariant(choco == div * stake);
    }

    return res;
}

bool solve()
{
    for (int i = 1; i <= n; i++) {
        char f[MAXN]{};
        scanf("%s", f+1);
        for (int j = 1; j <= m; j++)
            d[i][j] = f[j] == '@';
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];
    }

    int pieces = (h + 1) * (v + 1);
    int stake = d[n][m] / pieces;
    invariant(d[n][m] % pieces == 0);
    if (stake == 0) return true;

    int pi = 0;
    auto&& vcuts = get_cuts(stake, true);
    auto&& hcuts = get_cuts(stake);
    for (auto& ci: hcuts) {
        int pj = 0;
        for (auto& cj: vcuts) {
            int chocolates = d[ci][cj] - d[pi][cj] - d[ci][pj] + d[pi][pj];
            invariant(chocolates == stake);
            pj = cj;
        }
        pi = ci;
    }

    return true;
}

int main()
{
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        printf("Case #%d: ", C);
        scanf("%d%d%d%d", &n, &m, &h, &v);
        try {
            solve();
            puts("POSSIBLE");
        } catch (...) {
            puts("IMPOSSIBLE");
        }
    }
    return 0;
}

R대의 로봇이 C대의 서로 다른 계산대를 이용해서 B개의 물품(비트)을 계산하려고 한다. 각 계산대 $i$는 최대 $M_i$개의 비트만을 계산할 수 있고, $N (N ≤ M_i)$개의 비트를 계산하는 데에 $S_i \cdot N + P_i$ 만큼의 시간이 걸린다. 각 로봇이 최소 한 개의 비트를 계산해야 하며, 각자 다른 계산대를 이용해야 할 때, 계산을 모두 끝마치는 데에 걸리는 최소 시간은 얼마일까?

풀이는 바이너리 서치를 이용해서 시간 제한 $T$를 정하고, 해당하는 시간 제한 내에 모든 비트(B개)를 계산할 수 있는지 확인하면 간단하게 구현할 수 있다.

시간 제한이 고정돼 있을 경우에 각 계산대가 계산할 수 있는 비트의 수는 $\mathrm{max}(\mathrm{min}((T - P_i) / S_i, M_i), 0)$ 이 된다. 여기서 가장 많은 수의 비트를 계산할 수 있는 $R$개의 계산대의 비트 수를 더한 것이 바로 시간 제한 T 안에 계산할 수 있는 비트 개수의 최댓값이다.

#include<cstdio>
#include<vector>
#include<numeric>
#include<algorithm>
#define RALL(X) (X).rbegin(),(X).rend()
using namespace std;
using ll = long long;

const int MAXN = 1e3 + 10;

ll n, m, b;
ll s[MAXN], p[MAXN], u[MAXN];

ll calc_max(ll t)
{
    vector<ll> v(n);
    for (int i = 0; i < n; i++) {
        v[i] = max(0LL, min(ll(t - p[i]) / s[i], ll(u[i])));
    }
    sort(RALL(v));
    return accumulate(v.begin(), v.begin() + m, 0LL);
}

ll solve()
{
    ll l = 0, r = 1LL << 60, ans = r;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (calc_max(mid) >= b) {
            r = mid - 1;
            ans = mid;
        } else l = mid + 1;
    }
    return ans;
}

int main()
{
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        scanf("%lld%lld%lld", &m, &b, &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld%lld%lld\n", u + i, s + i, p + i);
        }
        printf("Case #%d: %lld\n", C, solve());
    }
    return 0;
}

Edgy Baking

이건 졸려서 내일..

Waffle Choppers

Bit Party

Edgy Baking