Google Kick Start - Round D 2020

아깝다

Record Breaker

Kick Start - Google’s Coding Competitions

\(N\)개의 수로 이루어진 배열 \(V\)가 주어진다.

각 원소 \(V_i\)에 대해, 모든 \(j < i\)에 대해 \(V_j < V_i\)이고, \(V_i > V_{i+1}\)또는 \(i = N\)을 만족하는 원소의 수를 구해야 한다.

 

하라는대로 구현하면 된다.

 

#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;
int v[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    for (int t = 1; t <= T; t++)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> v[i];
 
        int mx = -1;
        int ans = 0;
 
        for (int i = 0; i < n; i++)
        {
            if (v[i] > mx && (i == n - 1 || v[i] > v[i + 1])) ans++;
            mx = max(mx, v[i]);
        }
 
        cout << "Case #" << t << ": " << ans << '\n';
    }
}

---

Alien Piano

Kick Start - Google’s Coding Competitions

건반이 4개밖에 없는 피아노가 있다.

이 피아노를 이용해 곡을 연주하려고 한다.

곡의 맨 첫음은 4개 중 아무거나로 시작하되, 그 이후 음들은 이전 음보다 높으면 피아노에서도 높은 건반을, 낮으면 피아노에서도 낮은 건반을 눌러야 한다 (간격은 상관없다). 같은 음이면 같은 건반을 눌러야 한다.

 

연주해야 하는 곡의 음높이들이 주어지는데, 건반이 4개뿐이기 때문에 중간중간에 규칙에 맞지 않게 쳐야 할 수도 있다.

규칙에 맞지 않게 치는 횟수의 최소값을 알아내야 한다.

 

DP식을 다음과 같이 정의하자.

\(DP(i, j)\) : \(i\)번째 음을 \(j\)번째 건반으로 눌렀을 때, 이 이후 규칙에 맞지 않게 치는 횟수의 최소값

총 \(4k\)개의 상태가 있고, 각 상태를 계산하는데 4개의 부분 문제를 풀어야 하므로, \(O(16k)\)의 시간복잡도로 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 k;
int a[10001];
int dp[10001][4];
 
int solve(int idx, int key)
{
    int& ret = dp[idx][key];
    if (ret != -1) return ret;
    if (idx == k - 1) return ret = 0;
 
    ret = 987654321;
    
    for (int i = 0; i < 4; i++)
    {
        int res;
        if (key < i && a[idx] < a[idx + 1]
            || key == i && a[idx] == a[idx + 1]
            || key > i && a[idx] > a[idx + 1]) res = solve(idx + 1, i);
 
        else res = solve(idx + 1, i) + 1;
        ret = min(ret, res);
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    for (int t = 1; t <= T; t++)
    {
        cin >> k;
        for (int i = 0; i < k; i++) cin >> a[i];
 
        memset(dp, -1, sizeof dp);
 
        int ans = 987654321;
        for (int i = 0; i < 4; i++)
        {
            int res = solve(0, i);
            ans = min(ans, res);
        }
 
        cout << "Case #" << t << ": " << ans << '\n';
    }
}

---

Beauty of tree

Kick Start - Google’s Coding Competitions

\(N\)개의 노드로 이루어진 트리가 주어진다. 1번 노드는 트리의 루트다.

 

두 사람이 다음과 같은 방식으로 트리를 칠한다.

첫번째 사람은 무작위로 노드 하나를 골라 칠한 다음, 루트까지의 경로를 따라 올라가면서 각 \(A\)번째 노드를 칠한다.

두번째 사람은 무작위로 노드 하나를 골라 칠한 다음, 루트까지의 경로를 따라 올라가면서 각 \(B\)번째 노드를 칠한다.

 

이 때, 칠해진 노드의 개수의 기대값이 얼마인지 알아내야 한다.

 

Test set 1은 모든 경우를 시뮬레이션으로 해보면 된다.

 

노드가 겹쳐져서 칠해지는 경우를 생각하지 않고, 모든 경우에 대해 칠해지는 노드 개수를 구하자.

노드의 깊이가 \(l\)이고, 첫번째 사람이 이 노드부터 시작해 칠한다면,

\(\lfloor \frac lA \rfloor + 1\)개의 노드가 칠해질 것이다. (루트까지의 깊이는 0이다.)

 

다음으로, 각각의 노드에 대해 겹쳐져 칠해지는 경우가 몇가지인지 계산해보자.

어떤 노드가 겹쳐져 칠해지는 경우의 수는,

(이 노드에서 자식방향으로 \(A\)의 배수만큼 떨어진 자식의 수) \(\times\) (이 노드에서 자식방향으로 \(B\)의 배수만큼 떨어진 자식의 수) 이다.

 

스파스 테이블을 이용해 각 노드의 \(A\)번째, \(B\)번째 부모를 계산할 수 있으므로, 거리가 \(A\), \(B\)떨어진 포레스트를 만들 수 있다.

각 포레스트의 각 노드에 대해 DFS등으로 자식의 수를 구하면 위의 식을 계산할 수 있다.

 

#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 N = 500001;
int n, a, b;
int spt[20][N];
vector <int> graph[N];
int lv[N];
 
ll ans = 0;
void DFS(int v, int l)
{
    ans += l / a + 1;
    ans += l / b + 1;
 
    lv[v] = l;
    for (int nv : graph[v]) DFS(nv, l + 1);
}
 
vector <int> graphA[N], graphB[N];
int cacheA[N], cacheB[N];
ll szA[N], szB[N];
 
void DFS2(vector <int>* graph, int* cache, ll* sz, int v)
{
    cache[v] = 1;
    sz[v] = 1;
 
    for (int nv : graph[v])
    {
        DFS2(graph, cache, sz, nv);
        sz[v] += sz[nv];
    }
}
 
void DFS1(int v)
{
    if (!cacheA[v]) DFS2(graphA, cacheA, szA, v);
    if (!cacheB[v]) DFS2(graphB, cacheB, szB, v);
 
    for (int nv : graph[v]) DFS1(nv);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    for (int t = 1; t <= T; t++)
    {
        cin >> n >> a >> b;
        for (int i = 1; i <= n; i++)
        {
            graph[i].clear();
            graphA[i].clear();
            graphB[i].clear();
        }
 
        for (int i = 2; i <= n; i++)
        {
            int p; cin >> p;
            spt[0][i] = p;
            graph[p].push_back(i);
        }
 
        ans = 0;
        DFS(1, 0);
 
        for (int i = 1; i < 20; i++)
        {
            for (int v = 1; v <= n; v++)
                spt[i][v] = spt[i - 1][spt[i - 1][v]];
        }
 
        for (int v = 1; v <= n; v++)
        {
            int pa = v, pb = v;
            for (int i = 0; i < 20; i++)
            {
                if (a & (1 << i)) pa = spt[i][pa];
                if (b & (1 << i)) pb = spt[i][pb];
            }
 
            if (pa) graphA[pa].push_back(v);
            if (pb) graphB[pb].push_back(v);
        }
 
        memset(cacheA, 0, sizeof cacheA);
        memset(cacheB, 0, sizeof cacheB);
        memset(szA, 0, sizeof szA);
        memset(szB, 0, sizeof szB);
 
        DFS1(1);
 
        ans *= n;
        for (int v = 1; v <= n; v++)
        {
            ll res = szA[v] * szB[v];
            ans -= res;
        }
 
        cout.precision(6);
        cout << fixed << "Case #" << t << ": " << (double)ans / n / n << '\n';
    }
}

---

Locked Doors

Kick Start - Google’s Coding Competitions

\(N\)개의 방이 있고, 각 방 사이에 \(N-1\)개의 문이 있다.

각각의 문을 여는데의 난이도는 \(D_i\)이다.

 

현재 열 수 있는 문이 좌우로 2개라면, 둘 중 쉬운 난이도의 문을 연다.

1개밖에 없다면, 그 문을 연다. 한번 연 문은 다시 열지 않는다.

 

\(Q\)개의 쿼리가 주어진다. 각 쿼리에 대해, \(S, K\)가 주어지면, \(S\)번째 방에서 위의 규칙으로 문을 열며 이동했을 때 \(K\)번째로 도착하게 되는 방의 번호를 구해야 한다.

 

Test Set 1은 시뮬레이션으로 직접 열어보면 된다.

 

\(i\)번 문을 열었다고 생각해보자. \(D_i\)보다 높은 난이도의 문을 열기 위해서는 그 전에 열 수 있는 \(D_i\)보다 낮은 난이도의 문을 모두 열어야 한다.

 

이를 트리 형태로 나타내보자.

\(i\)번째 문을 연 다음, \(D_i\)보다 높은 난이도의 문 중 가장 빨리 열어야 하는 문을 \(j\)번 문이라고 하자.

그러면 \(i\)는 \(j\)의 자식이다.

 

그러면 \(i\)번 문을 열고 나서 \(j\)번 문을 열기 위해서는, 그 전에 \(i\)의 서브트리에 해당되는 문을 모두 열고 나야 가능하다고 생각할 수 있다.

 

각 쿼리에 대해, \(S, K\)가 주어지면 맨 처음 열어야 되는 문이 뭔지 알 수 있다. 이 문을 \(f\)라고 하자.

만약 \(K\)가 \(f\)를 루트로 하는 서브트리의 크기보다 작거나 같다면, 처음 연 문 방향으로 \(K\)회 이동하면 된다.

 

그렇지 않다면, 서브트리의 크기가 \(K\)보다 크거나 같은 부모 중 가장 가까운 노드로 이동해 위와 같이 행동하면 된다.

서브트리의 크기가 \(K\)보다 크거나 같은 부모 중 가장 가까운 노드는, 스파스 테이블을 미리 만들어 놓음으로써 \(O(logN)\)의 시간 복잡도로 구할 수 있다.

 

#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 N = 100001;
const int INF = 987654321;
 
int n, q;
int d[N];
int idx[N];
int lpar[N], rpar[N];
 
int spt[20][N];
int child[N][2];
 
int sz[N];
void DFS(int v)
{
    sz[v] = 1;
    if (child[v][0] != -1)
    {
        DFS(child[v][0]);
        sz[v] += sz[child[v][0]];
    }
    if (child[v][1] != -1)
    {
        DFS(child[v][1]);
        sz[v] += sz[child[v][1]];
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    for (int t = 1; t <= T; t++)
    {
        cin >> n >> q;
        memset(child, -1, sizeof child);
        memset(spt, 0, sizeof spt);
 
        d[0] = d[n] = INF;
        for (int i = 1; i < n; i++)
        {
            cin >> d[i];
            idx[d[i]] = i;
        }
 
        vector <int> stk;
        for (int i = 1; i <= n; i++)
        {
            while (!stk.empty() && stk.back() < d[i]) stk.pop_back();
            if (stk.empty()) lpar[i] = INF;
            else lpar[i] = stk.back();
 
            stk.push_back(d[i]);
        }
 
        stk.clear();
        for (int i = n; i >= 1; i--)
        {
            while (!stk.empty() && stk.back() < d[i]) stk.pop_back();
            if (stk.empty()) rpar[i] = INF;
            else rpar[i] = stk.back();
 
            stk.push_back(d[i]);
        }
 
        int rt = -1;
 
        for (int i = 1; i < n; i++)
        {
            int par = min(lpar[i], rpar[i]);
            if (par == INF)
            {
                rt = i;
                continue;
            }
 
            par = idx[par];
            spt[0][i] = par;
            if (i < par) child[par][0] = i;
            else child[par][1] = i;
        }
 
        for (int i = 1; i < 20; i++)
        {
            for (int j = 1; j <= n; j++)
                spt[i][j] = spt[i - 1][spt[i - 1][j]];
        }
 
        DFS(rt);
 
        vector <int> ans;
        while (q--)
        {
            int s, k; cin >> s >> k; k--;
 
            int fdoor = -1;
            if (d[s - 1] < d[s]) fdoor = s - 1;
            else fdoor = s;
 
            if (sz[fdoor] >= k)
            {
                if (fdoor == s - 1) ans.push_back(s - k);
                else ans.push_back(s + k);
                continue;
            }
 
            int c = fdoor;
            for (int i = 19; i >= 0; i--)
            {
                if (spt[i][c] == 0) continue;
                if (sz[spt[i][c]] < k)
                {
                    c = spt[i][c];
                }
            }
 
            c = spt[0][c];
            if (s <= c)
                ans.push_back(c + k - sz[child[c][0]]);
            else
                ans.push_back(c + 1 - (k - sz[child[c][1]]));
        }
 
        cout << "Case #" << t << ":";
        for (int i : ans) cout << ' ' << i;
        cout << '\n';
    }
}