Google Kick Start - Round E 2020

아깝다

Longest Arithmetic

Kick Start - Google’s Coding Competitions

어떤 배열이 2개 이상의 원소를 가지고, 인접한 두 원소의 차이가 모두 같다면, 이 배열을 arithmetic array라고 한다.

 

\(n\)길이의 배열이 주어지고, 이 배열의 부분 배열중 arithmetic array인 것들 중에 가장 긴것의 길이를 알아내야 한다.

 

 

단순 구현문제이다. 하라는대로 하면 된다.

 

#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;
ll a[200001];
 
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;
        for (int i = 0; i < n; i++) cin >> a[i];
 
        int ans = 0;
        int cnt = 1;
        ll cd = a[1] - a[0];
        for (int i = 2; i < n; i++)
        {
            if (a[i] - a[i - 1] == cd) cnt++;
            else
            {
                ans = max(ans, cnt);
                cnt = 1;
                cd = a[i] - a[i - 1];
            }
        }
 
        ans = max(ans, cnt);
 
        cout << "Case #" << tc << ": " << ans + 1 << '\n';
    }
}

---

High Buildings

Kick Start - Google’s Coding Competitions

\(n\)개의 빌딩이 일직선으로 서있다.

가장 왼쪽에 서 있는 빌딩의 왼쪽에서 이 빌딩들을 바라봤을 때 \(a\)채의 빌딩이 보였고,

가장 오른쪽에 서 있는 빌딩의 오른쪽에서 이 빌딩들을 바라봤을 때 \(b\)채의 빌딩이 보였다.

또, 어느쪽에서 보든 상관없이 보이는 빌딩의 수는 \(c\)채이다.

 

어떤 빌딩이 보이기 위에서는, 내 시야와 그 빌딩사이에 더 높은 빌딩이 없어야 한다.

빌딩의 높이가 1이상 \(n\)이하의 정수라고 할 때, 이 정보를 토대로 가능한 빌딩 높이를 하나 알아내야 한다.

또는, 불가능함을 알아내야 한다.

 

우선 가운데 \(c\)채의 빌딩을 \(n\)높이로 놓자.

그리고 그 왼쪽으로 \(a-c\)채의 빌딩을 높이를 1씩 줄여가면서 놓고,

오른쪽으로 \(b-c\)채의 빌딩을 높이를 1씩 줄여가면서 놓자.

 

총 빌딩이 아직 \(n\)채가 안됬다면, 높이가 1인 빌딩을 적당히 중간에 껴놓으면 된다.

도중에 불가능한 경우가 생기면, 조건을 만족하는 경우도 없다.

 

#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, a, b, c;
vector <int> 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++)
    {
        cin >> n >> a >> b >> c;
 
        cout << "Case #" << tc << ": ";
 
        if (a + b - c > n)
        {
            cout << "IMPOSSIBLE\n";
            continue;
        }
 
        ans.clear();
 
        for (int i = 0; i < a - c; i++) ans.push_back(n - (a - c) + i);
        for (int i = 0; i < c; i++) ans.push_back(n);
        for (int i = 0; i < b - c; i++) ans.push_back(n - 1 - i);
 
        int tmp = -1;
        for (int i = 1; i < ans.size(); i++)
        {
            bool f1 = false, f2 = false;
            for (int j = 0; j < i; j++)
            {
                if (ans[j] > 1) f1 = true;
            }
 
            for (int j = i; j < ans.size(); j++)
            {
                if (ans[j] > 1) f2 = true;
            }
 
            if (f1 && f2)
            {
                tmp = i;
                break;
            }
        }
 
        if (tmp == -1 && n - (a + b - c) > 0)
        {
            cout << "IMPOSSIBLE\n";
            continue;
        }
 
        for (int i = 0; i < ans.size(); i++)
        {
            if (i == tmp)
            {
                for (int i = 0; i < n - (a + b - c); i++) cout << "1 ";
            }
            cout << ans[i] << ' ';
        }
 
        cout << '\n';
    }
}

---

Toys

Kick Start - Google’s Coding Competitions

아기가 \(n\)개의 장난감을 가지고 놀려고 한다.

장난감은 원형으로 늘어서 있고, 1번 장난감부터 가지고 놀기 시작해서 시계방향으로 있는 장난감을 차례로 가지고 놀게 된다.

\(i\)번 장난감을 가지고 놀면, \(e_i\) 시간동안 가지고 논다.

다 논 다음에는, 그 장난감에 대해 \(r_i\) 시간동안 기억한다.

 

만약 어떤 장난감에 대한 기억이 아직 남아있는 상태에서 그 장난감에 도착하게 되면, 놀기를 그만둔다.

장난감에 대한 정보가 주어지면, 장난감을 최대한 적게 제거해서 아기가 놀 수 있는 시간의 최대 길이를 알아내야 한다.

 

 

우선 장난감의 정보와 관계없이, 일단 모든 장난감을 한번씩 가지고 놀게 된다.

 

현재 남아있는 장난감의 모든 \(e_i\)의 합을 \(sum\)이라고 하자.

\(i\)번 장난감에 대해, \(sum - e_i - r_i\)가 0보다 작다면 그 장난감을 2번째로 봤을 때 놀기를 그만두게 된다.

만약 현재 그런 장난감이 여러 가지라면, 번호가 가장 작은 장난감에서 놀기를 그만둘 것이다.

 

따라서 현재 상황에 대해 아기가 놀 수 있는 최대 시간을 계산하고, 아기가 놀기 그만두는 장난감을 제거하는 것을 반복하면 된다.

만약 도중에 \(sum - e_i - r_i\)가 0보다 작은 경우가 없다면 무한히 놀 수 있게 되고,

그런 경우가 없다면 지금까지 계산한 최대 시간 중 최대값을 찾으면 된다.

 

구현은 Priority Queue나 Segment Tree등등으로 할 수 있다.

 

 

#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;
ll e[100001];
ll r[100001];
 
ll segTree[100001];
void update(int i, ll v)
{
    while (i <= n)
    {
        segTree[i] += v;
        i += i & -i;
    }
}
ll getVal(int i)
{
    ll res = 0;
    while (i)
    {
        res += segTree[i];
        i -= i & -i;
    }
    return res;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        ll sum = 0;
        memset(segTree, 0, sizeof segTree);
 
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> e[i] >> r[i];
            update(i, e[i]);
            sum += e[i];
        }
 
        priority_queue<pll> pq;
        for (int i = 1; i <= n; i++)
        {
            pq.push({ r[i] + e[i], i });
        }
 
        priority_queue<int> ni;
        while (!pq.empty())
        {
            ll x = pq.top().first;
            int idx = pq.top().second;
 
            if (sum - x < 0)
            {
                pq.pop();
                ni.push(-idx);
            }
            else break;
        }
 
        ll mxLen = 0;
        int mxCnt = 0;
 
        int cnt = 0;
        while (!ni.empty())
        {
            int idx = -ni.top(); ni.pop();
 
            ll curLen = sum + getVal(idx - 1);
            if (mxLen < curLen)
            {
                mxLen = curLen;
                mxCnt = cnt;
            }
 
            cnt++;
            sum -= e[idx];
            update(idx, -e[idx]);
            while (!pq.empty())
            {
                ll x = pq.top().first;
                int idx = pq.top().second;
 
                if (sum - x < 0)
                {
                    pq.pop();
                    ni.push(-idx);
                }
                else break;
            }
        }
 
        if (pq.size() > 1)
        {
            cout << "Case #" << tc << ": " << cnt << " INDEFINITELY\n";
            continue;
        }
 
        cout << "Case #" << tc << ": " << mxCnt << ' ' << mxLen << '\n';
    }
}

---

Golden Stone

Kick Start - Google’s Coding Competitions

\(n\)개의 정점과 \(m\)개의 간선으로 이루어져 있는 그래프가 있다.

\(s\)개의 원소가 있고, 그래프의 각 정점에는 어떤 원소(들)를 무한히 얻을 수 있는 광산이 있거나, 없다.

\(r\)개의 레시피가 주어진다. 각 레시피는 최대 3개의 원소를 조합해 다른 어떤 원소를 만들 수 있다는 정보를 가지고 있다.

레시피대로 원소를 조합하기 위해서는, 각 원소들이 같은 장소에 있어야 한다.

하나의 원소를 어떤 정점에서 간선으로 이어진 다른 정점으로 옮기는데 1의 에너지가 든다.

 

1번 원소를 제작하기 위해, 사용해야 하는 에너지의 최소값을 구해야 한다.

만약 에너지가 \(10^{12}\)이상 필요하다면 대신 -1을 출력한다.

 

 

정점이 \((k, v)\)의 순서쌍인 그래프를 생각해보자.

각 정점까지의 거리는 \(v\)번 정점에 \(k\)번 원소를 가져오기 위한 (또는 제작하기 위한) 최소 에너지를 나타낸다.

 

광산이 있는 정점들에 대해, 그 원소를 만드는데 필요한 에너지가 0이라고 생각하고, 다익스트라를 이용해 최단거리를 계산해보자.

 

어떤 정점 \((k, v)\)를 보고 있다면 다음 정점들에 대해 완화를 시도할 수 있다.

\((k, u)\): 원래 그래프의 정점 \((u, v)\)사이에 간선이 존재한다면, (\((k,v)\)까지의 거리 + 1)로 완화를 시도할 수 있다.

\((l, v)\): \(k\)번 원소가 \(l\)번 원소를 만드는 레시피에 필요한 원소라면, \(v\)번 정점에서 해당 레시피를 이용해 \(l\)번 원소를 만드는데 필요한 에너지로 완화를 시도할 수 있다.

 

최단거리를 모두 갱신했다면, 1번 원소를 각 정점에서 제작했을 때 필요한 에너지의 최소값을 알 수 있으므로, 이 중 최소값을 구하면 된다.

 

 

#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 ll INF = 1e12;
 
int n, m, s, r;
vector <int> graph[301];
ll dist[301][301];
 
vector <pair<vector<int>, int> > rcp;
vector <int> ing[301];
 
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 >> m >> s >> r;
        for (int i = 1; i <= n; i++) graph[i].clear();
        fill(&dist[0][0], (&dist[n][n]) + 1, INF);
        rcp.clear();
        for (int i = 1; i <= s; i++) ing[i].clear();
 
        for (int i = 0; i < m; i++)
        {
            int u, v; cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
 
        priority_queue<pair<ll, pii> > pq;
        for (int v = 1; v <= n; v++)
        {
            int c; cin >> c;
            for (int j = 0; j < c; j++)
            {
                int k; cin >> k;
                dist[k][v] = 0;
                pq.push({ 0, {k, v} });
            }
        }
 
        for (int i = 0; i < r; i++)
        {
            int c; cin >> c;
            vector <int> tmp;
            for (int j = 0; j < c; j++)
            {
                int k; cin >> k;
                tmp.push_back(k);
                ing[k].push_back(i);
            }
 
            int rs; cin >> rs;
            rcp.push_back({ tmp, rs });
        }
 
        while (!pq.empty())
        {
            ll cd = -pq.top().first;
            int k = pq.top().second.first;
            int v = pq.top().second.second;
            pq.pop();
 
            if (dist[k][v] < cd) continue;
 
            for (int nv : graph[v])
            {
                if (dist[k][nv] > cd + 1)
                {
                    dist[k][nv] = cd + 1;
                    pq.push({ -dist[k][nv], {k, nv} });
                }
            }
 
            for (int idx : ing[k])
            {
                vector <int>& ci = rcp[idx].first;
                int res = rcp[idx].second;
 
                ll rd = 0;
                for (int nk : ci)
                {
                    rd += dist[nk][v];
                }
 
                if (dist[res][v] > rd)
                {
                    dist[res][v] = rd;
                    pq.push({ -dist[res][v], {res, v} });
                }
            }
        }
 
        ll res = *min_element(&dist[1][1], (&dist[1][n]) + 1);
        if (res == INF) res = -1;
 
        cout << "Case #" << tc << ": " << res << '\n';
    }
}