[C++] 11670번 초등 수학 / 30887번 Basic Math

https://www.acmicpc.net/problem/11670

https://www.acmicpc.net/problem/30887

---

 

26/01/17,18

 

 

두 문제는 동일한 문제이므로 하나의 게시물로 묶어서 올려본다.

---

 

문제 접근 방식:

 

 

하나의 순서쌍 $(a, b)$를 $\text{left}$에 있는 하나의 정점으로 간주하고, $a\cdot b, a+b, a-b$에 해당하는 수 $3$개 각각을 $\text{right}$에 있는 정점들로 간주하자.

그러면 $(a, b)\to a\cdot b$ 간선 하나, $(a, b)\to a+b$ 간선 하나, $(a, b)\to a-b$ 간선 하나를 만들 수 있다.

이제 그래프 모델링이 완료되었으므로, 이분 매칭을 진행하면 된다.

$N \leq 2\ 500$이므로 $V \leq 10 \ 000 \ , E \leq 30 \ 000$이고, Kuhn의 알고리즘을 사용한다면 $\mathcal{O}(VE)$이므로 대략 3억번의 연산이 필요하다. 시간 제한은 10초이므로 충분하다.

만약 Hopkroft-Karp 알고리즘을 사용한다면 $\mathcal{O}(E\sqrt{V })$이므로 대략 3백만번의 연산이 필요하다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 11670번 초등 수학
// 이분 매칭
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <random>
#include <map>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
typedef long long ll;

struct HopcroftKarp {
    int L, R;
    vector<vector<int>> adj;
    vector<int> matchL, matchR, dist;

    HopcroftKarp(int L, int R) : L(L), R(R), adj(L), matchL(L, -1), matchR(R, -1), dist(L, 0) {}
    void addEdge(int u, int v) { if (find(adj[u].begin(), adj[u].end(), v) == adj[u].end()) adj[u].push_back(v); }
    void adjShuffle() {
        mt19937 rng(random_device{}());
        for (int u = 0; u < L; ++u) shuffle(adj[u].begin(), adj[u].end(), rng);
    }
    int bfs(void) {
        queue<int> q;
        const int INF = 1e9;
        for (int u = 0; u < L; ++u) {
            if (matchL[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INF;
            }
        }
        int foundAugPath = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int u2 = matchR[v];
                if (u2 == -1) {
                    foundAugPath = 1;
                } else if (dist[u2] == INF) {
                    dist[u2] = dist[u] + 1;
                    q.push(u2);
                }
            }
        }
        return foundAugPath;
    }
    int dfs(int u) {
        for (int v : adj[u]) {
            if (matchR[v] == -1 || (dist[matchR[v]] == dist[u] + 1 && dfs(matchR[v]))) {
                matchL[u] = v;
                matchR[v] = u;
                return 1;
            }
        }
        dist[u] = 1e9;
        return 0;
    }
    int matching(void) {
        int match = 0;
        while (bfs()) {
            for (int u = 0; u < L; ++u) {
                if (matchL[u] == -1) {
                    if (dfs(u)) ++match;
                }
            }
        }
        return match;
    }
    vector<pair<int,int>> matchedEdges() const {
        vector<pair<int,int>> res;
        res.reserve(min(L, R));
        for (int u = 0; u < L; ++u) {
            if (matchL[u] != -1) res.push_back({u, matchL[u]});
        }
        return res;
    }
};

int main(void){
    fastio

    int N; cin >> N;
    map<int, ll> mappingIdxToRes;
    map<ll, int> mappingResToIdx;
    vector<pair<ll, ll>> pairList(N);
    for (int i = 0; i < N; ++i){
        cin >> pairList[i].first >> pairList[i].second;
    }
    int idx = 0;
    for (int i = 0; i < N; ++i){
        ll res1 = pairList[i].first + pairList[i].second;
        ll res2 = pairList[i].first - pairList[i].second;
        ll res3 = pairList[i].first * pairList[i].second;
        if (mappingResToIdx.find(res1) == mappingResToIdx.end()){
            mappingResToIdx[res1] = idx;
            mappingIdxToRes[idx] = res1;
            ++idx;
        }
        if (mappingResToIdx.find(res2) == mappingResToIdx.end()){
            mappingResToIdx[res2] = idx;
            mappingIdxToRes[idx] = res2;
            ++idx;
        }
        if (mappingResToIdx.find(res3) == mappingResToIdx.end()){
            mappingResToIdx[res3] = idx;
            mappingIdxToRes[idx] = res3;
            ++idx;
        }
    }

    HopcroftKarp HK(N, mappingIdxToRes.size());
    int v;
    for (int u = 0; u < N; ++u){
        ll res1 = pairList[u].first + pairList[u].second;
        v = mappingResToIdx[res1];
        HK.addEdge(u, v);

        ll res2 = pairList[u].first - pairList[u].second;
        v = mappingResToIdx[res2];
        HK.addEdge(u, v);

        ll res3 = pairList[u].first * pairList[u].second;
        v = mappingResToIdx[res3];
        HK.addEdge(u, v);
    }

    if (HK.matching() == N){
        vector<pair<int, int>> matchedEdges = HK.matchedEdges();
        for (pair<int, int> p : matchedEdges){
            int u = p.first, v = p.second;
            ll res = mappingIdxToRes[v];
            ll res1 = pairList[u].first + pairList[u].second;
            ll res2 = pairList[u].first - pairList[u].second;
            ll res3 = pairList[u].first * pairList[u].second;
            if (res == res1){
                cout << pairList[u].first << " + " << pairList[u].second << " = " << res << endl;
            } else if (res == res2){
                cout << pairList[u].first << " - " << pairList[u].second << " = " << res << endl;
            } else {
                cout << pairList[u].first << " * " << pairList[u].second << " = " << res << endl;
            }
        }
    } else {
        cout << "impossible";
    }
    return 0;
}