Editorial

Kickstart 2021 Round A 개인 풀이

대회 참가 후기 및 개인 풀이

A. K-Goodness String

문자열 절반을 기준으로 서로 대칭이 아닌 쌍의 개수를 정확히 $K$개로 만들기 위해 최소 몇 개의 문자를 바꿔야하는지 출력하는 문제다.

현재 문자열에서 대칭이 아닌 쌍의 개수를 구하고, $K$와 얼마나 차이나는지 출력했다.

배열 크기를 잘못잡아서 한 번 틀렸다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define size(v) ((int)v.size())
#define all(v) (v).begin(),(v).end()
using lint = long long;
using fint = long double;
const lint INF = 1e9 + 9;

int n, k;
char s[200001];

int solve(){
    int cnt = 0;
    for(int i=0;i<n/2;++i)
        if(s[i] != s[n-1-i])
            cnt++;
    return abs(cnt - k);
}

int main(){
    int tc=1; scanf("%d",&tc);
    for(int tt=1;tt<=tc;++tt){
        scanf("%d%d%s",&n,&k,s);

        int ans = solve();
        printf("Case #%d: %d\n",tt,ans);
    }
}

B. L Shaped Plots

$0$과 $1$로 이뤄진 $R \times C$ 그리드에서 L자 모양이 몇 개인지 구하는 문제다. L자는 두 선분이 끝 점에서 수직으로 만나는 형태를 말한다. 한 선분 길이는 다른 선분 길이의 두 배여야 하며, 각 선분의 길이는 $2$ 이상이어야 한다.

각 위치에 대해 상하좌우에 몇 개의 $1$이 연속으로 있는지 전처리했다. L자가 가능한 $8$가지 모양에 대해 모두 처리했다.

반복문 범위를 잘못 정해줘서 두 번 틀렸다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
#define size(v) ((int)v.size())
#define all(v) (v).begin(),(v).end()
using lint = long long;
using fint = long double;
const lint INF = 1e9 + 9;

int n, m, a[1002][1002];

int u[1002][1002], d[1002][1002];
int l[1002][1002], r[1002][1002];

int solve(){
    for(int i=0;i<=n+1;++i)
        for(int j=0;j<=m+1;++j)
            l[i][j] = r[i][j] = u[i][j] = d[i][j] = 0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(a[i][j]) l[i][j] = l[i][j-1]+1;
            else l[i][j] = 0;
        }
        for(int j=m;j;--j){
            if(a[i][j]) r[i][j] = r[i][j+1]+1;
            else r[i][j] = 0;
        }
    }
    for(int j=1;j<=m;++j){
        for(int i=1;i<=n;++i){
            if(a[i][j]) u[i][j] = u[i-1][j]+1;
            else u[i][j] = 0;
        }
        for(int i=n;i;--i){
            if(a[i][j]) d[i][j] = d[i+1][j]+1;
            else d[i][j] = 0;
        }    
    }
    int ans = 0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            int v = min(u[i][j], l[i][j]/2);
            if(v>1) ans += v-1;
            v = min(u[i][j]/2, l[i][j]);
            if(v>1) ans += v-1;
            v = min(u[i][j], r[i][j]/2);
            if(v>1) ans += v-1;
            v = min(u[i][j]/2, r[i][j]);
            if(v>1) ans += v-1;
            v = min(d[i][j], r[i][j]/2);
            if(v>1) ans += v-1;
            v = min(d[i][j]/2, r[i][j]);
            if(v>1) ans += v-1;
            v = min(d[i][j], l[i][j]/2);
            if(v>1) ans += v-1;
            v = min(d[i][j]/2, l[i][j]);
            if(v>1) ans += v-1;
        }
    }
    return ans;
}

int main(){
    int tc; scanf("%d",&tc);
    for(int tt=1;tt<=tc;++tt){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                scanf("%d",&a[i][j]);
        int ans = solve();
        printf("Case #%d: %d\n",tt,ans);
    }
}

C. Rabbit House

$R \times C$ 모양의 각 그리드에 박스들이 쌓여 있다. 이웃한 위치에 대해 박스 개수의 차이가 최대 $1이$ 되도록 하려고한다. 추가로 필요한 박스의 최소 개수를 구하는 문제다.

모든 그리드를 순서대로 돌면서 이웃과 비교해서 박스 높이를 최저로 맞춰준다. 한 번 돌 때마다 $O(R+C)$개의 그리드는 조건을 만족하게 된다. 따라서 이를 $O(RC)$번 수행하면 모든 그리드가 조건을 만족하게 된다.

반복문 범위를 잘못 정해줘서 한 번 틀렸다.

다른 풀이도 봤다. 가장 높이 쌓여있는 그리드는 더 쌓을 필요가 없기 때문에 다익스트라로 풀 수 있다. 높이가 확정되지 않은 위치를 max heap에 넣고 순서대로 방문하면서 이웃들의 높이를 적어도 $-1$ 만큼 높아지게 맞춰주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
#define size(v) ((int)v.size())
#define all(v) (v).begin(),(v).end()
using lint = long long;
using fint = long double;
const lint INF = 1e9 + 9;int r, c, g[300][300];

lint solve(){
    lint ret = 0;
    while(true){
        for(int i=0;i<r;++i){
            for(int j=0;j<c;++j){
                if(i>0 && g[i][j] < g[i-1][j]-1)
                    ret += g[i-1][j]-1 - g[i][j], g[i][j] = g[i-1][j] - 1;
                if(j>0 && g[i][j] < g[i][j-1]-1)
                    ret += g[i][j-1]-1 - g[i][j], g[i][j] = g[i][j-1] - 1;
                if(i<r-1 && g[i][j] < g[i+1][j]-1)
                    ret += g[i+1][j]-1 - g[i][j], g[i][j] = g[i+1][j] - 1;
                if(j<c-1 && g[i][j] < g[i][j+1]-1)
                    ret += g[i][j+1]-1 - g[i][j], g[i][j] = g[i][j+1] - 1;
            }
        }
        bool chk = true;
        for(int i=0;i<r;++i)
            for(int j=0;j<c;++j){
                if(i<r-1 && abs(g[i][j]-g[i+1][j])>1)
                    chk = false;
                if(i>0 && abs(g[i][j]-g[i-1][j])>1)
                    chk = false;
                if(j>0 && abs(g[i][j]-g[i][j-1])>1)
                    chk = false;
                if(j<c-1 && abs(g[i][j]-g[i][j+1])>1)
                    chk = false;
            }
        if(chk) break;
    }
    return ret;
}

int main(){
    int tc; scanf("%d",&tc);
    for(int tt=1;tt<=tc;++tt){
        scanf("%d%d",&r,&c);
        for(int i=0;i<r;++i)
            for(int j=0;j<c;++j)
                scanf("%d",&g[i][j]);
        lint ans = solve();
        printf("Case #%d: %lld\n",tt,ans);
    }
}

D. Checksum

$N \times N$ 크기의 $0$과 $1$로 이뤄진 행렬 $A$가 있는데, 몇 개의 원소가 $-1$로 대체되어 버렸다. 원래 행렬에서 각 행의 원소를 모두 XOR한 값과 각 열의 원소를 XOR한 값을 알고 있다. 따라서 몇 개의 원소를 복원하면 남은 원소들을 유추할 수 있기 때문에 행렬 A를 다시 구할 수 있다. $A[i][j]$를 복원하기 위해서는 $B[i][j]$의 비용이 들 때, 행렬 $A$를 복원하는데 드는 최소 비용을 구하는 문제다.

대회 중에는 DP, Greedy, Flow로 접근해봤으니 풀지 못했다(아는 거 다 시도했다 ㅋㅋ). 이전에 비슷한 문제를 풀어봤지만 대회 중에 풀지 못했다.

이 문제는 놀랍게도 MST로 해결하는 문제였다. 맞은 사람들의 코드를 봐도 이해할 수가 없어 어떤 코드포스 블로그의 풀이를 참고했다.

첫 번째 관찰은 대체되지 않은 원소를 비용이 0인 복원해야할 원소로 보는 것이다. 그러면 간단하게 모든 숫자를 최소 비용으로 복원해야하는 문제로 환원된다.

두 번째 관찰은 $N \times N$ 행렬에서 정확히 $(N-1)^2$개의 원소만 복원하면 된다는 것이다.

이제 $(N-1)^2$개의 복원할 원소를 고르는 것 대신 $2N-1$개의 원소를 제외해보자. 제외할 $2N-1$개의 원소의 비용이 최대가 되면 전체 비용은 최소가 되기 때문이다.

아이디어는 $N$개의 행과 $N$개의 열을 노드로 보고 각 원소를 속한 행과 열을 연결하는 간선으로 생각하는 것이다. 그러면 총 $2N$개의 노드가 생기고 우리는 그 중 비용이 최대가 되는 $2N-1$개의 간선을 고르면 된다.

MST로 이 문제를 풀 수 있음을 보장하기 위해 사이클이 허용되는지 확인해야 한다. 행과 열 사이에는 간선이 없으므로 사이클은 반드시 $r_0\leftrightarrow c_0\leftrightarrow r_1\leftrightarrow c_1\cdots\leftrightarrow r_0$꼴이다. 이러한 사이클이 있다면 최소 두 개의 원소가 제외된 행 또는 열이 있게 된다. 이는 각 원소를 유추할 수 없기 때문에 모순이 된다.

따라서 $2N$개의 노드에서 $2N-1$개의 간선을 사이클 없이 골라야하는 문제가 됐고 이를 MST 알고리즘으로 해결하면 $O(N^2logN)$에 해결할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#define size(v) (int)v.size()
#define all(v) (v).begin(),(v).end()
using lint = long long;
using fint = long double;
const lint INF = 1e9 + 9;

int n;
int a[500][500], b[500][500];
int r[500], c[500];

int p[1000];
void init(int n){
    iota(p, p+n, 0);
}
int find(int x){
    return x==p[x] ? x : p[x] = find(p[x]);
}
bool uni(int x,int y){
    if((x=find(x))^(y=find(y)))
        return p[x] = y, true;
    return false;
}

int solve(){
    priority_queue<tuple<int,int,int>> pq;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            pq.emplace(b[i][j], i, n+j);

    int ans = 0;
    init(n*2);
    while(!pq.empty()){
        auto [c, x, y] = pq.top(); pq.pop();
           if(!uni(x,y)) ans += c;    
    }
    return ans;
}

int main(){
    int tc; scanf("%d",&tc);
    for(int tt=1;tt<=tc;++tt){
        scanf("%d",&n);
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                scanf("%d",&a[i][j]);
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                scanf("%d",&b[i][j]);
        for(int i=0;i<n;++i)
            scanf("%d",&r[i]);
        for(int i=0;i<n;++i)
            scanf("%d",&c[i]);
        int ans = solve();
        printf("Case #%d: %d\n",tt,ans);
    }
}

References


  1. My Editorial for Google Kick Start 2021 Round A - Codeforces