[BOJ] Journey to TST set3

저번에 이어서 Journey to TST set3를 풀려고 한다.

 

https://psforhobby.tistory.com/58

[BOJ] Journey to TST set2

https://dsstar.tistory.com/53

Journey to TST 문제 셋 공유

02/09의 문제 셋이고, 이번에도 내가 푼 순서대로 리뷰하려고 한다. 이번엔 더 오래 걸렸다. 마지막으로 푼 문제가 어려웠다. 사실상 답을 까고 푼 수준.

 

1. Commuter Pass(15556)

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

실제 난이도에 비해 나는 어렵게 느껴졌다. 

 

문제

양방향 간선들 각각에 비용이 있는 크기 $N$, 간선 개수 $M$의 그래프가 주어진다. 한 Commuter Pass를 사면 $S$에서 $T$로 가는 최소 비용 경로 중 하나의 모든 간선 비용을 $0$으로 만들 수 있다. 이 때 한 Commuter Pass를 사서 $U$에서 $V$로 가는 비용의 최소로 할 때 그 비용을 구하라.

$1 \leq N \leq 10^5, 1 \leq M \leq 2 \times 10^5$.

 

풀이

풀이는 간단하다. S와 T를 연결하는 최단경로들 중에서 적당히 두 정점을 뽑아 하나로부터 U까지의 최소 비용과 다른 하나로부터 V까지의 최소 비용 합이다. 다만 모든 경로를 일일이 해볼 수는 없다. 때문에 최단경로 상의 점들에 대해 각 점에서 $S/T$까지 가는 경로 상 정점들의 $U/V$까지 가는 최소비용를 dp로 구해주면 모든 정점들에 대해 $(S,U) + (T,V)$와 $(S,V)+(T,U)$ 중 최솟값이 답임을 알 수 있다. ($(S,U)$는 $S$까지 가는 경로 상 정점들의 $U$까지 가는 최소 비용을 의미)

 

다른 사람들의 풀이를 보니 $S \rightarrow T$ 최단경로 상의 점들을 구했으면 $U \rightarrow V$ 로 가는 다익스트라에 조금 변형을 가해도 답을 구할 수 있는 것으로 보인다.

 

TMI로 람다 표현식을 배울 겸 람다를 이용해 작성해봤다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;

const int INF = 1e9;
const ll LINF = 1e18;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int N, M, S, T, U, V;
    cin >> N >> M >> S >> T >> U >> V;
    vector <vector <pil>> g(N+1);
    for(int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].eb(v, c), g[v].eb(u, c);
    }

    auto Djikstra = [&](vector <ll> &d, int st) {
        d[st] = 0;
        priority_queue <pll> pq;
        vector <bool> chk(N+1);
        pq.em(0, st);
        while(!pq.empty()) {
            int x = pq.top().se;
            pq.pop();
            if(chk[x]) continue;
            chk[x] = true;
            for(auto [y, c] : g[x]) {
                if(d[y] > d[x] + c) {
                    d[y] = d[x] + c;
                    pq.em(-d[y], y);
                }
            }
        }
    };

    vector <ll> d_S(N+1, LINF), d_T(N+1, LINF), d_U(N+1, LINF), d_V(N+1, LINF);
    Djikstra(d_S, S);
    Djikstra(d_T, T);
    Djikstra(d_U, U);
    Djikstra(d_V, V);

    auto get_pre = [&](vector <vector <int>> &pre, vector <ll> &d, int tar) {
        queue <int> q;
        vector <bool> chk(N+1);
        chk[tar] = true;
        q.em(tar);
        while(!q.empty()) {
            int x = q.front();
            q.pop();
            for(auto [y, c] : g[x]) {
                if(d[x] == d[y] + c) {
                    pre[x].eb(y);
                    if(!chk[y]) {
                        q.em(y);
                        chk[y] = true;
                    }
                }
            }
        }
    };

    vector <vector <int>> pre_S(N+1), pre_T(N+1);
    get_pre(pre_S, d_S, T);
    get_pre(pre_T, d_T, S);

    auto get_dp = [&](vector <vector <int>> &pre, vector <ll> &dp_U, vector <ll> &dp_V, int tar) {
        vector <int> ind(N+1);
        queue <int> q;
        for(int i = 1; i <= N; i++) {
            for(int j : pre[i]) {
                ind[j]++;
            }
        }
        q.em(tar);
        while(!q.empty()) {
            int x = q.front();
            q.pop();
            dp_U[x] = min(dp_U[x], d_U[x]), dp_V[x] = min(dp_V[x], d_V[x]);
            for(int i : pre[x]) {
                ind[i]--;
                dp_U[i] = min(dp_U[i], dp_U[x]);
                dp_V[i] = min(dp_V[i], dp_V[x]);
                if(ind[i] == 0) q.em(i);
            }
        }
    };

    vector <ll> dp_SU(N+1, LINF), dp_SV(N+1, LINF), dp_TU(N+1, LINF), dp_TV(N+1, LINF);
    get_dp(pre_S, dp_SU, dp_SV, T);
    get_dp(pre_T, dp_TU, dp_TV, S);

    ll ans = LINF;
    for(int i = 1; i <= N; i++) {
        ans = min({ans, dp_SU[i] + dp_TV[i], dp_SV[i] + dp_TU[i]});
    }
    cout << min(ans, d_U[V]) << '\n';
}

 

2. Kingdom Trip(11476)

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

의도된 풀이는 $O(N^2)$인 것으로 보이나 나는 $O(N^2\log N)$에 풀었다. 내 원래 풀이가 단순하지만 의도된 풀이보다 코딩은 더 복잡한 듯.

 

문제

2차원 평면에 점 $N$개 $p_1, \cdots p_N$이 있다. $p_1$에서 출발해 $p_N$으로 이동할 것이고 $1 \leq i<j \leq N$인 $i, j$와 $i<k<j$인 모든 $k$에 대해 $p_i$와 $p_j$를 연결하는 선분과 $p_k$의 거리가 $d$ 이하일 때만 $i$에서 $j$로 이동 가능하다. $p_N$에 도착할 때까지 거치는 점의 최소는?

$2 \leq N \leq 2 \times 10^3, 1 \leq d \leq 10^6$이고 각 점의 좌표 $|x_i|, |y_i| \leq 10^6$.

 

풀이

결국 $i<j$인 모든 $(i, j)$ 쌍에 대해 $i$에서 $j$로 바로 이동 가능한지 판별하기만 하면 된다. 이는 $i<k<j$인 $k$들이 있어야 하는 영역을 $p_j$쪽을 무한히 늘렸을 때와 $p_i$쪽을 무한히 늘렸을 때 모두 가능한 것과 동치이다. 즉 $p_i$로부터 $p_j$를 연결하는 반직선과 $p_j$로부터 $p_i$를 연결하는 반직선에 대해 각각 판별 가능하면 원래 문제를 풀 수 있다. 이를 각각 $(i, j)$ 조건, $(j, i)$ 조건이라 하자.

 

내 풀이는 다음과 같다. 점 $i$를 기준으로 거리가 $d$ 이하인 점들은 예외 처리한다. 나머지 점들의 경우 각 점이 영역에서 빠지고 들어가도록 하는 반직선의 각도를 알 수 있다.(약간의 수학 계산이 필요하다.) 각 점들과 빠지고 들어가는 각도를 모두 넣고 각도정렬 후 스위핑 해주면서 펜윅 트리를 같이 이용해주면 모든 조건의 참 거짓을 판별할 수 있고 문제가 풀린다. 정렬과 스위핑하며 펜윅을 쓰는 것 때문에 시간복잡도는 $O(N^2 \log N)$.

 

따로 코드를 작성하지는 않았지만 $N^2$ 풀이에 대해 설명하고자 한다. 결국 연속된 번호들이 어떤 영역에 있는지 판별하면 되기 때문에 굳이 점의 순서를 각도별로 보지 않고 점 번호 순으로 보며 판단하면 간단할 것으로 보인다. $i$로부터 시작하여 연속된 번호들의 점들을 차례로 보며 그 점들이 모두 영역에 포함되도록 하는 반직선으로 가능한 각도의 범위를 계산해주자. 이 각도 범위 안에 $p_j$가 있다면 $(i, j)$는 참인 조건인 것이다. 비슷하게 모든 조건들의 참 거짓을 판별 가능하며 문제가 풀린다. 시간복잡도는 $O(N^2)$. 여담이지만 가능한 각도를 사분면 등으로 잘 나눠 관리해야 되서 케이스워크가 조금 빡세 보인다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;
const ll mod = 998244353;

pii operator + (pii &X, pii &Y) { return pii(X.fi + Y.fi, X.se + Y.se); }
pii operator - (pii &X, pii &Y) { return pii(X.fi - Y.fi, X.se - Y.se); }

struct Point {
    double x, y;
    int idx;
    Point(double _x, double _y, int _idx) : x(_x), y(_y), idx(_idx) {}

    bool operator < (const Point &p) const {
        double sgn = x * p.x;
        if(abs(sgn) < 1e-18) {
            if(abs(p.x) < 1e-12 && p.y < 0.0) return false;
            if(abs(x) < 1e-12 && y < 0.0) return true;
            return x * p.y - y * p.x > 0.0;
        }
        else if(x * p.x < 0.0) return x > 0.0;
        else return x * p.y - y * p.x > 0.0;
    }
};

struct BIT {
    vector <int> tree;
    int sz;
    BIT(int n) : sz(n) {
        tree.resize(n+1);
    }
    
    void clear() {
        for(int &i : tree) i = 0;
    }

    void update(int i, int val) {
        for(; i <= sz; i += (i & -i)) tree[i] += val;
    }

    int cal(int l, int r) {
        if(l > sz) exit(1);
        if(r > sz) exit(1);
        int ret = 0;
        if(l > r) swap(l, r);
        for(; r > 0; r -= (r & -r)) ret += tree[r];
        for(l--; l > 0; l -= (l & -l)) ret -= tree[l];
        return ret;
    }
};

ll dist(pii a, pii b) {
    return (ll)(a.fi - b.fi) * (a.fi - b.fi) + (ll)(a.se - b.se) * (a.se - b.se);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, d;
    cin >> n >> d; 
    vector <pii> v(n+1);
    vector <vector <bool>> chk(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> v[i].fi >> v[i].se;
        chk[i].resize(n+1);
    } 

    BIT T(n);
    for(int i = 1; i <= n; i++) {
        vector <Point> tv;
        for(int j = 1; j <= n; j++) {
            if(i == j) continue;
            v[j].fi -= v[i].fi, v[j].se -= v[i].se;
            tv.eb(v[j].fi, v[j].se, n + j);
            if((ll)v[j].fi * v[j].fi + (ll)v[j].se * v[j].se <= (ll)d * d) T.update(j, 1);
            else {
                double vv = (double)((ll)v[j].fi * v[j].fi + (ll)v[j].se * v[j].se);
                double temp = sqrt(vv - (double)d * d);
                tv.eb(temp * v[j].fi + (double)d * v[j].se, temp * v[j].se - (double)d * v[j].fi, j);
                tv.eb(temp * v[j].fi - (double)d * v[j].se, temp * v[j].se + (double)d * v[j].fi, -j);
            }
            v[j].fi += v[i].fi, v[j].se += v[i].se;
        }
        sort(all(tv));
        vector <bool> c(n+1);
        for(Point &p : tv) {
            if(p.idx > n) continue;
            if(p.idx < 0 && !c[abs(p.idx)]) T.update(-p.idx, 1);
            c[abs(p.idx)] = true;
        }
        for(Point &p : tv) {
            if(p.idx > n) {
                p.idx -= n;
                if(T.cal(i, p.idx) == abs(i - p.idx)) chk[i][p.idx] = true;
            }
            else if(p.idx > 0) T.update(p.idx, 1);
            else T.update(-p.idx, -1);
        }
        T.clear();
    }

    vector <int> dp(n+1);
    dp[1] = 1;
    for(int i = 2; i <= n; i++) {
        dp[i] = n;
        for(int j = 1; j < i; j++) {
            if(chk[i][j] && chk[j][i]) dp[i] = min(dp[i], dp[j] + 1);
        }
    }
    cout << dp[n] << endl;
}

 

3. Pork barrel(10511)

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

Dynamic MST 예시문제로 봤던 기억이 나는데 푸는 방법이 기억이 안 나서 묵혀뒀다가 다시 보니까 그냥 풀렸다.

 

문제

정점 $N$개와 비용이 주어진 간선 $M$개로 이루어진 그래프가 있다. $Q$개의 쿼리가 주어진다. $i$번째 쿼리에서는 비용이 $l_i$ 이상 $h_i$ 이하인 간선들만 사용했을 때 최대한 많은 도시를 최소 비용으로 연결할 때 비용을 구해야 한다. $l_i$와 $h_i$가 이전 답에 따라 달라져 온라인으로 처리해야 한다.

$1 \leq N \leq 10^3, 0 \leq M \leq 10^5, 1 \leq Q \leq 10^6$. 각 간선의 비용 $1 \leq w \leq 10^6$.

 

풀이

크루스칼 알고리즘을 적용한다고 생각해보자. 어떤 간선 $x y w$가 사용되지 않는 경우는 $x$와 $y$가 이미 연결된 경우이다. 최초로 이러한 상황이 발생했다고 생각해보자. 여기서 이 간선을 사용하도록 하기 위한 비용 하한의 최대는 ($x$와 $y$를 연결하는 경로 상 가장 작은 간선 비용) $+ 1$일 것이다. 이제 그 경로 상 가장 작은 비용을 가진 간선을 끊고 현재 간선을 이어보자. 그러면 다음으로 두 정점이 이미 연결된 간선에 대해서도 위 식이 성립할 것이다. 따라서 이를 계속 반복하면 모든 간선에 대해 해당 간선이 처음으로 사용되는 시점을 구할 수 있다.

 

위 관찰을 거쳤다면 다음과 같이 문제를 단순화시킬 수 있다. 간선을 정렬하고 $k$번 간선이 연결되기 위해 끊어야 하는 간선의 번호를 $pre_k$라고 하자. 그러면 요구하는 $i$번째 쿼리의 답은 $l_i$ 이상 $h_i$ 이하 비용을 가진 간선들 중 $pre_k$번 간선의 비용이 $l_i$ 미만인 $k$들에 대해 $w_k$를 더한 값이다. (마치 서로 다른 수와 쿼리의 풀이와 비슷하다.) 이 2D 쿼리를 PST로 잘 구현해주면 시간복잡도 $O(NM+Q\log M)$에 해결 가능하다. 

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int INF = 1e9;
const ll LINF = 1e18;

struct PST {
    struct Node {
        int l, r;
        ll val;
        Node(int _l, int _r, ll _val) : l(_l), r(_r), val(_val) {}
    };
    vector <Node> tree;
    vector <int> root;
    int sz;
    PST(int n) : sz(n) {
        root.eb(tree.size());
        tree.eb(0, 0, 0);
    }

    void update(int k, int val) {
        root.eb(tree.size());
        tree.eb(0, 0, 0);
        update(root.back(), root[root.size()-2], 0, sz-1, k, val);
        return;
    }
    void update(int cnd, int pnd, int s, int e, int k, int val) {
        tree[cnd].val = tree[pnd].val + val;
        if(s == e) return;
        int m = (s + e) / 2;
        if(k <= m) {
            tree[cnd].l = tree.size();
            tree[cnd].r = tree[pnd].r;
            tree.eb(0, 0, 0);
            update(tree[cnd].l, tree[pnd].l, s, m, k, val);
        }
        else {
            tree[cnd].l = tree[pnd].l;
            tree[cnd].r = tree.size();
            tree.eb(0, 0, 0);
            update(tree[cnd].r, tree[pnd].r, m+1, e, k, val);
        }
        return;
    }

    int cal(int L, int R, int r) {
        return cal(root[L-1], root[R], 0, sz-1, r);
    }
    ll cal(int pnd, int cnd, int s, int e, int r) {
        if(s > r) return 0;
        if(e <= r) return tree[cnd].val - tree[pnd].val;
        int m = (s + e) / 2;
        return cal(tree[pnd].l, tree[cnd].l, s, m, r) + cal(tree[pnd].r, tree[cnd].r, m+1, e, r);
    }
};

struct DSU {
    vector <int> p, sz;
    DSU(int n) {
        p.resize(n+1);
        sz.resize(n+1);
        for(int i = 1; i <= n; i++) {
            p[i] = i; sz[i] = 1;
        }
    }

    int find(int x) {
        return x == p[x] ? x : p[x] = find(p[x]);
    }

    bool uni(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return false;
        if(sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        p[y] = x;
        return true;
    }
};

struct Edge {
    int u = 0, v = 0, w = 0;
};

pii dfs(int x, int pa, int tar, vector <set <pii>> &g, vector <Edge> &E) {
    for(pii i : g[x]) {
        if(i.fi == pa) continue;
        if(i.fi == tar) return pii(i.se, 1);
        pii val = dfs(i.fi, x, tar, g, E);
        if(val.se) {
            if(E[val.fi].w > E[i.se].w) val.fi = i.se;
            return val;
        }
    }
    return pii(0, 0);
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector <Edge> E(m+1);
    for(int i = 1; i <= m; i++) {
        cin >> E[i].u >> E[i].v >> E[i].w;
    }
    sort(next(E.begin()), E.end(), [](Edge &a, Edge &b) { return a.w < b.w; });

    PST T(m+1);
    DSU S(n);
    vector <set <pii>> g(n+1);
    vector <int> pre(m+1);

    for(int i = 1; i <= m; i++) {
        if(!S.uni(E[i].u, E[i].v)) {
            pre[i] = dfs(E[i].u, 0, E[i].v, g, E).fi;
            g[E[pre[i]].u].erase(pii(E[pre[i]].v, pre[i]));
            g[E[pre[i]].v].erase(pii(E[pre[i]].u, pre[i]));
        }
        g[E[i].u].em(E[i].v, i);
        g[E[i].v].em(E[i].u, i);
        T.update(pre[i], E[i].w);
    }

    int q;
    ll c = 0;
    cin >> q;
    while(q--) {
        ll tl, tr;
        cin >> tl >> tr;
        int l = tl - c, r = tr - c;
        int L, R;
        int lb = 1, ub = m;
        while(lb < ub) {
            int m = (lb + ub) / 2;
            if(E[m].w >= l) ub = m;
            else lb = m + 1;
        }
        L = lb;
        lb = 1, ub = m;
        while(lb < ub) {
            int m = (lb + ub + 1) / 2;
            if(E[m].w <= r) lb = m;
            else ub = m - 1;
        }
        R = lb;
        c = T.cal(L, R, L - 1);
        cout << c << '\n';
    }

    return;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int t;
    cin >> t;
    while(t--) {
        solve();
    }

    return 0;
}

 

4. Merlin QA (Large)(12126)

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

TLE 몇 번 맞고 맞왜틀 하다가 답답해서 구글링으로 답을 봤는데 애초에 풀이가 틀렸었다. 근데 풀이가 코드만 보고 유추하긴 힘들 정도로 멋있다.

 

문제

$M$ 종류의 재료가 있다. 주문이 $N$개 있는데 각 주문은 몇 개의 재료들을 소진해 몇 개의 재료들을 생성할 수 있다. 초기에는 아무 재료도 가지고 있지 않으며, 각 주문을 사용할 때 재료가 부족하다면 부족한 만큼 창고에서 가져올 수 있다.(즉, 재료가 부족해도 주문 사용 가능) 이 때 주문의 순서를 잘 배치해 최종 재료 개수 합의 최대로 하라.

$1 \leq N \leq 100, 1 \leq M \leq 8$. 총 $T \leq 100$개의 테스트케이스로 이루어져 있다.

 

풀이

전체 합을 고려하기 전에 먼저 각 재료의 개수가 어떻게 변화하는지 살펴보자. 어느 순간 0이 되었다가 그 이후로는 한 번도 0이 되지 않을 것이다. $M$개의 재료에 대해 각각 그렇게 되는 시점이 다를텐데, 이 시점의 순서를 고정하고(!!!) 생각해보자.

 

그럼 결국 처음에는 답에 첫 번째 것만 더해지다가, 그 다음에는 첫 번째와 두 번째 것만 더해지다가... 할 것이다. 즉 우리는 문제를 $N$개의 주문을 적당히 나눠 현재 정해놓은 순서에 대해 위 규칙으로 더한 값의 최대를 구하는 것으로 바꿀 수 있다. 여기서 미리 마지막으로 0이 되는 시점을 정한 것이 강력한 이유가 나오는데, 바로 그냥 시점 순서대로 각 재료들의 변화량을 더했을 때 그 과정에서의 최댓값이 그 주문으로부터 얻을 수 있는 양이 되기 때문이다. 예를 들어 3번째까지 더한 값이 최대라면 세 번째 것까지 더하는 타이밍에 주문을 사용한다고 생각하면 된다. 따라서 테스트케이스당 $M! NM$에 해결 가능하다. 시간 제한이 조금 빡빡하다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int INF = 1e9;
const ll LINF = 1e18;

void solve() {
    int n, m;
    cin >> n >> m;
    vector <vector <int>> v(n);
    vector <int> p(m);
    for(int i = 0; i < n; i++) {
        v[i].resize(m);
        for(int j = 0; j < m; j++) {
            cin >> v[i][j];
        }
    }
    for(int i= 0; i < m; i++) {
        p[i] = i;
    }

    int f = 1;
    int ans = -INF;
    for(int i = 2; i <= m; i++) f *= i;

    for(int t = 0; t < f; t++) {
        int tans = 0;
        for(int i = 0; i < n; i++) {
            int c = 0, val = 0;
            for(int j = 0; j < m; j++) {
                c += v[i][p[j]];
                val = max(val, c);
            }
            tans += val;
        }
        ans = max(ans, tans);
        next_permutation(all(p));
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int t;
    cin >> t;
    for(int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}