AtCoder ABC 282 D, E

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

Tasks - HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)

 

오랜만에 앳코더 풀어봤습니다. ABC는 쉽기도 하고 귀찮아서 패스합니다.

D, E가 생각할 거리가 있는 문제입니다.

 

 

D. 

문제를 요약하면 연결안된 선분 u, v에 대해 선분을 추가해서 이분그래프가 되게 하는 정점쌍 (u,v)의 개수를

구하는 문제입니다. 우선 이분그래프의 특징을 알아야 합니다.

이분그래프는 두 색깔로 색칠했을 때, 인접한 점들을 서로 다른색으로 칠할 수 있는 그래프입니다.

 

관찰1.  선분이 추가된 그래프가 이분그래프면, 추가 전에도 이분그래프입니다. 

대우명제로 현재 그래프가 이분그래프가 아니라고 하면, 어떤 인접한 정점 x, y가 존재하여

x와 y는 같은 색상입니다. 따라서 x,y가 아닌 어떤 선분을 잇는다고 해도 같은 색상인 선분은 사라지지

않습니다. 따라서 추가된 선분도 이분그래프가 아닙니다. 따라서 대우명제에 의해 관찰1이 성립합니다.

 

관찰2. 추가할 선분을 세는 것보다 빼주는 선분을 세는게 쉽습니다.

만약 추가할 선분을 센다면 (u,v)=(빨,파), (파, 빨)인 경우를 빼줘야 합니다. 그런데 그 중에는

이미 이분그래프의 일부인 점도 있습니다. 그럼 이런 선들은 또 제외해줘야 하는데 귀찮습니다.

그렇다면 애초에 안되는 선분들을 세봅시다.

   0. 총 선분의 수는 N^2개 입니다. 

   1. 우선, M개의 input 선분이 빠집니다.  

   2. 한 이분그래프를 빨강과 파랑으로 색칠했을 때, 같은 색끼리는 인접하지 않습니다. 

       우리가 제외할 쌍은 같은 색상 (x, y)이기 때문에 그냥 빨강개수C2 + 파랑개수C2를 빼주면 됩니다.

  (이 문제의 주의할 점은 연결 그래프가 아닌 경우도 있으므로 이분그래프가 여러개 존재할 수 있습니다.)

 

이제 이걸 구현해주면 됩니다. DFS를 돌면서 빨강과 파랑의 개수를 저장해두고 처리해주면 됩니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, u, v, c1, c2;
// c1: 빨간색(1) , c2: 파란색(2)
vector<int>g[200005];
int vis[200005];
// DFS 방문여부와 색을 같이 처리

ll f(ll i) { return i * (i - 1) / 2; }

void dfs(ll u, int col) {
    vis[u] = col;
    (col == 1 ? c1 : c2)++;
    for (int v : g[u]) {
        // 현재 이분그래프 아니면 답은 0
        if (vis[v] == vis[u]) {
            cout << 0 << '\n';
            exit(0);
        }
        else if (vis[v]) continue;
        else dfs(v, 3 - col);
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ll ans = f(n) - m; 
    // 빨강C2+파랑C2 제거 
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            c1 = 0, c2 = 0;
            dfs(i, 1);
            ans -= f(c1) + f(c2);
        }
    }
    cout << ans << '\n';
}

 

 

 

 

E. 

처음 보면 참 막막합니다. 값은 거듭제곱 분할로 잘 처리한다쳐도 순서를 어떻게 정할까 고민됩니다.

그런데 마지막 동작이 포인트입니다. 하나만 빼고 하나는 남긴다는 정보입니다.

아니 원래 이런건 둘 다 뺀다던지 값을 바꾸고 하나를 냅둔다던지 이렇게 하는데 그냥 하나만 버린다?

이걸 어떻게 처리할지 고민하다가 그래프로 표현해보니 그냥 선분하나를 선택하는게 됩니다.

이 부분이 뉴비인 저에겐 참신하게 느껴졌는데  선분을 선택해가며 2개 이상이 남으면 계속 진행한다.

즉, N-1번 진행한다는 뜻입니다.

그럼 답은 바로 최대 스패닝 트리가 되네요. 최소 스패닝 트리에서 마지막에 값을 그리디하게 택하고

유니온파인드 해주는 과정만 최소 스패닝 트리와 반대로 해주면 됩니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, a[505], par[505];
struct Edge {
    ll val, u, v;
};
Edge g[505 * 505];

bool cmp(Edge e1, Edge e2) {
    return e1.val < e2.val;
}

ll Pow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ret % m;
}

ll func(int i, int j) {
    return (Pow(a[i], a[j]) + Pow(a[j], a[i])) % m;
}

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

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    int idx = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            // Edge 생성 
            g[idx].val = func(i, j);
            g[idx].u = i;
            g[idx++].v = j;
        }
    }
    sort(g, g + idx, cmp); // 정렬
    memset(par, -1, sizeof(par));
    ll ans = 0;
    // 크루스칼 알고리즘 과정 
    // 큰 것부터 역순으로 선택하면 최대신장트리
    for (int k = idx - 1; k >= 0; k--) {
        ll x = find(g[k].u);
        ll y = find(g[k].v);
        if (x != y) {
            par[y] = x;
            ans += g[k].val;
        }
    }
    cout << ans << '\n';
}