Google Kick Start - Round F 2020

아깝다

ATM Queue

Kick Start - Google’s Coding Competitions

\(n\)명의 사람들이 ATM에서 돈을 뽑으려 줄을 서있다.

각 사람은 \(a_i\)만큼의 돈을 뽑으려 한다.

 

이 ATM은 한번에 \(x\)의 돈밖에 뽑을 수 없다.

자신의 차례에 돈을 뽑았는데 아직 총 \(a_i\)만큼의 돈을 뽑지 못했다면, 줄의 맨 뒤로 되돌아가 다시 줄을 서야 한다.

 

사람들이 돈을 다 뽑아서 돌아가는 순서를 출력해야 한다.

 

우선 \(\lceil \frac {a_i}{x} \rceil\)로 ATM을 이용하는 횟수를 알아낼 수 있다.

이 횟수가 적은 순으로, 같다면 초기에 앞쪽에 서있던 순으로 정렬하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll n, x;
ll a[100001];
 
vector <pll> v;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        cin >> n >> x;
        for (int i = 1; i <= n; i++) cin >> a[i];
 
        v.clear();
        for (int i = 1; i <= n; i++)
        {
            v.push_back({ (a[i] - 1) / x + 1, i });
        }
 
        sort(v.begin(), v.end());
 
        cout << "Case #" << tc << ":";
        for (auto it : v) cout << ' ' << it.second;
        cout << "\n";
    }
}

---

Metal Harvest

Kick Start - Google’s Coding Competitions

광석을 로봇을 이용해 캐려고 한다.

각 광석을 캐기 위해서는 \([s_i, e_i]\) 사이의 모든 시간을 로봇으로 작업해야 한다.

각 광석을 캐는 시간은 서로 겹치지 않는다.

로봇은 한 번에 \(k\)의 시간만큼 광석을 캘 수 있다.

 

\(n\)개의 모든 광석을 캐기 위해 로봇을 사용해야 하는 횟수를 알아내야 한다.

 

광석을 캐야 하는 시간을 정렬하고, 앞에서부터 그리디하게 \(k\)시간을 전부 사용해 캐 나가면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll n, k;
pll itv[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            cin >> itv[i].first >> itv[i].second;
 
        sort(itv + 1, itv + 1 + n);
 
        ll ans = 0;
        ll last = 0;
 
        for (int i = 1; i <= n; i++)
        {
            if (last >= itv[i].second) continue;
            if (last < itv[i].first) last = itv[i].first;
            ll res = (itv[i].second - last - 1) / k + 1;
 
            ans += res;
            last += res * k;
        }
 
        cout << "Case #" << tc << ": " << ans << '\n';
    }
}

 

 

여담으로 문제 디스크립션이 굉장히 애매하게 쓰여있어서 해석이 힘들었다.

(각 광석당 1의 시간만 작업하면 되는지 또는 전체 시간동안 작업해야 하는지 여부, 광석 하나를 한번의 로봇 사용으로만 캘 수 있는지 여부, \(s_i\)가 이미 정렬된 상태로 들어오는지 여부)

해석 문제로 11번 제출한 후에야 맞을 수 있었다.

---

Painters' Duel

Kick Start - Google’s Coding Competitions

한 변의 길이가 \(s\) 길이인 정삼각형이 있다. 이 정삼각형은 한 변의 길이가 1인 정삼각형 (방)으로 나누어져 있다.

Alma, Berthe 두 사람이 이 정삼각형 판에서 게임을 하려고 한다.

두 사람은 임의의 방에서 시작해, 자신의 차례에 변으로 인접한 방으로 이동해 색칠한다.

처음 시작하는 방은 이미 색칠되어 있고, 이미 색칠된 방이나 문제에서 주어지는 움직일 수 없는 방으로는 움직일 수 없다.

 

자신의 차례에 움직일 수 없으면 차례를 넘기고, 둘 다 움직일 수 없으면 게임이 종료된다.

게임의 점수는 (Alma가 색칠한 칸 수 - Berthe가 색칠한 칸 수)로 계산한다.

 

두 사람이 이상적으로 플레이할 때, (Alma는 점수를 최대화, Berthe는 점수를 최소화) 얻을 수 있는 최대 점수를 알아내야 한다.

 

\(s\)가 최대 6이므로 최대 36개의 방이 있고, 최대 \(3^{36}\)가지의 게임 상황이 존재한다고 생각할 수 있지만,

문제 조건에 의해 게임을 직접 해보면 나올 수 있는 상태의 가짓수가 그렇게 많지 않다는 사실을 알 수 있다.

(실제로 가장 큰 입력을 넣어도 가능한 게임판의 상태가 5만을 넘지 않는다.)

 

따라서 단순한 게임이라 생각하고 DP로 풀면 된다.

현재 판의 상태를 나타내는 방법은 여러가지가 있겠지만, 모든 상태를 정수로 예쁘게 치환하기는 조금 어려우니 뇌를 비우고 map을 이용한 DP로 해결하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int INF = 987654321;
const pii rp[36] =
{
    {1,1},
    {2,1},{2,2},{2,3},
    {3,1},{3,2},{3,3},{3,4},{3,5},
    {4,1},{4,2},{4,3},{4,4},{4,5},{4,6},{4,7},
    {5,1},{5,2},{5,3},{5,4},{5,5},{5,6},{5,7},{5,8},{5,9},
    {6,1},{6,2},{6,3},{6,4},{6,5},{6,6},{6,7},{6,8},{6,9},{6,10},{6,11}
};
 
int s, ra, pa, rb, pb;
set <pii> rst;
 
map <pair<pll, pii>, int> dp;
int solve(ll a, ll b, int wa, int wb)
{
    if (dp.count({ {a,b},{wa, wb} })) return dp[{ {a, b}, { wa, wb } }];
 
    vector <pii> n[2];
    pii c[2] = { rp[wa], rp[wb] };
 
    for (int k = 0; k < 2; k++)
    {
        if (c[k].second % 2 == 1)
        {
            int r, p, idx;
            r = c[k].first + 1;
            p = c[k].second + 1;
            idx = (r - 1) * (r - 1) + (p - 1);
 
            if (r <= s && rst.find({ r,p }) == rst.end()
                && (a & (1ll << idx)) == 0 && (b & (1ll << idx)) == 0)
            {
                n[k].push_back({ r,p });
            }
 
            r = c[k].first;
            p = c[k].second - 1;
            idx = (r - 1) * (r - 1) + (p - 1);
 
            if (p >= 1 && rst.find({ r,p }) == rst.end()
                && (a & (1ll << idx)) == 0 && (b & (1ll << idx)) == 0)
            {
                n[k].push_back({ r,p });
            }
 
            r = c[k].first;
            p = c[k].second + 1;
            idx = (r - 1) * (r - 1) + (p - 1);
 
            if (p < r * 2 && rst.find({ r,p }) == rst.end()
                && (a & (1ll << idx)) == 0 && (b & (1ll << idx)) == 0)
            {
                n[k].push_back({ r,p });
            }
        }
        else
        {
            int r, p, idx;
            r = c[k].first - 1;
            p = c[k].second - 1;
            idx = (r - 1) * (r - 1) + (p - 1);
 
            if (r >= 1 && rst.find({ r,p }) == rst.end()
                && (a & (1ll << idx)) == 0 && (b & (1ll << idx)) == 0)
            {
                n[k].push_back({ r,p });
            }
 
            r = c[k].first;
            p = c[k].second - 1;
            idx = (r - 1) * (r - 1) + (p - 1);
 
            if (p >= 1 && rst.find({ r,p }) == rst.end()
                && (a & (1ll << idx)) == 0 && (b & (1ll << idx)) == 0)
            {
                n[k].push_back({ r,p });
            }
 
            r = c[k].first;
            p = c[k].second + 1;
            idx = (r - 1) * (r - 1) + (p - 1);
 
            if (p < r * 2 && rst.find({ r,p }) == rst.end()
                && (a & (1ll << idx)) == 0 && (b & (1ll << idx)) == 0)
            {
                n[k].push_back({ r,p });
            }
        }
    }
 
    if (n[0].size() == 0 && n[1].size() == 0)
    {
        int sa = 0, sb = 0;
        for (int i = 0; i < s * s; i++)
        {
            if (a & (1ll << i)) sa++;
            if (b & (1ll << i)) sb++;
        }
 
        return dp[{ {a, b}, { wa, wb } }] = sa - sb;
    }
 
    int ret = -INF;
    if (n[0].size() && n[1].size())
    {
        for (auto na : n[0])
        {
            int idxa = (na.first - 1) * (na.first - 1) + (na.second - 1);
            int res = INF;
 
            if (n[1].size() == 1 && na == n[1].back())
            {
                int idxa = (na.first - 1) * (na.first - 1) + (na.second - 1);
                int res = solve(a | (1ll << idxa), b, idxa, wb);
 
                ret = max(ret, res);
                continue;
            }
 
            for (auto nb : n[1])
            {
                int idxb = (nb.first - 1) * (nb.first - 1) + (nb.second - 1);
                if (idxa == idxb) continue;
                int tmp = solve(a | (1ll << idxa), b | (1ll << idxb), idxa, idxb);
 
                res = min(res, tmp);
            }
 
            ret = max(ret, res);
        }
    }
    else if (n[0].size())
    {
        for (auto na : n[0])
        {
            int idxa = (na.first - 1) * (na.first - 1) + (na.second - 1);
            int res = solve(a | (1ll << idxa), b, idxa, wb);
 
            ret = max(ret, res);
        }
    }
    else if (n[1].size())
    {
        int res = INF;
 
        for (auto nb : n[1])
        {
            int idxb = (nb.first - 1) * (nb.first - 1) + (nb.second - 1);
            int tmp = solve(a, b | (1ll << idxb), wa, idxb);
 
            res = min(res, tmp);
        }
 
        ret = max(ret, res);
    }
 
    return dp[{ {a, b}, { wa, wb } }] = ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        dp.clear();
        rst.clear();
 
        cin >> s >> ra >> pa >> rb >> pb;
 
        int idxa = (ra - 1) * (ra - 1) + (pa - 1);
        int idxb = (rb - 1) * (rb - 1) + (pb - 1);
 
        int c; cin >> c;
        for (int i = 0; i < c; i++)
        {
            int r, p; cin >> r >> p;
            rst.insert({ r,p });
        }
 
        int ans = solve(1ll << idxa, 1ll << idxb, idxa, idxb);
 
        cout << "Case #" << tc << ": " << ans << '\n';
    }
}

---

Yeetzhee

Kick Start - Google’s Coding Competitions

\(n\)개의 주사위가 있다. 각 주사위는 \(1\)부터 \(m\)까지의 수가 적혀있고, 주사위를 던지면 각 수가 같은 확률로 나온다.

 

모든 주사위를 적어도 한번씩 던진다. 각 주사위는 원하는 만큼 다시 던질 수 있다.

주사위를 다 던졌다면, 같은 눈끼리 그룹으로 묶는다. 그리고 이 그룹들을 주사위의 개수가 작은 순으로 정렬하자.

이 작업 이후에 주사위 그룹의 수가 \(k\)개이며, 각 그룹에 포함된 주사위의 수가 정확히 \(a_i\)개가 되도록 하는 것이 목표이다.

 

이를 위해 주사위를 던지는 횟수에 대한 기대값을 알아내야 한다.

 

 

최적의 방법은 다음과 같다.

1. 주사위를 던진다.

2. 현재 상태에서 시작해도 목표를 만들 수 있다면, 다음 주사위로 넘어간다.

3. 그렇지 않다면, 다시 던진다.

 

작은 TC는 이를 완전탐색으로 구현하면 된다.

 

각 상태를 압축해보자.

주사위의 눈이 어떤 숫자인지는 전혀 중요하지 않음을 알 수 있다.

따라서 지금까지 던진 주사위의 상태를, 같은 숫자가 몇번씩 나왔는지에 대한 vector의 형태로 저장할 수 있다.

 

이 문제 역시 \(n\)과 \(m\)이 최대 50이라 많은 상태가 나올 것 같지만, 실제로 큰 테스트케이스를 만들어보면 가능한 상태의 수가 그렇게 많지 않음을 알 수 있다.

 

따라서 위를 각 상태 vector을 key로 가지는 map으로 저장하여 DP를 돌리면 문제를 해결할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m, k;
multiset<int> st;
 
map <vector<int>, double> dp;
double solve(vector<int>& v)
{
    if (dp.count(v)) return dp[v];
 
    int yes = 0;
    vector <double> res;
 
    for (int& i : v)
    {
        i++;
 
        bool flag = true;
        auto cst = st;
        for (int j : v)
        {
            auto it = cst.lower_bound(j);
            if (it == cst.end())
            {
                flag = false;
                break;
            }
 
            cst.erase(it);
        }
 
        if (flag)
        {
            yes++;
            vector <int> nv = v;
            sort(nv.begin(), nv.end());
 
            res.push_back(solve(nv));
        }
 
        i--;
    }
 
    int ac = 0;
    double ares = 0.0;
 
    if (v.size() + 1 <= k)
    {
        v.push_back(1);
 
        bool flag = true;
        auto cst = st;
        for (int j : v)
        {
            auto it = cst.lower_bound(j);
            if (it == cst.end())
            {
                flag = false;
                break;
            }
 
            cst.erase(it);
        }
 
        if (flag)
        {
            yes += m - (v.size() - 1);
            vector <int> nv = v;
            sort(nv.begin(), nv.end());
 
            ac = m - (v.size() - 1);
            ares = solve(nv);
        }
 
        v.pop_back();
    }
 
    if (yes == 0) return 0;
 
    double ans = (double)m / yes;
    double tmp = 0.0;
    for (double x : res) tmp += x;
    tmp += ares * ac;
 
    tmp /= yes;
 
    ans += tmp;
    return dp[v] = ans;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        st.clear();
        dp.clear();
 
        cin >> n >> m >> k;
        for (int i = 0; i < k; i++)
        {
            int a; cin >> a;
            st.insert(a);
        }
 
        vector <int> tmp;
        double ans = solve(tmp);
 
        cout.precision(6);
        cout << fixed << "Case #" << tc << ": " << ans << '\n';
    }
}