AtCoder ABC 264 풀이

https://atcoder.jp/contests/abc264/tasks

Tasks - freee Programming Contest 2022（AtCoder Beginner Contest 264）

 

A.

pass

 

B.

굳이 채우지 않고 규칙성으로 해결해봅시다. 중앙사각형에서 "간격"이 홀수이면 검은색이고

짝수면 흰색입니다. 여기서 간격이란 어떤 칸을 잡았을 때 그 칸을 포함하는 정사각틀과 중앙사각형의

거리입니다. 이 간격은 |R-8|과 |C-8|중 최댓값이 됨을 쉽게 알 수 있습니다. 

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int R, C; cin >> R >> C;
    if (max(abs(R - 8), abs(C - 8)) % 2) {
        cout << "black";
    }
    else cout << "white";
}

 

 

C.

N,M이 10밖에 안됩니다. 아이디어는 간단합니다. A의 행에서 H2개 뽑고 A의 열에서 W2개를 뽑는 조합마다

비교해주면 됩니다. 조합구현은 dfs로 쉽게 할 수 있습니다.

또한 뽑은 후에 값을 결정해줄 때 b[i][j]를 읽을 때처럼 이중반복하면 그 순서가 같아집니다.

즉, 뽑아서 값을 벡터에 저장해두면 그냥 비교해주면 끝납니다. 

구현은 x먼저 뽑고 y먼저 뽑는 식으로 했습니다.

 

#include <bits/stdc++.h>
using namespace std;
int h1, w1, h2, w2;
vector<int> v;
int a[11][11], b[11][11], xvis[11], yvis[11];

void solve(int idx1, int idx2, int cnt1, int cnt2) {
    if (cnt1 == h2 && cnt2 == w2) {
        vector<int>temp;
        for (int i = 1; i <= h1; i++) {
            for (int j = 1; j <= w1; j++) {
                if (xvis[i] && yvis[j]) {
                    temp.push_back(a[i][j]);
                }
            }
        }
        if (temp == v) {
            cout << "Yes";
            exit(0);
        }
    }
    for (int i = idx1; i <= h1; i++) {
        if (xvis[i])continue;
        xvis[i] = 1;
        solve(i, idx2, cnt1 + 1, cnt2);
        xvis[i] = 0;
    }
    if (cnt1 == h2) {
        for (int j = idx2; j <= w1; j++) {
            if (yvis[j])continue;
            yvis[j] = 1;
            solve(idx1, j, cnt1, cnt2 + 1);
            yvis[j] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> h1 >> w1;
    for (int i = 1; i <= h1; i++) {
        for (int j = 1; j <= w1; j++) {
            cin >> a[i][j];
        }
    }
    cin >> h2 >> w2;
    for (int i = 1; i <= h2; i++) {
        for (int j = 1; j <= w2; j++) {
            cin >> b[i][j];
            v.push_back(b[i][j]);
        }
    }
    solve(1, 1, 0, 0);
    cout << "No";
}

 

 

D.

이것도 수가 작습니다. BFS해주면서 도착하면 그게 최소횟수가 됩니다. 시간은 O(7!)이 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
map<string, int>vis;

void BFS(string st) {
    queue<string>q;
    vis[st] = 1;
    q.push(st);
    while (q.size()) {
        auto x = q.front(); q.pop();
        if (x == "atcoder") {
            cout << vis[x] - 1;
            return;
        }
        for (int i = 1; i < 7; i++) {
            string nx = x;
            swap(nx[i - 1], nx[i]);
            if (!vis[nx]) {
                vis[nx] = vis[x] + 1;
                q.push(nx);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    string s; cin >> s;
    BFS(s);
}

 

 

E.

도시와 발전소들을 연결하고 매쿼리마다 특정경로를 지우고 그 때 전력도시의 개수를 찾아야 합니다. 

관찰1. 발전소간 연결은 의미가 없습니다. 

관찰2. 경로를 지우는 쿼리는 오프라인으로 뒤집는게 국룰입니다. 

관찰3. N이 크다보니 매번 개수갱신에 O(logN)을 넘으면 안됩니다.  

유니온 파인드로 경로를 합치면서 배열 cnt[ ] 를 만들어 관리합시다. 근데 매번 출력해야하는것은

cnt[n+1]+cnt[n+2]+...+cnt[n+m]입니다. O(n) 이라 더 줄여야 합니다.  

또한 이 방식은 문제가 있습니다. 발전소마다 가능한 마을이 겹치기 때문입니다. 따라서 이렇게는 안됩니다. 

여기서 관찰1이 사용되는데, 발전소간 연결은 무의미하니 발전소 M개는 그냥 N+1번 1개로 묶어줘도 됩니다. 

이후 유파로 합쳐주면서 cnt [n+1]을 출력해주면 됩니다. 유니온 과정에선 항상 큰게 부모가 되도록 해주면

구현이 쉬워집니다. 재밌는 문제였습니다. 

 

#include <bits/stdc++.h>
using namespace std;
const int MAX = 500005;
pair<int, int>info[MAX];
int par[200005];
int n, m, Q, E;
int u[MAX], v[MAX], x[MAX], vis[MAX];
int ans[MAX], cnt[MAX];

int chk(int x) {
    return (x <= n ? x : n + 1);
}

int find(int x) {
    return !~par[x] ? x : par[x] = find(par[x]);
}

void uni(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
        if (x < y) swap(x, y);
        par[y] = x;
        cnt[x] += cnt[y];
        cnt[y] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> E;
    memset(par, -1, sizeof(par));
    fill(cnt + 1, cnt + n + 1, 1);
    for (int i = 1; i <= E; i++) {
        cin >> u[i] >> v[i];
        u[i] = chk(u[i]);
        v[i] = chk(v[i]);
        info[i] = { u[i], v[i] };
    }
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        cin >> x[i];
        vis[x[i]] = 1;
    }
    for (int i = 1; i <= E; i++) {
        if (vis[i]) continue;
        uni(u[i], v[i]);
    }
    for (int i = Q; i >= 1; i--) {
        ans[i] = cnt[n + 1];
        auto [uu, vv] = info[x[i]];
        uni(uu, vv);
    }
    for (int i = 1; i <= Q; i++) {
        cout << ans[i] << '\n';
    }
}

 

F.

뭔가 최소컷인가 했는데 n<=2000이라 빠르게 포기합니다.

dp삘이 납니다. 우선 행 또는 열을 뒤집는 행위는 최대 1번이 가능합니다. 2번이상이라면

0,1번 뒤집은 상태의 반복이고 최소비용이 안됩니다. 

또한 현재 칸의 상태와 인덱스가 필요합니다. 칸의 상태는 디폴트 a[i][j]에서 flip여부에 따라 바뀝니다. 

dp[i][j][f1][f2]:= (i,j)에 도달했고 Ri를 f1번 뒤집었고  Cj를 f2번 뒤집었을때 단색경로의 최솟값이라 정의합니다. 

우선 (i+1,j)로 전이되는 경우를 봅시다. x방향 아래로 전이되므로 f2는 바뀌지 않습니다. 

그럼 a[i][j]와 a[i+1][j] 색깔과 f1에 따라 그다음 f1의 상태를 결정해줄 수 있습니다. 

여기서 경우는 8가지로 나뉩니다. 

1. a[i][j]=0 & a[i+1][j]=0 & f1=0 인 경우 a[i][j]는 최종적으로 흰색이므로 (i,j)까지가 흰색경로입니다. 

또한 a[i+1][j]도 흰색이므로 이 때는 뒤집을 필요가 없습니다. 즉, nf1=0입니다. 

2. a[i][j]=0 & a[i+1][j]=0 & f1=1 인 경우 a[i][j]는 최종적으로 검은색이고 검은색 경로가 됩니다. 

a[i+1][j]는 흰색이므로 한번 뒤집어야 검은색 단색경로가 됩니다. 즉 nf1=1입니다. 

이렇게 a[i][j]경우 2가지, a[i+1][j]경우 2가지 f1 2가지마다 nf1을 구해보면, 

nf1은 (a[i][j], a[i+1][j], f1 에서 1의 개수) %2입니다. 비트 트릭을 이용하면 a[i][j]^a[i+1][j]^f1이 됩니다. 

따라서 dp[i+1][j][nf1][f2]=min(dp[i][j][f1][f2]+nf1*비용) 이 됩니다. 

(i,j+1)로 전이되는 경우도 위와 똑같은 논리입니다. 되게 재밌게 푼 문제였습니다. 

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll h, w, R[2002], C[2002], a[2002][2002];
ll dp[2002][2002][2][2];
#define FOR(i,s,n) for(int i=s;i<=n;i++)

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> h >> w;
    FOR(i, 1, h) cin >> R[i];
    FOR(j, 1, w) cin >> C[j];

    FOR(i, 1, h) FOR(j, 1, w) {
        char s; cin >> s;
        a[i][j] = s - '0';
        // init 
        FOR(x, 0, 1) FOR(y, 0, 1) {
            dp[i][j][x][y] = 1e18;
        }
    }
    // base case
    FOR(x, 0, 1) FOR(y, 0, 1) {
         dp[1][1][x][y] = x * R[1] + y * C[1];     
    }
    FOR(i, 1, h) FOR(j, 1, w) FOR(f1, 0, 1) FOR(f2, 0, 1) {
        // (i,j)->(i+1,j)
        if (i < h) {
            int nf1 = a[i][j] ^ a[i + 1][j] ^ f1;
            dp[i + 1][j][nf1][f2] = min(dp[i + 1][j][nf1][f2],
                dp[i][j][f1][f2] + nf1 * R[i + 1]);
        }
        // (i,j)->(i,j+1)
        if (j < w) {
            int nf2 = a[i][j] ^ a[i][j + 1] ^ f2;
            dp[i][j + 1][f1][nf2] = min(dp[i][j + 1][f1][nf2],
                dp[i][j][f1][f2] + nf2 * C[j + 1]);
        }
    }
    ll ans = 1e18;
    FOR(f1, 0, 1) FOR(f2, 0, 1) ans = min(ans, dp[h][w][f1][f2]); 
    cout << ans;
}

 

 

G.

풀이 예정 

 

 

H.

풀이 예정.