Round A 2021 - Kick Start 2021

K-Goodness String

Kick Start - Google’s Coding Competitions

\(n\)길이의 문자열 \(s\)가 주어진다.

이 문자열의 점수를 \(s_i \ne s_{n-i+1}\)를 만족하는 \(i\)의 개수라고 하자. (\(1 \le i \le n/2\))

문자열의 점수를 \(k\)로 만들기 위해, 바꿔야 하는 문자의 최소 개수를 구해야 한다.

 

 

주어지는 문자열의 원래 점수가 \(ck\)라고 하면, \(|ck-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; }
 
int n, k;
string s;
 
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;
        cin >> s;
 
        int ck = 0;
        for (int i = 0; i < n / 2; i++)
            if (s[i] != s[n - 1 - i]) ck++;
 
        int res = k - ck;
        if (res < 0) res = -res;
 
        cout << "Case #" << tc << ": " << res << '\n';
    }
}

---

L Shaped Plots

Kick Start - Google’s Coding Competitions

\(r \times c\)크기의 격자가 있다.

격자의 값은 0또는 1이다.

 

이 격자에서 문제에서 말하는 "L-모양"이 몇개 있는지 알아내야 한다.

 

각각의 칸에서 시작해서, 왼쪽/오른쪽/위쪽/아래쪽으로 최대 몇 칸까지 연결되어 있는지 간단한 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 N = 1005;
 
int r, c;
int board[N][N];
 
ll psum_r[N][N];
ll psum_l[N][N];
ll psum_d[N][N];
ll psum_u[N][N];
 
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 >> r >> c;
        for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++)
            cin >> board[i][j];
 
        for (int i = 0; i <= r + 1; i++) for (int j = 1; j <= c + 1; j++)
        {
            psum_r[i][j] = 0;
            psum_l[i][j] = 0;
            psum_d[i][j] = 0;
            psum_u[i][j] = 0;
        }
 
        for (int i = 1; i <= r; i++)
        {
            for (int j = 1; j <= c; j++)
            {
                if (board[i][j] == 0) continue;
                psum_l[i][j] = psum_l[i][j - 1] + 1;
            }
 
            for (int j = c; j >= 1; j--)
            {
                if (board[i][j] == 0) continue;
                psum_r[i][j] = psum_r[i][j + 1] + 1;
            }
        }
 
        for (int j = 1; j <= c; j++)
        {
            for (int i = 1; i <= r; i++)
            {
                if (board[i][j] == 0) continue;
                psum_u[i][j] = psum_u[i - 1][j] + 1;
            }
 
            for (int i = r; i >= 1; i--)
            {
                if (board[i][j] == 0) continue;
                psum_d[i][j] = psum_d[i + 1][j] + 1;
            }
        }
 
        ll ans = 0;
        for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++)
        {
            if (psum_l[i][j] >= 4)
            {
                ll r1 = min(psum_l[i][j] / 2 - 1, max(0ll, psum_u[i][j] - 1));
                ll r2 = min(psum_l[i][j] / 2 - 1, max(0ll, psum_d[i][j] - 1));
 
                ans += r1;
                ans += r2;
            }
 
            if (psum_r[i][j] >= 4)
            {
                ll r1 = min(psum_r[i][j] / 2 - 1, max(0ll, psum_u[i][j] - 1));
                ll r2 = min(psum_r[i][j] / 2 - 1, max(0ll, psum_d[i][j] - 1));
 
                ans += r1;
                ans += r2;
            }
 
            if (psum_u[i][j] >= 4)
            {
                ll r1 = min(psum_u[i][j] / 2 - 1, max(0ll, psum_l[i][j] - 1));
                ll r2 = min(psum_u[i][j] / 2 - 1, max(0ll, psum_r[i][j] - 1));
 
                ans += r1;
                ans += r2;
            }
 
            if (psum_d[i][j] >= 4)
            {
                ll r1 = min(psum_d[i][j] / 2 - 1, max(0ll, psum_l[i][j] - 1));
                ll r2 = min(psum_d[i][j] / 2 - 1, max(0ll, psum_r[i][j] - 1));
 
                ans += r1;
                ans += r2;
            }
        }
 
        cout << "Case #" << tc << ": " << ans << '\n';
    }
}

---

Rabbit House

Kick Start - Google’s Coding Competitions

\(r \times c\)크기의 격자가 있다. 각 격자의 초기 높이가 주어진다.

인접한 격자의 높이 차이가 1보다 작거나 같도록 하기 위해, 각 격자에서 추가로 높여야 하는 높이의 합의 최소값을 구해야 한다.

 

가장 높은 칸에 대해 생각해보자. 이 칸의 높이는 \(h\)이다.

먼저, 이 칸을 추가로 높일 필요는 없다는 사실을 알 수 있다.

그리고 가장 높은 칸과 인접한 칸들은, 적어도 \(h-1\)의 높이를 가져야 함을 알 수 있다.

만약 이보다 높이가 낮다면, 높이를 \(h-1\)로 바꿔준다.

 

그리고 남은 칸들 중에서 가장 높은 칸을 찾아, 이를 반복하면 된다.

set이나 priority queue등의 자료구조를 이용하면 \(O(rc\log rc)\)에 이를 해결할 수 있다.

 

#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 r, c;
ll g[301][301];
ll res[301][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++)
    {
        priority_queue<pair<ll, pii> > pq;
 
        cin >> r >> c;
        for (int i = 0; i < r; i++) for (int j = 0; j < c; j++)
        {
            cin >> g[i][j];
            res[i][j] = g[i][j];
 
            pq.push({ g[i][j], {i, j} });
        }
 
        ll ans = 0;
 
        while (!pq.empty())
        {
            auto it = pq.top(); pq.pop();
            ll v = it.first;
            int x = it.second.first, y = it.second.second;
 
            if (res[x][y] > v) continue;
 
            for (int k = 0; k < 4; k++)
            {
                int nx = x + "0121"[k] - '1';
                int ny = y + "1012"[k] - '1';
 
                if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                if (res[nx][ny] >= v - 1) continue;
 
                ans += v - 1 - res[nx][ny];
                res[nx][ny] = v - 1;
 
                pq.push({ v - 1,{nx, ny} });
            }
        }
 
        cout << "Case #" << tc << ": " << ans << '\n';
    }
}

---

Checksum

Kick Start - Google’s Coding Competitions

\(n \times n\)크기의 이진 행렬 \(a\)가 있다.

이 행렬이 바이러스로 인해 손상되어서, 일부 원소가 원래 무엇이었는지 알 수 없게 되었다.

다행히도 각 행과 각 열에 있는 원소들의 XOR값을 저장해 두었기 때문에, 이를 이용해 어느정도 복원이 가능하다.

또, 이를 이용해서도 복원이 불가능하다면, \(b_{i, j}\)의 비용으로 임의의 칸을 복원할 수도 있다.

 

행렬을 모두 복원하는데 필요한 최소 비용을 구해야 한다.

 

 

먼저, 단순히 복원 가능 여부를 알기 위해서는 XOR값은 전혀 쓸모 없다는 사실을 알 수 있다.

각 열과 행 자체를 정점으로 하고, \(a_{i, j}\)가 훼손되었다면 \(i\)번째 열과 \(j\)번째 행을 잇는 간선으로 하는 그래프를 생각해보자.

 

임의의 칸 복원 없이 행렬이 복원될 수 있으려면, 이 그래프에 사이클이 없어야 된다는 사실을 알 수 있다.

 

각 간선의 가중치를 \(B_{i, j}\)로 설정하자.

최소한의 간선을 제거하여 사이클이 없도록 만들기 위해서는, 남은 간선들이 Maximum Spanning Forest가 되어야 한다는 사실을 알 수 있다.

 

#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 a[501][501];
int b[501][501];
int r[501];
int c[501];
 
int par[1001];
int getPar(int x)
{
    if (par[x] == x) return x;
    return par[x] = getPar(par[x]);
}
bool merge(int a, int b)
{
    a = getPar(a), b = getPar(b);
    if (a == b) return false;
    par[a] = b;
    return true;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    for (int tc = 1; tc <= t; tc++)
    {
        vector<pair<ll, pii> > v;
 
        ll ans = 0;
 
        cin >> n;
        for (int i = 0; i < n + n; i++) par[i] = i;
 
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
            cin >> a[i][j];
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
            cin >> b[i][j], ans += b[i][j];
        for (int i = 0; i < n; i++) cin >> r[i];
        for (int i = 0; i < n; i++) cin >> c[i];
 
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        {
            if (a[i][j] != -1) continue;
            v.push_back({ b[i][j], {i, j + n} });
        }
 
        sort(v.rbegin(), v.rend());
        for (auto it : v)
        {
            ll w = it.first;
            int i = it.second.first, j = it.second.second;
 
            if (merge(i, j)) ans -= w;
        }
 
        cout << "Case #" << tc << ": " << ans << '\n';
    }
}