Category: Competitive Programming

올해는 예년보다 문제들이 쉬워진 느낌이었습니다. 다섯 문제를 전부 풀었습니다.

제 풀이를 공유합니다.

1차 1번 – 친구들

사람이 $N \leq 100\,000$명 있습니다.

번호 $i$인 사람은 수 $D_i$를 갖고 있는데, $i + D_i \leq N$라면 $i$번 사람과 $i + D_i$번 사람은 친구입니다. 또, 친구의 친구는 친구입니다.

이 때, ‘극대 그룹’의 수를 찾아야 합니다.

친구 관계를 그래프로 생각해 봅시다. ‘친구의 친구가 친구‘라는 말을 잘 생각해 보면, 어떤 연결 요소 안의 모든 사람들은 서로 친구가 됩니다.

따라서 DFS/BFS 여러 번을 통해 연결 요소의 수를 세 주면 문제의 답이 됩니다. 또는 DSU^{disjoint set union}를 사용해도 됩니다. DFS/BFS를 사용하면 $\mathcal{O}\left(N\right)$만에 해결할 수 있습니다.

저는 DSU를 사용해서 풀었습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

int dsu[100001];

int find(int u) {
    return dsu[u] == u ? u : (dsu[u] = find(dsu[u]));
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u != v) dsu[v] = u;
}

void solve() {
    int n;
    cin >> n;

    iota(dsu + 1, dsu + 1 + n, 1);

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (i + x > n) continue;
        merge(i, i + x);
    }

    set<int> s;
    for (int i = 1; i <= n; i++) s.emplace(find(i));
    cout << s.size() << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

DSU를 만들 때 std::iota라는 좋은 함수를 사용하면 쉽고 빠르게 초기화할 수 있습니다. STL에 이런 함수가 있다는 게 좀 의외일까요?

1차 2번 – 이진수

길이가 $n \leq 50\,000$인 비트 문자열 $a$가 있고, 같은 길이의 비트 문자열 $b$를 다음과 같이 정의합니다. $\vee$는 OR 연산입니다.

\[b_i = \left(a_{i-t} \vee a_{i+t}\right)\]

$b$가 주어지면, 사전순으로 제일 앞서는 $a$를 구해야 합니다.

약간 헤멜 수 있는 문제였던 것 같습니다. 일단 두 가지 사실을 기반으로 생각해봅시다.

• $b_i$가 켜져 있다면, $a_{i-t}$ 또는 $a_{i+t}$가 켜져 있어야 합니다.
• $a_i$가 켜져 있다면, $b_{i-t}$와 $b_{i+t}$가 모두 켜져 있어야 합니다.

이제 $b_i$를 왼쪽부터 보면서, 켜져 있으면서 아직 $a_{i-t}$와 $a_{i+t}$ 모두가 꺼져 있는 $b_i$들에 대해, 그리디하게 $a$의 비트들을 켜 줍니다.

• 오른쪽($a_{i+t}$) 비트를 켤 수 있으면 켜 줍니다. 오른쪽 비트를 켤 수 있으려면, $b_{i+2t}$가 존재하지 않거나 켜져 있어야 합니다. 이는 사전 순으로 가장 먼저 오는 $a$를 구성하기 위함입니다.
• 오른쪽 비트를 켤 수 없다면 왼쪽($a_{i-t}$) 비트를 켜 줍니다.

생각해 보면 모든 $b_i$에 대해 둘 중 하나 이상을 켤 수 있는 경우만 입력으로 주어진다는 사실을 알 수 있습니다. 이를 그대로 구현해 주면 됩니다. $\mathcal{O}\left(n\right)$만에 해결할 수 있습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

void solve() {
    int n, t;
    cin >> n >> t;

    string b;
    cin >> b;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        if (b[i] == '0') continue;
        int l = i - t, r = i + t;
        if ((l >= 0 && a[l]) || (r < n && a[r])) continue;

        int ll = l - t, rr = r + t;
        if (r < n) {
            if (rr >= n || b[rr] == '1') {
                a[r] = 1;
                continue;
            }
        }
        if (l >= 0) {
            if (ll < 0 || b[ll] == '1') {
                a[l] = 1;
                continue;
            }
        }
    }
    for (int i = 0; i < n; i++) cout << a[i];
    cout << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

1차 3번 – No Cycle

정점 $N \leq 500$개, 간선 $M+K$개의 그래프가 있습니다. $M+K$의 간선 중 $M \leq 2\,000$개는 방향이 있고, $K \leq 2\,000$개는 방향이 정해지지 않았습니다.

이 때 $K$개의 간선들의 방향을 잘 정해서, 사이클이 없는 그래프를 구성하고 싶습니다. 방향이 정해진 $M$개의 간선들만 있는 경우에는 사이클이 없는 상태입니다.

답은 $K$글자의 비트 문자열입니다. 방향이 없는 $i$번째 간선의 입력이 $\textcolor{#ff3b57}{u}$ $\textcolor{#ffb717}{v}$로 주어졌을 때, $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$로 방향을 정했다면 $0$, $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$로 방향을 정했다면 $1$입니다. 이 때 사전 순으로 가장 앞서는 비트 문자열을 출력해야 합니다.

사이클이 없는 방향 그래프에서, 임의의 정점 $\textcolor{#ff3b57}{u}$와 $\textcolor{#ffb717}{v}$를 고르고 그 정점을 잇는 간선을 추가한다고 생각해 봅시다. $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$로 정할 수도 있고 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$로 정할 수도 있습니다. 두 경우 모두가 사이클을 만드는 경우가 있을까요?

$\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$라는 간선을 추가했을 때 사이클이 생긴다는 것은, $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$로 가는 경로가 이미 존재한다는 사실과 동치입니다.

따라서 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$도 사이클을 만들고 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$도 사이클을 만든다면, 각각 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$라는 경로와 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$라는 경로 모두가 이미 존재해야 됩니다.

하지만 그런 두 개의 경로가 이미 존재한다면, 그 두 개의 경로만으로 사이클을 만들 수 있습니다. 이는 우리가 처음에 한 가정 — 사이클이 없는 방향 그래프 — 에 모순됩니다. 따라서 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$와 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$ 중 적어도 하나는 새로운 사이클을 만들지 않는다는 사실을 알 수 있습니다.

그러므로 이미 사이클이 없는 방향 그래프라면, 간선들을 무한정 추가해줄 수 있습니다. 그래프의 정점과 간선의 수가 작기 때문에, 간선을 추가해줄 때마다 사이클이 생기는지 생기지 않는지 확인하면서 간선을 하나씩 추가해나갈 수 있습니다.

사전 순으로 가장 앞서는 비트 문자열을 구성해야 하므로, 우선 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$를 추가한 뒤 사이클이 안 생긴다면 그대로 가져갑니다. 사이클이 생긴다면 위의 증명을 통해 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$를 추가해줄 수 있음이 보장된다는 것을 알 수 있으므로, 그렇게 해 줍니다.

사이클의 존재 여부를 판단하는 방법은 여러 가지가 있습니다. 저는 DFS로 구현했습니다. 그래프가 연결 그래프임은 보장되지 않으므로, 방문하지 않은 모든 정점에서 DFS를 시작해야 함에 유의합니다.

간선을 $K$개 추가해 주고, 추가할 때마다 DFS를 한 번 해야 하므로 $\mathcal{O}\left(K\left(N+K+M\right)\right)$의 시간이 걸립니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

bitset<501> root;
int vis[501], ans[2000];

bool dfs(int u, const vector<vector<int>> &graph) {
    // check for cycles
    if (vis[u]) return vis[u] == -1;
    vis[u] = -1;
    for (int v : graph[u]) {
        if (dfs(v, graph)) return true;
    }
    vis[u] = 1;
    return false;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    root.reset(), root.flip();

    vector<vector<int>> graph(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace_back(v);
    }
    
    for (int i = 0; i < k; i++) {
        int u, v;
        cin >> u >> v;

        // 0?
        graph[u].emplace_back(v);
        memset(vis, 0, sizeof vis);
        bool flag = true;
        for (int x = 1; x <= n; x++) {
            if (vis[x]) continue;
            if (dfs(x, graph)) {
                flag = false;
                break;
            }
        }
        ans[i] = !flag;
        if (flag) continue;
        
        // 1?
        graph[u].pop_back();
        graph[v].emplace_back(u);
    }

    for (int i = 0; i < k; i++) cout << ans[i];
    cout << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

1차 4번 – 예약 시스템

$2 \times m$개의 방이 있는 호텔이 있습니다. $m \leq 50\,000$입니다.

$n\leq 20\,000$개 그룹의 투숙객들이 호텔에 묵으려 합니다. 각 그룹의 크기는 $5$ 이상이고, 한 명이 한 개의 방에 묵습니다.

모든 투숙객들은 스트레스 지수 $w_i$를 갖고 있어서, 인접한 방에 다른 그룹의 투숙객이 있고 그 투숙객의 스트레스 지수가 $w_j$라면, 그 쌍에 대해 $w_i + w_j$만큼의 충돌이 발생합니다. 모든 쌍에 대해 충돌의 합을 최소화하고 싶습니다.

(그냥 이렇게 설명하면 끝나는 문제인데, SCPC 운영진은 디스크립션을 어렵게 쓰는 재주가 있는 걸까요?)

SCPC의 서브태스크는 보통은 만점 풀이와는 무관한 브루트포스 풀이를 요구하는 경향이 있는데, 이 문제는 서브태스크 순서대로 생각해 보면 정해 풀이까지 다다를 수 있는 문제였다고 생각합니다.

문제를 처음 읽으면 어떻게 배치해야 될지 조차 감이 오지 않지만 서브태스크가 그룹 크기가 홀수 또는 짝수인 경우로 나뉘어 있다는 점에서 착안해 아래와 같은 접근을 시작할 수 있었습니다.

서브태스크 1: 그룹이 모두 짝수인 경우

우선 그룹의 크기 $l_i$가 모두 짝수일 때의 경우, 최적의 배치가 어떻게 되는지 생각해 봅시다. 다른 그룹과 ‘닿는’ 부분이 최소화되면 좋을 것 같습니다. 그런 배치는 아래 그림과 같이, $2 \times \frac{l_i}{2}$ 직사각형들을 이어 붙인 경우가 됩니다.

이 때 핑크색으로 칠한 부분에서 충돌이 일어납니다.

그룹의 순서가 정해져 있을 때 충돌의 합을 최소화하려면, 첫 번째 그룹과 마지막 그룹에서는 제일 작은 원소 $2$개씩을 고르고, 나머지 그룹에서는 제일 작은 원소 $4$개씩을 고르면 됩니다.

다르게 생각한다면 모든 그룹에서 제일 작은 원소 $4$개씩을 고른 후, 두 개의 그룹에서만 $3$번째로 작은 원소와 $4$번째로 작은 원소 하나씩을 빼 주면 됩니다.

$i$번째 그룹에서 $j$번째로 작은 원소를 $m_{i,j}$라고 합시다. 그러면 모든 그룹을 $m_{i,3}+m_{i,4}$ 순으로 정렬한 후, $\sum_i \left(m_{i,1}+m_{i,2}+m_{i,3}+m_{i+4}\right)$에서 $m_{i,3}+m_{i,4}$가 제일 큰 두 그룹만 빼 주면 정답입니다.

서브태스크 2: 그룹이 모두 홀수인 경우

짝수인 경우와 비슷하게 배치해줄 수 있습니다.

이 경우에는 충돌이 조금 더 많이 생기긴 합니다만, 짝수의 경우와 비슷하게 접근할 수 있습니다.

우선 각 그룹마다 두 번씩 충돌이 일어나는 원소가 하나 있는데, 이를 그 그룹에서 가장 작은 원소로 둡시다. 그러면 모든 그룹에서 제일 작은 원소 $4$개씩을 고른 후, 두 개의 그룹에서만 $3$번째로 작은 원소와 $4$번째로 작은 원소 하나씩을 빼 주면 되는 것은 동일합니다만, 가장 작은 원소는 한 번 더 더해줘야 합니다.

다시 말하면 모든 그룹을 $m_{i,3}+m_{i,4}$ 순으로 정렬한 후, $\sum_i \left(\textcolor{#ff3b57}{2m_{i,1}}+m_{i,2}+m_{i,3}+m_{i+4}\right)$에서 $m_{i,3}+m_{i,4}$가 제일 큰 두 그룹만 빼 주면 정답입니다.

서브태스크 3: 짝수 그룹과 홀수 그룹이 섞여 있는 경우

위에서의 접근을 바탕으로, 크게는 $3$가지 경우로 나눠 생각할 수 있습니다.

• 짝수 그룹과 홀수 그룹이 하나 이상씩 있다면, 맨 왼쪽 그룹과 맨 오른쪽 그룹에 짝수 그룹 하나와 홀수 그룹 하나씩이 있는 경우
• 짝수 그룹의 개수가 $2$개 이상이라면, 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 짝수 그룹인 경우
• 홀수 그룹의 개수가 $2$개 이상이라면, 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 홀수 그룹인 경우

3a: 맨 왼쪽 그룹과 맨 오른쪽 그룹에 짝수 그룹 하나와 홀수 그룹 하나씩이 있는 경우

먼저 홀수 그룹들을 전부 왼쪽에 배치하고, 나머지 짝수 그룹들을 전부 오른쪽에 배치합시다.

짝수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 하나와, 홀수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 하나를 골라서 빼 주면 됩니다.

3b: 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 짝수 그룹인 경우

위의 경우와 비슷합니다. 오른쪽에 있는 짝수 그룹들 중 하나를 빼다가 맨 왼쪽에 붙이면 됩니다.

짝수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 두 개를 골라서 빼 주면 됩니다.

3c: 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 홀수 그룹인 경우

이 경우는 약간 까다롭습니다.

일단 홀수 그룹 두 개를 잘 합치면 직사각형을 만들 수 있다는 점에서 착안해 아래와 같은 배치를 생각할 수 있습니다.

이 경우, 홀수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 두 개를 골라서 빼 주면 됩니다.

하지만 이런 경우는 홀수 그룹이 $4$개 이상인 경우에만 만들 수 있습니다. 홀수 그룹이 $2$개라면 어쩔 수 없이 아래와 같은 경우로 구성해야 합니다.

이 경우에는, 짝수 그룹들에서 $\sum_i \left(\textcolor{#ff3b57}{2m_{i,1}}+\textcolor{#ff3b57}{2m_{i,2}}+m_{i,3}+m_{i+4}\right)$를 해 줘야 합니다. 홀수 그룹이 $2$개인 경우에만 특수하게 처리해줍시다.

모든 경우를 고려한 코드는 아래와 같습니다. 정렬이 필요하기 때문에 $\mathcal{O}\left(n \log n\right)$만큼의 시간이 걸립니다. 사실 제일 큰 두 개 그룹만 구해도 상관없기 때문에, 잘 짠다면 $\mathcal{O}\left(n\right)$도 가능하지만요.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

int a[100000];
pii p[20000];

void solve() {
    int n, m;
    cin >> n >> m;

    ll s = 0, sa = 0;
    ll oc = 0, ec = 0;

    for (int i = 0; i < n; i++) {
        int l;
        cin >> l;
        for (int j = 0; j < l; j++) cin >> a[j];
        sort(a, a + l);
        ((l & 1) ? oc : ec)++;
        p[i].first = a[2] + a[3];
        p[i].second = (l & 1);
        s += (1 + (l & 1)) * a[0] + a[1] + a[2] + a[3];
        sa += 2 * a[0] + (2 - (l & 1)) * a[1] + a[2] + a[3];
    }

    sort(p, p + n, greater<>());

    if (oc && ec) {
        ll coe = 0, coo = 0, cee = 0;

        // coe: o o .. o e .. e e
        int o = 0, e = 0;
        for (int i = 0; i < n; i++) {
            if (!o && p[i].second) {
                coe += p[i].first;
                o++;
            }
            if (!e && !p[i].second) {
                coe += p[i].first;
                e++;
            }
            if (o && e) break;
        }

        // coo: o o .. o e .. e o .. o o
        if (oc >= 2) {
            o = 0;
            for (int i = 0; i < n; i++) {
                if (o < 2 && p[i].second) {
                    coo += p[i].first;
                    o++;
                }
                if (o >= 2) break;
            }
        }

        // cee: e e .. e o .. o e .. e e
        if (ec >= 2) {
            e = 0;
            for (int i = 0; i < n; i++) {
                if (e < 2 && !p[i].second) {
                    cee += p[i].first;
                    e++;
                }
                if (e >= 2) break;
            }
        }

        vector<ll> cd;
        cd.emplace_back(s - coe);
        cd.emplace_back(sa - coo);
        cd.emplace_back(s - cee);
        if (oc >= 4) cd.emplace_back(s - coo);

        s = *min_element(cd.begin(), cd.end());
    } else {
        s -= p[0].first + p[1].first;
    }

    cout << s << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

$s$는 다음의 합입니다.

\[s=\sum_i \begin{cases}m_{i,1}+m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is even}\\ 2m_{i,1}+m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is odd}\end{cases}\]

$sa$는 홀수 그룹이 $2$개인 경우 특수 처리를 해 주기 위한 값으로서 다음의 합입니다.

\[sa=\sum_i \begin{cases}2m_{i,1}+2m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is even}\\ 2m_{i,1}+m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is odd}\end{cases}\]

배열 $p$에는 모든 그룹들에 대해 홀/짝 정보와 $m_{i,3}+m_{i,4}$ 정보를 저장해 두고 정렬했습니다.

여담

이 문제는 오후 7시 33분에 한 번 수정되었습니다.

예약 시스템 문제에서 조건이 하나 빠져 있었습니다. 아래와 같이 명시했고, 제출 횟수를 20회로 늘릴 것입니다.

– 한 집합에 속한 예약자들은 모두 한 덩어리의 방들을 배정 받아야 한다. 한 덩어리의 방들이란 덩어리에 속한 어떤 방 두개에 대해서도, 덩어리에 속하고 인접한 방들을 통해서 이동이 가능하다는 의미이다.

그런 말이 쓰여 있지는 않았지만, 운이 좋게도? 당연히 연결 요소여야 최소일 것이라고 생각하고 풀었고, 문제를 맞을 수 있었습니다. 연결 요소가 아니어도 괜찮았을 경우, 다음과 같은 반례가 있습니다.

1
5 14
6 1 1 1 1 1 1
6 2 2 2 2 2 2
6 2 2 2 2 2 2
5 10 10 10 10 10
5 10 10 10 10 10

이 경우 아래와 같은 구성이 가능합니다.

이 때 답은 $84$입니다.

1차 5번 – 차이

$100\,000$개 이하의 미지수 $X_i$들에 대해 다음 쿼리들을 수행해야 합니다. 쿼리의 수는 $200\,000$개 이하입니다.

• 1 i j d: $X_i + d = X_j$라는 조건을 추가합니다.
• 2 i j: $X_i-X_j$를 출력합니다. 조건이 모순된다면 CF를, 주어진 조건들만으로 알 수 없다면 NC를 출력합니다.

$d$가 없다면 간단한 DSU 문제입니다. 이걸로 서브태스크 1과 3을 쉽게 해결할 수 있습니다.

DSU 트리의 간선들에 가중치가 있다고 생각한다면 서브태스크 2와 4를 해결할 수 있습니다.

우리가 DSU 쿼리를 $\mathcal{O}\left(\alpha\left(N\right)\right)$만에 할 수 있는 이유는 경로 압축^{path compression}이라는 좋은 테크닉이 있어서입니다. $p_u$가 노드 $u$의 부모 노드라고 한다면, $u$의 루트를 구하는 함수 $\mathrm{find}$에서 경로 압축은 다음과 같이 재귀적으로 수행했습니다.

\[\mathrm{find}\left(u\right) = \begin{cases} u & \text{if } u=p_u \\ p_u \leftarrow \mathrm{find}\left(p_u\right) & \text{otherwise} \end{cases}\]

이렇게 하면 $u$에서 $u$의 루트 $r$로 가는 경로 위에 있는 모든 정점들의 부모가 아예 $r$로 바뀌어 버리게 됩니다.

현재 노드 $u$에서 부모 노드 $p_u$로 가는 비용을 $d_u$라고 합시다. 그러면 $d_u$도 비슷한 방법으로 압축해버릴 수 있습니다.

$\mathrm{find}$ 함수를 돌릴 때 $u$의 부모 노드는 $p_u$였고, $p_u$의 부모 노드는 $r$이었습니다. 따라서 $u$에서 $r$까지 가는 데는 $d_u + d_{p_u}$만큼의 비용이 필요합니다. $\mathrm{find}$ 함수에서 경로 압축을 수행하면서, $d_u$를 $d_u + d_{p_u}$로 업데이트해 주면 됩니다. 이제 가중치가 있는 DSU 트리에서도 경로 압축을 할 수 있습니다.

1번 쿼리와 2번 쿼리 모두 $\mathcal{O}\left(\alpha\left(N\right)\right)$만큼의 시간이 걸립니다. 총 시간 복잡도는 $\mathcal{O}\left(K\alpha\left(N\right)\right)$입니다.

$\alpha$는 역 아커만 함수^{inverse Ackermann function}이며, $\alpha\left(2^{2^{2^{65536}}}-3\right)=4$ 정도로 작기 때문에 상수라고 생각해도 무방합니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

int dsu[100001], conf[100001];
ll val[100001]; // [u] + val[u] = [dsu[u]]

int find(int u) {
    if (dsu[u] == u) return u;
    int pp = find(dsu[u]);
    val[u] += val[dsu[u]], dsu[u] = pp;
    return pp;
}

bool merge(int u, int v, ll x) {
    // [u] + x = [v]
    if (find(u) == find(v)) {
        if (val[u] + x != val[v]) {
            conf[find(u)] = true;
            return false;
        }
        return true;
    }

    int pu = find(u);
    x += val[u];
    int pv = find(v);
    x -= val[v];
    u = pu, v = pv;
    val[u] = val[v] - x, dsu[u] = v;
    conf[v] |= conf[u];
    return true;
}

void solve() {
    int n, q;
    cin >> n >> q;

    iota(dsu + 1, dsu + n + 1, 1);
    memset(conf, 0, sizeof conf);
    memset(val, 0, sizeof val);

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i, j, d;
            cin >> i >> j >> d;
            merge(i, j, -d);
        } else {
            int i, j;
            cin >> i >> j;
            int pi = find(i), pj = find(j);
            if (pi != pj) {
                cout << "NC\n";
            } else if (conf[pi]) {
                cout << "CF\n";
            } else {
                cout << val[i] - val[j] << '\n';
            }
        }
    }

    cout.flush();
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

conf는 모순이 발생했는지 여부를 저장하는 배열입니다. find 함수가 항상 루트를 찾아주기 때문에, conf 플래그도 맨 위에만 달면 충분합니다.

긴 시간 문제 푸시느라 모두 수고하셨습니다. 라운드 2에서 만납시다!

• 1차 예선 풀이

2차 예선에서 1, 2, 3, 5번을 풀어서 1,000점 만점에 750점을 받았습니다.

4번 문제보다 5번이 구현이 쉬워 보여서 5번을 먼저 해결했습니다. 이후 부분 점수를 보니 1번 + 2번 + 3번 + 4번 + 5번 47점 = 747점이었고, 이는 1번 + 2번 + 3번 + 5번 = 750점보다 적은 점수여서, 27위 안에 들었음을 확신하고 4번을 느긋하게 건들어 보다가 포기했습니다.

제 2차 1, 2, 3, 5번 풀이를 공유합니다. 4번 문제는 구현하지 않아서, 대략적인 아이디어만 갖고 있습니다.

2차 1번 – 실력 맞추기

각각 $N \leq 300\ 000$명의 멤버가 있는 A팀과 B팀이 있습니다. 멤버들은 각각의 실력 값을 갖고 있습니다. 이 때, A의 멤버를 최대 한 명까지 교체해서, A팀의 멤버 한 명과 B팀의 멤버 한 명씩을 매칭했을 때 전체 매칭의 실력 차의 합이 최소가 되게 하고 싶습니다.

두 가지 관찰을 할 수 있습니다.

• A팀에서 멤버 교체가 일어나지 않는 경우에는, A팀의 실력 값과 B팀의 실력 값을 각각 정렬해서 큰 순서대로 한 명씩 매칭해주는 것이 최적임은 자명합니다.
• 한 명을 교체하는 경우에는, 어떻게 교체하더라도 어떤 B팀 멤버가 있어서 그 멤버의 실력과 같도록 교체해 주는 것이 무조건 이득입니다. 그리고 이 경우 새롭게 매칭된 멤버들의 실력 차는 $0$입니다.

따라서 A팀에서 한 명을 교체한다기보다는, A팀과 B팀에서 한 명씩을 제외하고 나머지를 적절히 매칭하는 것을 생각할 수 있습니다. 이를 해결하기 위해 A팀과 B팀을 각각 정렬해 두고, 다음과 같은 다이나믹 프로그래밍을 생각할 수 있습니다.

• $dp\left(i,0\right)$: A팀과 B팀의 $\left[0, i\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
  따라서 $dp\left(i,0\right) = dp\left(i-1,0\right) + \left|A_i-B_i\right|$입니다.
• $dp\left(i,1\right)$: A팀 한 명을 제외하고, A팀의 $\left[0, i\right]$과 B팀의 $\left[0, i – 1\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
  따라서 $dp\left(i,1\right) = \min\left\{ dp\left(i-1,0\right), dp\left(i-1,1\right) + \left|A_i-B_{i-1}\right| \right\} $입니다.
• $dp\left(i,2\right)$: B팀 한 명을 제외하고, A팀의 $\left[0, i – 1\right]$과 B팀의 $\left[0, i\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
  따라서 $dp\left(i,2\right) = \min\left\{ dp\left(i-1,0\right), dp\left(i-1,2\right) + \left|A_{i-1}-B_i\right| \right\} $입니다.
• $dp\left(i,3\right)$: A팀과 B팀 중 각각 한 명씩을 제외하고, A팀과 B팀의 $\left[0, i\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
  따라서 $dp\left(i,3\right) = \min\left\{ dp\left(i-1,3\right), dp\left(i-1,1\right), dp\left(i-1,2\right) \right\}$입니다.

이를 전부 계산하고 나면, 정답은 $dp\left(n,0\right)$과 $dp\left(n,3\right)$ 중 작은 쪽이 됩니다. 저는 1-based index를 사용해 구현했습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

int a[200001], b[200001];
ll dp[200001][4];

const ll inf = 1e18;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;

        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + n);

        dp[1][0] = abs(a[1] - b[1]);
        dp[1][1] = 0; // ignore a[i - 1]
        dp[1][2] = 0; // ignore b[i - 1]
        dp[1][3] = 0;

        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] + abs(a[i] - b[i]);
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1] + abs(a[i] - b[i - 1])); // ignore a[i - 1]
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][2] + abs(a[i - 1] - b[i])); // ignore b[i - 1]
            dp[i][3] = min({dp[i][1], dp[i][2], dp[i - 1][3] + abs(a[i] - b[i])});
        }

        cout << min(dp[n][0], dp[n][3]) << endl;
    }

    return 0;
}

2차 2번 – 고구마

고구마 $N\leq 300\ 000$개가 일렬로 길게 연결되어 있습니다. 각 고구마의 가격은 $-10^{12} \leq A_i \leq 10^{12}$로 정해져 있습니다. 음수는 상품가치가 없어 발생하는 처리 비용입니다.

$M$만큼의 예산이 있어, 연결되어 있는 고구마 덩어리를 적절히 잘라 중간 덩어리를 사 가려고 합니다. 덩어리의 크기는 중요하지 않으나, 한 덩어리만 사갈 수 있습니다. 이 때 고구마를 적절히 잘라서, 예산 $M$을 넘지 않으면서 최대한 비싸게 사가고 싶습니다.

요약하면, 최대 구간합^{maximum subarray sum} 문제인데, 합이 $M$보다 작거나 같으면서 최대한 큰 경우를 찾아야 합니다.

제한조건 때문에, 선형 시간에 최대 구간합 문제를 해결하는 Kadane’s 알고리즘은 사용할 수 없습니다. 다만 최대 구간을 구해야 한다는 점에서 구간합 배열^{prefix sum array}을 이용해 접근해볼 수 있습니다.

구간합 배열 $P$를 만든 후, 현재 보고 있는 인덱스가 $i$라면, $P_i-P_j \leq M$이면서 $j < i$에 대해 $P_i-P_j$의 최댓값을 구해 주면 됩니다. 이는 std::set 자료 구조에 이전 인덱스까지의 구간합들을 전부 집어넣고, $\mathcal{O}\left(\log n\right)$이 걸리는 std::set::lower_bound을 사용해 쉽게 해결할 수 있습니다. 이유는 모르겠지만 저는 대회 당시에는 std::set::upper_bound를 사용해 구현했습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;

        int n;
        ll m;
        cin >> n >> m;

        set<ll> s;
        s.emplace(0);
        ll mx = 0, prf = 0;
        for (int i = 0; i < n; i++) {
            ll x;
            cin >> x;
            prf += x;
            s.emplace(prf);
            ll v = *s.upper_bound(prf - m - 1);
            mx = max(mx, prf - v);
        }

        cout << mx << endl;
    }

    return 0;
}

2차 3번 – 아르바이트

안타깝게도 디스크립션이 정확히 기억나진 않는데요, $N \leq 200\ 000$ 크기의 배열 $A$가 주어지고, 특정 인덱스의 값을 바꾸는 연산을 $Q\leq 2\ 000$번 하려고 합니다. 이 때 각각의 연산마다 $A$의 길이 $K \leq \min\left\{200,N\right\}$의 모든 부분 배열의 구간합에 대해, 이들의 중앙값을 구해야 합니다. 단 가능한 부분 배열의 개수가 짝수 개라면, 중앙에 있는 두 값 중 더 큰 값을 구해야 합니다.

계속 변화하는 중앙값을 구해야 하는 문제로 BOJ 1572번이 있습니다. 이 문제의 경우 저는 크기가 같은 std::multiset을 두 개 만들어 두고, 한 쪽의 집합의 모든 원소가 다른 쪽의 집합의 모든 원소보다 작도록 유지해두는 방식으로 해결했습니다. 제 1572번 소스 코드는 여기에서 볼 수 있습니다.

원래 배열에 대한 생각은 접어 두고, 구간합들이 저장된 배열이 있다고 생각해 봅시다. 원래 배열에서 한 개의 원소가 바뀌면 구간합 배열에서는 최대 $K$개의 원소가 바뀝니다. $K \leq \min\left\{200,N\right\}$라는 조건 때문에, 전부 나이브하게 처리해 줘도 최대 $KQ \leq 400\ 000$번밖에 바뀌지 않으니 위와 같은 방법으로 열심히 짜면 맞을 수 있을 것이라 생각했고, 시간 초과를 받았습니다.

std::multiset의 삽입/삭제 연산의 복잡도는 $\mathcal{O}\left(\log n\right)$이지만, 상수가 크기 때문에 사용에 주의를 요합니다. 상수 커팅을 위해 다소 특이할 수 있는 세그먼트 트리를 생각해내 해결했습니다.

BOJ 1572번의 해법과 비슷하게, $mxt$와 $mnt$라는 세그먼트 트리를 각각 만들었습니다. $mxt$는 최댓값 세그먼트 트리, $mnt$는 최솟값 세그먼트 트리이며, 항상 $\max mxt \leq \min mnt$가 되도록 관리합니다. 그런데 이렇게 관리하려면, 만약 $\max mxt > \min mnt$일 때 $mxt$의 최댓값을 $mnt$의 최솟값과 바꿔 줘야 하고, 또한 특정 인덱스 $i$에 대해 값 업데이트도 가능해야 합니다.

이를 위해 트리의 노드에는 최대/최솟값과, 그 최대/최솟값이 들어 있는 배열에서의 인덱스를 저장하도록 했습니다. 또한, 랜덤 액세스를 쉽게 하기 위해, 두 세그먼트 트리의 크기는 $N-K+1$로 고정해 두고, 노드에 저장된 값이 $-1$인 경우 이 트리의 이 인덱스에 값이 존재하지 않음을 의미하도록 했습니다.

정해인지는 잘 모르겠습니다. 어떻게 잘 하면 느리게 갱신^{lazy propagation}하는 테크닉을 섞어서 좀 더 빠르게 할 수도 있을 것 같기도 한데, 아래 코드도 만점을 받아서 더 이상 생각을 하지 않기로 했습니다.

들리는 말로는 크기 $NK$의 펜윅 트리로도 해결할 수 있다고 합니다. 하긴 펜윅이 빠르긴 빠르니까요.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

struct node {
    int i, v;

    node() : i(0), v(0) {}

    node(int i, int v) : i(i), v(v) {}

    bool operator<(const node &rhs) const {
        return v < rhs.v;
    }
};

node mnt[524288], mxt[524288];
int a[200001], val[200001], vals[200001];
ll prf[200001];
int tn, mxs, mns;

node minimum() { return mnt[1]; }

node maximum() { return mxt[1]; }

node argmin(const node &lhs, const node &rhs) {
    if (lhs.v == -1) return rhs;
    if (rhs.v == -1) return lhs;
    return min(lhs, rhs);
}

node argmax(const node &lhs, const node &rhs) {
    if (lhs.v == -1) return rhs;
    if (rhs.v == -1) return lhs;
    return max(lhs, rhs);
}

void setn(int i, int v, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e && s == i) {
        mnt[x].v = v;
        return;
    }
    if (i <= (s + e) / 2) {
        setn(i, v, x * 2, s, (s + e) / 2);
    } else {
        setn(i, v, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

void setx(int i, int v, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e && s == i) {
        mxt[x].v = v;
        return;
    }
    if (i <= (s + e) / 2) {
        setx(i, v, x * 2, s, (s + e) / 2);
    } else {
        setx(i, v, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
}

void update(int i, int dx, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e) {
        if (mxt[x].v != -1) mxt[x].v += dx;
        if (mnt[x].v != -1) mnt[x].v += dx;
        return;
    }
    if (i <= (s + e) / 2) {
        update(i, dx, x * 2, s, (s + e) / 2);
    } else {
        update(i, dx, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

void init(int x = 1, int s = 0, int e = tn - 1) {
    if (s == e) {
        mnt[x].i = mxt[x].i = s;
        if (s >= tn / 2) {
            mxt[x].v = -1, mnt[x].v = vals[s];
            mns++;
        } else {
            mnt[x].v = -1, mxt[x].v = vals[s];
            mxs++;
        }
        return;
    }
    init(x * 2, s, (s + e) / 2);
    init(x * 2 + 1, (s + e) / 2 + 1, e);
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

bool exchange() {
    const auto mx = maximum(), mn = minimum();
    if (mx.v <= mn.v) return false;
    // set mntree
    setn(mn.i, -1);
    setn(mx.i, mx.v);
    // set mxtree
    setx(mx.i, -1);
    setx(mn.i, mn.v);
    return true;
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;

    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;

        int n, k, q;
        cin >> n >> k >> q;
        tn = n - k + 1;

        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            prf[i] = prf[i - 1] + a[i];
        }

        for (int i = k; i <= n; i++) {
            val[i - k + 1] = prf[i] - prf[i - k]; // [1, n - k + 1]
            vals[i - k] = val[i - k + 1];
        }

        init();
        while (exchange());

        cout << minimum().v << ' ';
        while (q--) {
            int i, v;
            cin >> i >> v;
            int d = v - a[i];
            for (int j = max(0, i - k); j < min(i, tn); j++) {
                update(j, d);
            }
            while (exchange());
            cout << minimum().v << ' ';
            a[i] = v;
        }
        cout << endl;
    }

2차 4번 – 안전운전

도로의 왼쪽, 오른쪽 경계와 운전 경로가 주어집니다. 도로 정보와 운전 경로는 선분들로 이루어져 있으며, 각각 $x$축 또는 $y$축과 평행합니다. 이 때, 운전 경로 중 특정한 가로선 하나 이하에 대해, 그 이후의 경로를 적절히 선대칭시켜서, 도로 안에 포함된 운전 경로의 세로선들의 길이의 합이 최대가 되게 하고 싶습니다. 단, 선대칭 이후의 도로 경로가 더 길어져서는 안 됩니다.

좌표 압축 후 위에서부터 아래로 내려오면서 스위핑 or 1차 4번과 비슷한 식의 세그먼트 트리를 이용하면 풀릴 거라고 생각했습니다. 하지만 1, 2, 3, 5번을 해결한 시점에서 이미 2차 예선 26위 이상임이 확정되었기 때문에 구현하다 포기했습니다.

2차 5번 – 삼각형의 거리

꼭지점 $N \leq 300$개의 단순다각형^{simple polygon}이 있습니다. 오목할 수도 있습니다. 이 다각형의 꼭지점들을 이어 전부 삼각형으로 분할하고자 합니다.

어떤 삼각형에서 다른 삼각형과 맞닿은 변만을 통해 이동한다고 할 때, 삼각형 간의 거리를 정의할 수 있습니다. 예를 들어, 현재 삼각형과 맞닿아 있는 삼각형까지의 거리는 1이 됩니다. 처음 주어진 다각형을 잘 분할해서, 두 삼각형 사이의 최대 거리가 최소가 되도록 하고 싶습니다.

이 문제의 Small 셋의 경우, 다각형이 볼록다각형이므로 ICPC 2019 Korea Regional J번과 같은 문제입니다. 실제 대회에서 제가 First Solve로 해결했던 문제라 기억에 잘 남아 있던 것이 도움이 되었습니다.

다각형의 삼각 분할은 모든 노드의 $\deg \leq 3$인 트리로 나타낼 수 있습니다. 삼각 분할을 트리로 나타냈을 때, 이 트리의 지름을 최소화하는 문제가 됩니다.

주어진 도형을 어떤 대각선 하나로 자르면, 그 대각선 오른쪽에 만들어질 삼각형은 대각선 왼쪽에 만들 삼각형과 무조건 이어집니다. 이걸 바탕으로 2차원 다이나믹 프로그래밍을 생각해볼 수 있습니다. 현재 $i$번째 점 $P_i$부터 $j$번째 점 $P_j$까지만을 사용해 만든 도형이 있고, $\overline{P_iP_j}$는 어떤 다른 삼각형과 맞닿아있다고 생각해 봅시다. 한 쪽이 뚫려 있는 다각형이라고 생각하면 됩니다. 아래 그림의 핑크색 부분이 되겠네요.

이제 $dp \left(i,j\right)$를 핑크색 도형을 어떻게 잘 삼각분할했을 때 $\overline{P_iP_j}$에서 다른 삼각형까지의 최단 거리라고 정의합시다. 그러면 모든 $i<k<j$에 대해, 삼각형 $P_iP_jP_k$가 원래 다각형 안에 포함되는 경우 그 삼각형으로 분할한 뒤 재귀적으로 DP 문제를 해결할 수 있겠습니다.

따라서 $P_iP_jP_k$가 삼각형이 되는 모든 $i<k<j$들의 집합을 $K_{ij}$라 하면, 최단 거리는 $\overline{P_iP_k}$ 쪽에서 오거나 $\overline{P_kP_j}$ 쪽에서 오는 두 가지 경우가 있으므로, $dp\left(i,j\right)$는 다음과 같이 구할 수 있습니다.

\[dp\left(i,j\right)=\begin{cases} 0 & \textrm{if } i+1=j \\ \min_{k \in K_{ij}} \left\{ dp\left(i,k\right),dp\left(k,j\right) \right\}+1 & \textrm{otherwise} \end{cases}\]

하지만 이걸로는 트리의 지름을 구하기엔 역부족입니다. 왜냐하면, 이 다이나믹 프로그래밍의 경우 $\overline{P_iP_k}$에서 $\overline{P_iP_j}$ 쪽으로, $\overline{P_kP_j}$에서 $\overline{P_iP_j}$ 쪽으로 가는 건 고려하고 있지만, $\overline{P_iP_k}$에서 $P_iP_jP_k$를 거쳐 다시 $\overline{P_kP_j}$ 쪽으로 나가는 경로는 고려하지 못하고 있기 때문입니다.

점화식을 다시 정의해 봅시다. 어떤 값 $d$가 있어서, $dp_d \left(i,j\right)$를 다음과 같이 정의합니다.

\[dp_d\left(i,j\right)=\begin{cases} 0 & \textrm{if } i+1=j \\ \min_{k \in K_{ij}} \left\{ dp_d\left(i,k\right),dp_d\left(k,j\right) \right\}+1 & \textrm{if } dp_d\left(i,k\right)+dp_d\left(k,j\right) \leq d \\ \infty & \textrm{otherwise}\end{cases}\]

이제 이 점화식을 이용해 $dp_d\left(0,n-1\right)$를 구했고 그 값이 $\infty$가 아니라면, 트리의 지름이 $d$ 이하가 되도록 다각형을 삼각 분할할 수 있다는 뜻이 됩니다. 이제 이분 탐색으로 $d$의 최소값을 결정할 수 있습니다.

다이나믹 프로그래밍 한 번에 $\mathcal{O}\left(n^3\right)$이고, $0 \leq d \leq n-3$이므로 총 $\mathcal{O}\left(n^3 \log n\right)$만에 문제를 해결할 수 있습니다. 어떤 대각선이 오목다각형 안에 있는지 아닌지 판정하는 방법은 여러 가지가 있으나 문제의 포커스는 이게 아닌 것 같으므로 스킵하도록 합시다.

대회가 끝나고 안 사실인데 이 문제를 해결하는 논문이 있었다고 합니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

struct point {
    int x, y;

    point() : x(0), y(0) {}

    point(int x, int y) : x(x), y(y) {}

    point operator*(const int &rhs) const {
        return {x * rhs, y * rhs};
    }

    point operator+(const point &rhs) const {
        return {x + rhs.x, y + rhs.y};
    }

    point operator-(const point &rhs) const {
        return *this + (rhs * -1);
    }
};


int ccw(const point &a, const point &b, const point &c) {
    point bb = b - a, cc = c - a;
    ll t = (ll) bb.x * cc.y - (ll) cc.x * bb.y;
    return t ? (t > 0 ? 1 : -1) : 0;
}

bool intersects(const point &la, const point &lb, const point &ma, const point &mb) {
    if (ccw(la, lb, ma) * ccw(la, lb, mb) != -1) return false;
    if (ccw(ma, mb, la) * ccw(ma, mb, lb) != -1) return false;
    return true;
}

point A[300];

const int inf = 1e8;

int dp[300][300], dg[300][300];

bool diag(int i, int j, int n) {
    if (i > j) swap(i, j);
    if (dg[i][j] != -1) return dg[i][j];
    if (i == j || i + 1 == j) return dg[i][j] = false;
    if (i == 0 && j == n - 1) return dg[i][j] = false;

    for (int v = 0, u = n - 1; v < n; u = v++) {
        if (intersects(A[i], A[j], A[u], A[v])) return dg[i][j] = dg[j][i] = false;
    }

    point V1 = A[(i + 1) % n] - A[i], V2 = A[(i + n - 1) % n] - A[i], V3 = A[j] - A[i];
    ll a = (ll) V1.x * V2.y - (ll) V1.y * V2.x;
    ll b = (ll) V1.x * V3.y - (ll) V1.y * V3.x;
    ll c = (ll) V3.x * V2.y - (ll) V3.y * V2.x;
    bool in = (a >= 0 && b >= 0 && c >= 0) || (a < 0 && !(b < 0 && c < 0));
    if (!in) return dg[i][j] = dg[j][i] = false;
    return dg[i][j] = dg[j][i] = true;
}

int f(int i, int j, int d, int n) {
    if (i + 1 == j) return dp[i][j] = 0;
    if (!(i == 0 && j == n - 1) && !diag(i, j, n)) return dp[i][j] = inf;
    if (dp[i][j] != -1) return dp[i][j];

    dp[i][j] = inf;

    for (int k = i + 1; k < j; k++) {
        if (!(i + 1 == k || diag(i, k, n))) continue;
        if (!(k + 1 == j || diag(k, j, n))) continue;
        if (f(i, k, d, n) + f(k, j, d, n) > d) continue;
        dp[i][j] = min(dp[i][j], max(f(i, k, d, n), f(k, j, d, n)) + 1);
    }

    return dp[i][j];
}

bool sat(int d, int n) {
    memset(dp, -1, sizeof dp);
    return f(0, n - 1, d, n) != inf;
}

int g(int x) {
    if (x == 3) return 0;
    if (x == 4) return 1;
    if (x == 5) return 2;
    return g((x + 1) / 2) + 2;
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;

    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;

        int n;
        cin >> n;

        memset(dg, -1, sizeof dg);

        for (int i = 0; i < n; i++) {
            cin >> A[i].x >> A[i].y;
        }

        if (n == 3) {
            cout << 0 << endl;
            continue;
        }

        int l = g(n), h = n - 3;
        while (l < h) {
            int m = (l + h) / 2;
            if (sat(m, n)) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        cout << l << endl;
    }

    return 0;
}

회사 프로젝트에서 KaTeX를 한 번 사용해 본 이후로 제 블로그의 모든 수식을 KaTeX로 바꾸고 있습니다. 렌더 속도가 훨씬 빨라졌고, 모바일에서 수식 자동 줄바꿈이 잘 됩니다. 개인적으로는 여러 면에서 MathJax보다 좋은 라이브러리라고 생각합니다.

• 2차 예선 풀이

1차 예선에서 1, 2, 3, 4번을 풀어서 800점 만점에 600점을 받았습니다. 부분 점수는 안 못 받았습니다.

다음 날 수술이 있었고, 4번까지 풀고 나니 새벽이어서 5번은 안 풀고 잤습니다. 전체적으로 디스크립션이 난해한 느낌이라 안타까웠습니다.

제 1차 1, 2, 3, 4번 풀이를 공유합니다.

1차 1번 – 다이어트

A 식당과 B 식당이 있고, 이 식당에는 각각 $N \leq 50\ 000$개의 메뉴가 있습니다. 이 메뉴들의 칼로리 값들이 주어집니다. $K$일동안 매일 A에서 한 끼를, B에서 한 끼를 먹을 때, 하루에 먹은 칼로리의 양의 최댓값이 최소가 되게 하고 싶습니다.

A 식당에서의 최대 칼로리의 음식을 순서대로, B 식당에서 최소 칼로리의 음식을 순서대로 $K$일간 하나하나 그리디하게 매칭해 주면 됩니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

int a[200000], b[200000];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        int n, k;
        cin >> n >> k;

        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
        for (int i = 0; i < n; i++) cin >> b[i];
        sort(b, b + n);
        int mx = 0;
        for (int i = 0; i < k; i++) mx = max(mx, a[i] + b[k - i - 1]);
        cout << mx << '\n';
    }


    return 0;
}

1차 2번 – 카드 게임

$N \leq 3\ 000$개의 카드가 쌓여 있는 두 덱 X와 Y가 있습니다. 각 카드에는 $K \leq 3\ 000$ 이하의 양의 정수가 적혀 있습니다. 두 명이 번갈아 카드를 가져가는데,

• 꼭 한 개의 덱을 선택해서 위에서부터 한 장 이상을 가져가야 하며,
• 가져간 카드의 합이 $K$ 이하여야 하고,
• 마지막으로 카드를 가져가는 사람이 집니다.

내 턴에 덱 X에 $i$장의 카드가, 덱 Y에 $j$장의 카드가 남아 있는 상태를 $\left(i,j\right)$라고 한다면, $N$과 $K$가 정해져 있는 게임에 대해 중간 상태로 가능한 경우는 총 $\left(N+1\right)^2$개입니다. 각각의 상태에서 두 플레이어가 각각 최선의 방법으로 플레이했을 때 내가 반드시 이기는 경우와 반드시 지는 경우의 갯수를 세고 싶습니다.

Grundy number를 바로 떠올릴 수 있겠지만, 아쉽게도 마지막으로 카드를 가져가는 사람이 지는 게임(misère)이기 때문에 Grundy를 쓸 수 없습니다. Grundy로 접근하기 전에 ‘이게 1차 예선 2번에 나올 수 있을 만한 지식인가?’를 생각해 볼 필요가 있습니다.

대신 다이나믹 프로그래밍으로 접근할 수 있습니다.

• 현재 상태 $\left(i,j\right)$에서 내가 어떤 덱에서 얼마나 많이 가져가더라도 다음 플레이어가 이기는 상태만 나온다면, 현재 상태는 내가 지는 상태입니다.
• 그렇지 않다면, 내가 특정한 동작을 하면 다음 플레이어가 지는 상태를 만들 수 있습니다. 이런 경우 현재 상태는 내가 이기는 상태입니다.

따라서, DP 테이블을 만들어둔 후 가져간 카드의 합이 $K$ 이하가 되도록 X에서 하나씩, Y에서 하나씩 가져가면서 다음 플레이어가 이기는 상태가 있는지 확인해 주면 됩니다. 이 계산을 $\left(N+1\right)^2$개에 대해 하므로, $\mathcal{O}\left(N^3\right)$입니다.

$N \leq 3\ 000$이므로 Large 셋을 풀기에는 불충분합니다. 이는 Prefix sum을 이용해 $\mathcal{O}\left(N^2\right)$로 최적화할 수 있습니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

int x[3010], y[3010], xp[3010], yp[3010], xi[3010], yj[3010];
bitset<3010> dp[3010];
int prs[3010][3010];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        memset(dp, 0, sizeof dp);
        dp[0][0] = true;

        int n, k;
        cin >> n >> k;

        for (int i = 1; i <= n; i++) {
            cin >> x[i], xp[i] = x[i] + xp[i - 1];
            int v = xp[i] - k - 1;
            int ii = upper_bound(xp, xp + i, v) - xp;
            xi[i] = ii;
        }
        for (int j = 1; j <= n; j++) {
            cin >> y[j], yp[j] = y[j] + yp[j - 1];
            int v = yp[j] - k - 1;
            int jj = upper_bound(yp, yp + j, v) - yp;
            yj[j] = jj;
        }

        int a = 0, b = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                int xc = (prs[i][j + 1] - prs[xi[i]][j + 1] - prs[i][j] + prs[xi[i]][j]);
                int yc = (prs[i + 1][j] - prs[i + 1][yj[j]] - prs[i][j] + prs[i][yj[j]]);

                dp[i][j] = ((i - xi[i]) - xc) || ((j - yj[j]) - yc);
                dp[0][0] = true;
                (dp[i][j] ? a : b)++;
                prs[i + 1][j + 1] = dp[i][j] + prs[i][j + 1] + prs[i + 1][j] - prs[i][j];
            }
        }

        cout << prs[n + 1][n + 1] << ' ' << (n + 1) * (n + 1) - prs[n + 1][n + 1] << endl;
    }


    return 0;
}

1차 3번 – 사다리 게임

$N \leq 1\ 500$개의 세로선과 $K \leq 2\ 000$개의 가로선이 있는 사다리가 있습니다.

$M \leq 100\ 000$개의 쿼리가 들어옵니다. $\left(i,j\right)$의 형태입니다. 위의 $i$번 위치에서 시작해서 아래의 $j$번 위치에서 끝나도록 가로선을 적절히 없애 사다리를 조작하고 싶은데, 가로선을 최소한으로 없앴을 때 몇 개 없애야 하는지를 구해야 합니다.

Kotlin Heroes: Episode 4의 E번 문제와 상당히 비슷합니다.

가로선들이 그래프의 간선들이라고 생각하고 접근해서 최단 거리 문제로 해결했습니다.

$u$와 $v$를 잇는 가로선이 있다면, 가로선을 무시하는 경우($u \rightarrow u$, $v \rightarrow v$)를 가중치 $1$로, 무시하지 않는 경우($u \rightarrow v$, $v \rightarrow u$)를 가중치 $0$으로 하여 간선 $4$개로 만들어 줍니다.

정점은 $N$개를 처음에 만들어 주고, 가로선을 하나 처리할 때마다 가로선의 끝점에 각각 하나씩, 총 $2$개를 더 만들어 줍니다. 이렇게 그래프를 구성하면 노드는 총 $N+2K \leq 5\ 500$개가 됩니다.

이렇게 하면 각 시작점마다 Dijkstra 혹은 0-1 BFS를 돌리는 것으로 각 종점까지의 최단거리를 구하면, 그것이 시작점에서 종점까지 가면서 제거해야 하는 가로선의 개수의 최댓값이 됩니다. 이 방법을 이용해 쿼리 값들을 전부 전처리해둔 후, 쿼리가 들어오는 대로 전처리된 값들을 출력해 주려고 합니다.

만들어 준 그래프의 정점은 $N+2K$개, 간선은 $4K$개이므로 0-1 BFS의 경우 한 번에 $\mathcal{O}\left(N+K\right)$, Dijkstra의 경우 한 번에 $\mathcal{O}\left(K \log K\right)$입니다. 이를 모든 시작점에 대해 한 번씩 돌려주면 0-1 BFS의 경우 $\mathcal{O}\left(N^2+NK\right)$, Dijkstra의 경우 $\mathcal{O}\left(NK \log K\right)$만에 해결할 수 있습니다. 저는 그냥 Dijkstra로 해결했습니다.

DP로도 해결할 수 있다고 합니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

pii seg[2000];
int last[1500], dist[1500][1500], dtemp[9000];
bitset<9000> vis;

void dijk(int s, const vector<vector<pii>> &graph) {
    memset(dtemp, -1, sizeof dtemp);
    vis.reset();
    priority_queue<pii> pq;
    dtemp[s] = 0;
    pq.emplace(0, s);
    while (pq.size()) {
        int u = pq.top().second, d = -pq.top().first;
        pq.pop();
        if (dtemp[u] < d) continue;
        if (vis[u]) continue;
        vis[u] = true;
        for (const auto &kv : graph[u]) {
            int v = kv.first, c = kv.second;
            if (dtemp[v] == -1 || dtemp[u] + c < dtemp[v]) {
                dtemp[v] = dtemp[u] + c;
                pq.emplace(-dtemp[v], v);
            }
        }
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        memset(dist, -1, sizeof dist);

        int n, k, q;
        cin >> n >> k >> q;

        vector<vector<pii>> graph(n);
        for (int i = 0; i < n; i++) last[i] = i;

        for (int i = 0; i < k; i++) {
            cin >> seg[i].first >> seg[i].second;
            seg[i].first--, seg[i].second--;
        }

        for (int i = 0; i < k; i++) {
            const auto &l = seg[i];
            int gn = graph.size();
            graph[last[l.first]].emplace_back(gn, 1);
            graph[last[l.second]].emplace_back(gn + 1, 1);
            graph[last[l.first]].emplace_back(gn + 1, 0);
            graph[last[l.second]].emplace_back(gn, 0);
            last[l.first] = gn;
            last[l.second] = gn + 1;
            graph.emplace_back();
            graph.emplace_back();
        }

        for (int i = 0; i < n; i++) {
            graph[last[i]].emplace_back(graph.size(), 0);
            last[i] = graph.size();
            graph.emplace_back();
        }

        for (int i = 0; i < n; i++) {
            dijk(i, graph);
            for (int j = 0; j < n; j++) dist[i][j] = dtemp[last[j]];
        }

        int s = 0;
        while (q--) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            s += dist[u][v];
        }
        cout << s << endl;
    }

    return 0;
}

1차 4번 – 범위 안의 숫자

0에서 9까지의 숫자 $n \leq 50\ 000$개로 이루어진 문자열 $t$가 주어집니다. 길이가 $k \leq \min\left\{9,n\right\}$인 부분 문자열들을 수라고 생각하고, 모두 수직선 위에 둡니다.

이 때, 여기서 최대 한 글자까지를 1로 바꿔서, 어떤 정수 $a$에 대해 길이가 $m \leq 10^9$인 구간 $\left[a,a+m\right]$ 안에 속한 수의 개수의 최댓값이 최대가 되게 하고 싶습니다. 이 때의 최댓값을 구해야 합니다.

일단 $k$가 커봐야 $9$고, $n$도 그렇게 크지 않아서, 문자 하나를 1로 바꿀 수 있다는 것을 배제하고 생각하면 이 문제는 스위핑으로 해결할 수 있습니다. 부분 문자열의 값을 $x_i$라고 하면, 선분 $\left[x_i,x_i+m\right]$들을 수직선 위에 깔아 두고 가장 많이 겹쳤을 때의 선분의 갯수를 구하면 됩니다.

이제 문자 하나를 1로 바꿀 수 있는 경우를 생각해봅시다. ‘문자 하나를 1로 바꾸는 것’이라는 행위에서 관찰 가능한 특별한 성질은 딱히 없다고 느꼈습니다. 다만, 문자 하나를 1로 바꾸면 다시 만들어줘야 하는 선분의 개수는 $9$개에 불과하다는 사실에 집중했습니다.

만약 다이나믹하게 선분을 제거하고 추가할 수 있는 스위핑이 있다면, 모든 위치의 숫자를 하나하나 1로 바꾸고 되돌리는 행위를 한다고 해도 추가/제거는 $\mathcal{O}\left(kn\right)$번만 일어나므로 시간 안에 해결할 수 있을 것 같습니다.

다행히도 그런 스위핑은 존재하는데요, 최댓값을 구하는 연산과 구간에 덧셈을 하는 연산(lazy propagation 등)을 수행 가능한 세그먼트 트리로 가능합니다.

다만 인덱스가 꽤 크기 때문에 다이나믹 세그먼트 트리를 구현하거나, 가능한 값들을 전부 좌표 압축한 후 처리하는 방법을 사용해야 합니다. 저는 후자로 구현했습니다. 총 시간 복잡도는 $\mathcal{O}\left(kn \log kn\right)$입니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

ll tree[1048576 * 2], lazy[1048576 * 2];

int c;

void _propagate(int x, int s, int e) {
    if (!lazy[x]) return;
    tree[x] += lazy[x];
    if (s != e) {
        lazy[x * 2] += lazy[x];
        lazy[x * 2 + 1] += lazy[x];
    }
    lazy[x] = 0;
}

ll _maximum(int x, int s, int e, int l, int r) {
    _propagate(x, s, e);
    if (l > e || r < s) return 0;
    if (l <= s && e <= r) return tree[x];
    int m = (s + e) / 2;
    return max(_maximum(x * 2, s, m, l, r),
               _maximum(x * 2 + 1, m + 1, e, l, r));
}

void _update(int x, int s, int e, int l, int r, ll dv) {
    _propagate(x, s, e);
    if (l > e || r < s) return;
    if (l <= s && e <= r) {
        tree[x] += dv;
        if (s != e) {
            lazy[x * 2] += dv;
            lazy[x * 2 + 1] += dv;
        }
        return;
    }
    int m = (s + e) / 2;
    _update(x * 2, s, m, l, r, dv);
    _update(x * 2 + 1, m + 1, e, l, r, dv);
    tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
}

ll maximum(int l, int r) {
    return _maximum(1, 0, c - 1, l, r);
}

void update(int l, int r, ll dv) {
    _update(1, 0, c - 1, l, r, dv);
}

ll zip(ll x, const vector<ll> &a) {
    return lower_bound(a.begin(), a.end(), x) - a.begin();
}

ll v[50000], v1[50000][10];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        ll n, k, m;
        cin >> n >> k >> m;
        string t;
        cin >> t;

        // init values
        vector<ll> ps;
        ll curr = 0, mod = 1;
        for (int i = 0; i < k; i++) mod *= 10;
        for (int i = 0; i < k; i++) curr *= 10, curr += t[i] & 15, curr %= mod;
        for (int i = k; i <= n; i++) {
            v[i - k] = curr;
            ps.emplace_back(curr);
            ll l = curr, r = 0, p = 1;
            for (int j = 0; j < k; j++) {
                v1[i - k][j] = (l / 10 * 10 + 1) * p + r;
                ps.emplace_back(v1[i - k][j]);
                l /= 10, r += (curr / p) % 10 * p, p *= 10;
            }
            if (i == n) break;
            curr *= 10, curr += t[i] & 15, curr %= mod;
        }
        int ts = ps.size();
        for (int i = 0; i < ts; i++) ps.emplace_back(ps[i] + m);

        sort(ps.begin(), ps.end());
        ps.erase(unique(ps.begin(), ps.end()), ps.end());

        memset(tree, 0, sizeof tree);
        memset(lazy, 0, sizeof lazy);
        c = ps.size();
        // query
        for (int i = 0; i <= n - k; i++) {
            update(zip(v[i], ps), zip(v[i] + m, ps), 1);
        }

        ll mx = maximum(0, ps.size() - 1);

        for (int i = 0; i < n; i++) { // replace i-th number to 1
            // remove
            for (int j = 0; j < k; j++) {
                if (i - k + j < 0 || i - k + j > n - k) continue;
                update(zip(v1[i - k + j][j], ps), zip(v1[i - k + j][j] + m, ps), -1);
            }
            if (i <= n - k) {
                update(zip(v[i], ps), zip(v[i] + m, ps), -1);
            }
            // add
            if (i - k >= 0) {
                update(zip(v[i - k], ps), zip(v[i - k] + m, ps), 1);
            }
            for (int j = 0; j < k; j++) {
                if (i - k + 1 + j < 0 || i - k + 1 + j > n - k) continue;
                update(zip(v1[i - k + 1 + j][j], ps), zip(v1[i - k + 1 + j][j] + m, ps), 1);
            }
            // query
            mx = max(mx, maximum(0, ps.size() - 1));
        }
        cout << mx << endl;
    }

    return 0;
}