[2020.1.1] JOI spring camp 2018/2019 Day 4

https://oj.uz/problems/source/379

 

1. Cake 3

유사 holiday (IOI 2014) 이다. 잘 생각해보면 결국 M개의 케이크조각을 골랐을 때 ∑|C_i-C_i+1|은 2 * (MAX(C_i) - MIN(C_i)) 와 같다는 것을 알 수 있다. 우선 케이크조각을 원형으로 배치한다 했을 때 제일 작은 원소와 큰 원소를 먼저 놓고, 나머지를 끼어넣는다 생각하자. 그러면 결국 최적해는 가장 작은 원소에서 가장 큰 원소로 갈 때 C가 증가해야한다는 것을 알 수 있다. 이 때 총 비용은 2 * (MAX(C_i) - MIN(C_i))이 된다.

 

그러면 이제 문제는 적당히 M개를 골라서 V를 모두 더하고 거기서 2*(MAX(C_i)-MIN(C_i))를 뺀 값의 최댓값을 구하면 된다. 우선 케이크조각을 C가 증가하는 순서로 정렬하자. 이 때 M개를 고른 경우 중 MAX(C_i)인 i, 다시 말하면 C값이 가장 큰 조각을 i라 하고 비슷하게 C가 가장 작은 조각을 j라 하면 이 때 최적해는 문제는 i~j중 큰 순서대로 V를 M개를 뽑아 더하고, 거기에 2*(C_i-C_j)를 뺀 값이 된다. 이 값은 PST를 이용하면 log n만에 구할 수 있다. 이제 그 다음이 문제인데, 모든 (i, j) 쌍을 고려하기에는 너무 시간이 많이 걸린다는 것이다.

 

여기서 DNC optimization을 사용하면 된다. 생각해보면 i가 증가함에 따라 j가 단조증가한다는 사실을 알 수 있다. (C_i-C_j) 만약 i일 때 j가 최적인데 i+1일 때는 j-a일 때 최적이라고 가정해보면 i일 때 j가 최적이라는 것이 모순임을 알 수 있다. 때문에 DNC optimization을 사용할 수 있고, 이에 총 시간복잡도는 O(n log^2 n)이 된다.

 

코드

#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;

struct Node {
    int l, r, c; ll val;
    Node(int l, int r, int c, ll val) : l(l), r(r), c(c), val(val) {}
};

pll arr[2*MAX];
int root[2*MAX], n, x;
vector <Node> tree;
vector <ll> num;
ll ans = -LINF;

void expand_tree(int s, int e, int k, int pnd, int cnd) {
    tree[cnd].c = tree[pnd].c + 1;
    tree[cnd].val = tree[pnd].val + num[k];
    if(s == e) return;
    int m = s + e >> 1;
    if(k <= m) {
        tree[cnd].r = tree[pnd].r;
        tree[cnd].l = tree.size();
        tree.eb(0, 0, 0, 0LL);
        expand_tree(s, m, k, tree[pnd].l, tree[cnd].l);
    }
    else {
        tree[cnd].l = tree[pnd].l;
        tree[cnd].r = tree.size();
        tree.eb(0, 0, 0, 0LL);
        expand_tree(m+1, e, k, tree[pnd].r, tree[cnd].r);
    }
}

ll cal(int s, int e, int cnt, int pnd, int cnd) {
    if(s == e) return cnt * num[s];
    int m = s + e >> 1, rcnt = tree[tree[cnd].r].c - tree[tree[pnd].r].c;
    if(rcnt >= cnt) return cal(m+1, e, cnt, tree[pnd].r, tree[cnd].r);
    else {
        ll rval = tree[tree[cnd].r].val - tree[tree[pnd].r].val;
        return cal(s, m, cnt-rcnt, tree[pnd].l, tree[cnd].l) + rval;
    }
}

void dnc(int s, int e, int l, int r) {
    if(s > e) return;
    int idx = l, m = s + e >> 1;
    ll tans = -LINF;
    for(int i = l; i <= min(r, m - x + 1); i++) {
        ll temp = cal(1, n, x, root[i-1], root[m]);
        temp -= 2 * (arr[m].se - arr[i].se);
        if(temp > tans) {
            tans = temp;
            idx = i;
        }
    }
    ans = max(ans, tans);
    dnc(s, m-1, l, idx);
    dnc(m+1, e, idx, r);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    
    cin >> n >> x;
    num.eb(0);
    for(int i = 1; i <= n; i++) {
        cin >> arr[i].fi >> arr[i].se;
        num.eb(arr[i].fi);
    }
    sort(arr+1, arr+n+1, [](pll a, pll b) {
        if(a.se == b.se) return a.fi < b.fi;
        return a.se < b.se;
    });
    sort(all(num));
    
    tree.eb(0, 0, 0, 0);
    for(int i = 1; i <= n; i++) {
        int k = lower_bound(all(num), arr[i].fi) - num.begin();
        root[i] = tree.size();
        tree.eb(0, 0, 0, 0LL);
        expand_tree(1, n, k, root[i-1], root[i]);
    }

    dnc(1, n, 1, n);
    cout << ans;
}

 

2. mergers

예전에 풀었던 삼각분할과 비슷하면서도 달랐다. 우선 조건 때문에 분할은 무조건 간선으로 해야 한다는 사실을 알 수 있다. 이 때 해당 간선을 끊어도 분리된 두 트리에 어떤 색이 모두 존재하면 안 된다. 이 조건을 해결하기 위한 간단한 방법으로는, 색깔별로 정점을 구분한 뒤 하나씩 체인처럼 이어주는 행위를 하는 방법이 있다. 이렇게 할 경우 같은 색인 두 점 쌍에 대하여 항상 경로가 두 개 이상 존재한다. 즉, 그 두 선 사이에는 단절선이 생기지 않는다. 때문에 이렇게 해서 그래프를 변형한 뒤 단절선을 모두 구할 수 있다.

이제 단절선이 아닌 간선으로 연결되어 있는 것들은 union-find 등을 이용하여 하나로 합쳐주고 단절선만 남기자. 그러면 다시 트리가 만들어질 것이다. 이제 답은 해당 트리에서 [(리프 노드 개수 + 1) / 2]라는 것을 알 수 있다. POI subway에서 설명했던 것처럼 리프노드끼리만 병합하면 사이의 길은 모두 합쳐지고, 이러한 사이의 길은 항상 연결되어있도록 하는 것이 최적이기 때문이다. 그래서 다시 dfs를 한 다음에 리프 노드 개수를 구하고 답을 출력하면 된다.

 

코드

#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 = 505050;
const int INF = 1e9;
const ll LINF = 1e18;

vector <int> g[MAX], s[MAX], ng[MAX];
vector <pii> E;
int num[MAX], low[MAX], cnt = 0, p[MAX], ans = 0;

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

void uni(int x, int y) {
    x = find(x), y = find(y);
    if(x > y) swap(x, y);
    p[y] = x;
}

void dfs(int x, int pa) {
    low[x] = num[x] = ++cnt;
    bool flag = false;
    for(auto i : g[x]) {
        if(i == pa && !flag) {
            flag = true;
            continue;
        }
        if(num[i] != 0) low[x] = min(low[x], num[i]);
        else if(num[i] == 0) {
            dfs(i, x);
            low[x] = min(low[x], low[i]);
        }
    }
    for(auto i : g[x]) {
        if(i == pa) continue;
        if(low[i] > num[x]) E.eb(i, x);
        else uni(i, x);
    }
}

void ndfs(int x, int pa) {
    int tcnt = 0;
    for(auto i : ng[x]) {
        if(i == pa) continue;
        ndfs(i, x);
        tcnt++;
    }
    if(tcnt == 0 && x != 1) ans++;
    if(tcnt == 1 && x == 1) ans++;
}

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

    int n, k;
    cin >> n >> k;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].eb(v), g[v].eb(u);
    }
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        int u; cin >> u;
        s[u].eb(i);
    }
    for(int i = 1; i <= k; i++) {
        for(int j = 1; j < s[i].size(); j++) {
            g[s[i][j-1]].eb(s[i][j]);
            g[s[i][j]].eb(s[i][j-1]);
        }
    }
    dfs(1, 0);
    for(auto i : E) {
        ng[find(i.fi)].eb(find(i.se));
        ng[find(i.se)].eb(find(i.fi));
    }
    ndfs(1, 0);
    cout << (ans + 1) / 2;
}

 

3. minerals

이건 문제를 안 봤다. 백준에도 없고 인터랙티브인 것 같아 귀찮아서 안 풀었다.