SCPC 2024 1차 예선에 참가했습니다 (1/3)

적당히 쉬엄쉬엄 풀어서 난이도에 비해 남은 시간이 다소 적습니다. 올해는 2번까지 풀지 않으면 Round 2를 가기 좀 힘들지 않을까 싶을 정도로 1, 2, 3번이 쉬웠습니다.

개인적인 난이도는 1 < 2 < 3 < 5 < 4번이었습니다.

1차 1번 – A보다 B가 좋아

길이 $N \le 300\,000$ 의 A와 B로만 이루어진 문자열이 있습니다. 이 문자열에서 길이 $2$ 이상의 어느 부분 문자열을 골라도 A의 개수보다 B의 개수가 크거나 같도록 하고 싶습니다. 원하는 위치에 B를 추가할 수 있다고 할 때 최소 몇 개를 추가해야 할까요?

작은 경우부터 생각해 봅시다.

길이 $2$ 인 부분 문자열은 AA인 경우만 피하면 됩니다.

길이 $3$ 인 부분 문자열은 AAA, AAB, ABA, BAA가 있는데, AA라는 부분 문자열을 어떻게 다 없앴다고 가정하면, ABA만 피하면 됩니다.

AA와 ABA를 어떻게 다 없앴다고 가정하면, 길이 $4$ 인 부분 문자열은 무조건 A의 개수보다 B의 개수가 크거나 같음을 알 수 있습니다.

이 성질이 길이 $5$ 이상에서도 성립하는지 알아봅시다. 귀납법을 사용할 수 있습니다.

길이 $K$ 의 문자열이 A로 끝나는 경우, AA와 ABA 패턴이 존재하지 않으므로, BBA로 끝나야 합니다. 따라서 이 경우 뒤에서 A와 B 한 글자씩 총 두 글자를 뗀 길이 $K-2$ 의 문자열에서 성질을 만족했다면, 길이 $K$ 의 문자열에서도 성질이 유지됩니다.
길이 $K$ 의 문자열이 B로 끝나는 경우, 길이 $K-1$ 의 문자열의 맨 뒤에 B를 하나 붙여 준다고 생각할 수 있습니다. 따라서 이 경우 길이 $K-1$ 의 문자열에서 성질을 만족했다면, 길이 $K$ 의 문자열에서도 성질이 유지됩니다.

따라서, A와 A 사이에 두 개 이상의 B가 있도록 추가해 주는 것으로 충분합니다.

#include <bits/stdc++.h>

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

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    
    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        int n;
        cin >> n;
        string str;
        cin >> str;

        vector<int> idxs;
        for (int i = 0; i < n; i++) {
            if (str[i] == 'A') idxs.emplace_back(i);
        }

        int s = 0;
        for (int i = 0; i + 1 < idxs.size(); i++) {
            int d = idxs[i + 1] - idxs[i] - 1;
            s += max(0, 2 - d);
        }

        cout << "Case #" << _ << endl;
        cout << s << endl;
    }

    return 0;
}

1차 2번 – 배달

물건이 $N \le 300\,000$ 개 있습니다. $N$ 은 $4$ 의 배수입니다. 물건들에는 무게가 있습니다( $1 \le \text{무게} \le 1\,500\,000$ ).

$4$ 개의 물건씩 골라 $N$ 개의 물건을 모두 배송할 예정입니다. 이 때, $4$ 개의 물건의 무게가 각각 $a \le b \le c \le d$ 라고 할 때,

|d-c|+|c-b|+|b-a|+|a-d|

원을 벌 수 있습니다. 모든 물건을 배달해서 벌 수 있는 최대 금액은 얼마일까요?

$a$ , $b$ , $c$ , $d$ 의 대소가 이미 정해져 있으므로 절댓값 기호는 의미가 없습니다. 식을 정리합시다.

\begin{aligned}& |d-c|+|c-b|+|b-a|+|a-d| \\ =\, & (d-c)+(c-b)+(b-a)+(d-a) \\ =\, & 2d-2a\end{aligned}

따라서 가장 무거운 하나와 가장 가벼운 하나만이 배송비에 관여한다는 사실을 알 수 있습니다.

가장 무거운 물건들의 합을 최대화하고, 가장 가벼운 물건들의 합을 최소화하는 방법은 가장 무거운 $N/4$ 개의 물건들을 $d$ 로 배정하고, 가장 가벼운 $N/4$ 개의 물건을 $a$ 로 배정하도록 하는 것입니다.

#include <bits/stdc++.h>

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

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

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());

        int m = n / 4;
        ll s = 0;
        for (int i = 0; i < m; i++) s -= a[i];
        for (int i = 3 * m; i < n; i++) s += a[i];

        cout << "Case #" << _ << endl;
        cout << s * 2 << endl;
    }

    return 0;
}

1차 3번 – 보안망 점검

보안 장비 $N \le 300\,000$ 개가 있습니다. 이들은 총 $N+1$ 개의 라인으로 연결되어 있으며, 이 중 $N$ 개의 라인은 보안 장비 $N$ 개를 원형으로 연결하고 있으며, 나머지 $1$ 개의 라인은 원형으로 연결되어 있는 보안 장비들 중 두 개를 잇습니다. 이 때, 정확히 $2$ 개의 라인이 파괴되었을 때 망이 분리되는 경우의 수를 구해야 합니다.

다시 말하면, 보안 장비 그래프는 $3$ 개의 사이클로 되어 있으며, 가장 큰 사이클은 크기가 $N$ 입니다.

큰 사이클을 나누는 한 개의 간선은 degree가 $3$ 인 정점 두 개를 찾는 것으로 찾을 수 있습니다. 그 한 개의 간선을 기준으로 왼쪽과 오른쪽에 간선이 몇 개 있나 확인합니다. 각각 $l$ 개와 $r$ 개가 있다면, 그래프를 분할하는 경우의 수는

\frac{l\left(l-1\right)}{2}+\frac{r\left(r-1\right)}{2}

개임을 확인할 수 있습니다.

#include <bits/stdc++.h>

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

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

    vector<vector<int>> graph(n + 1);
    vector<int> deg(n + 1, 0);

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

    vector<int> deg3;

    for (int u = 1; u <= n; u++) {
        if (deg[u] == 3) {
            deg3.emplace_back(u);
        }
    }

    assert(deg3.size() == 2);

    int a = deg3[0], b = deg3[1];
    ll l1 = 0, l2 = 0;

    function<int(int, int)> dfs = [&](int u, int p) {
        if (u == b) return 0;
        for (int v: graph[u]) {
            if (v == p) continue;
            return dfs(v, u) + 1;
        }
    };

    bool skip_flag = false;
    for (int c: graph[a]) {
        if (c == b && !skip_flag) {
            skip_flag = true;
            continue;
        }
        if (l1) {
            l2 = 1 + dfs(c, a);
        } else {
            l1 = 1 + dfs(c, a);
        }
    }

    ll s = 0;
    s += (l1) * (l1 - 1) / 2;
    s += (l2) * (l2 - 1) / 2;

    return s;
}

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

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {

        cout << "Case #" << _ << endl;
        cout << solve() << endl;
    }

    return 0;
}

1차 4번 – 딱 맞게

원소의 개수가 $5 \le N \le 100\,000$ 개인 두 중복 집합 $A$ 와 $B$ 가 있습니다.

여기에 일대일 대응 $F\left(A, B\right)$ 을 정의하여, 서로 대응하는 원소의 값의 차이의 절댓값들 중 가장 큰 값 $\max F\left(A, B\right)$ 를 계산할 수 있습니다. 이 값이 $1 \le L \le 10^9$ 보다 작으면서 가장 크게 되도록 해야 합니다. 이때 $\max F\left(A, B\right)$ 를 출력해야 합니다.

문제를 쉽게 써 봅시다. 배열 $A$ 와 $B$ 가 있어서, 이들의 순서를 잘 섞어서

\max \left\{ |a_1-b_1|,|a_2-b_2|,\cdots,|a_N-b_N| \right\}

을 $L$ 이하가 되게 하면서 최대화하라는 문제입니다.

$A$ 와 $B$ 를 각각 정렬하면 $\max F\left(A, B\right)$ 가 최소가 됩니다. 이 사실을 통해, $A$ 에서 적당한 한 개의 값 $a$ 와 $B$ 에서 적당한 한 개의 값 $b$ 를 골라 놓고, 나머지 원소들을 정렬해 놓는 방법을 사용할 수 있습니다. 이미 정렬된 $A$ 와 $B$ 에 대해서 $|A_i-B_i|$ , $|A_{i+1}-B_i|$ , $|A_i-B_{i+1}|$ 의 값들을 미리 계산하여 관리하고 있다면 적당한 $(a,b)$ 쌍에 대해 충분히 빠르게 계산할 수 있습니다.

$|a-b| \le L$ 인 모든 쌍을 보는 것만으로 문제를 해결하는 데에는 충분합니다. 더 나아가서, $a$ 가 정해져 있을 때, $|a-b|$ 의 값이 $L$ 이하이면서 가장 크도록 하는 $b$ 를 적당히 잘 골라 주고, 이런 $(a,b)$ 쌍들만을 보는 것만으로 충분함을 보일 수 있습니다.

아래 코드의 복잡도는 $\mathcal{O}\left(N \log N\right)$ 입니다. 제 소스 코드는 세그먼트 트리와 이분 탐색을 쓰지만 단조성을 이용한 투 포인터 등의 방법으로 시간을 더 줄일 수 있습니다.

#include <bits/stdc++.h>

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

ll a[100010], b[100010];

ll p[400010], pa[400010], pb[400010];

void update(ll *tree, int x, int s, int e, int i, ll v) {
    if (s == e) {
        tree[x] = v;
        return;
    }
    int m = (s + e) / 2;
    if (i <= m) update(tree, x * 2, s, m, i, v);
    else update(tree, x * 2 + 1, m + 1, e, i, v);
    tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
}

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

void update_p(int i, ll v) {
    update(p, 1, 1, 100000, i, v);
}

void update_pa(int i, ll v) {
    update(pa, 1, 1, 100000, i, v);
}

void update_pb(int i, ll v) {
    update(pb, 1, 1, 100000, i, v);
}

ll query_p(int l, int r) {
    if (l > r) return 0;
    return query(p, 1, 1, 100000, l, r);
}

ll query_pa(int l, int r) {
    if (l > r) return 0;
    return query(pa, 1, 1, 100000, l, r);
}

ll query_pb(int l, int r) {
    if (l > r) return 0;
    return query(pb, 1, 1, 100000, l, r);
}

ll solve() {
    ll n, l;
    cin >> n >> l;

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

    for (int i = 1; i <= n; i++) update_p(i, abs(a[i] - b[i]));
    for (int i = 1; i + 1 <= n; i++) update_pa(i, abs(a[i + 1] - b[i]));
    for (int i = 1; i + 1 <= n; i++) update_pb(i, abs(a[i] - b[i + 1]));

    ll ans = -1;

    for (int ai = 1; ai <= n; ai++) {
        for (ll x: {a[ai] - l, a[ai] + l}) {
            int biv = lower_bound(b + 1, b + 1 + n, x) - b;
            for (int bi: {biv - 1, biv}) {
                if (bi < 1 || bi > n) continue;

                // move ai and bi to the end; calculate max abs diff of the rest
                ll mx = abs(a[ai] - b[bi]);
                mx = max(mx, query_p(0, min(ai, bi) - 1));
                if (ai > bi) {
                    mx = max(mx, query_pb(bi, ai - 1));
                } else {
                    mx = max(mx, query_pa(ai, bi - 1));
                }
                mx = max(mx, query_p(max(ai, bi) + 1, n));

                if (mx <= l) ans = max(ans, mx);
            }
        }
    }

    return ans;
}

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

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

    return 0;
}

1차 5번 – 스퀘어

배열에서 $2$ 이상의 정수 $k$ 를 정해서, $k$ 개의 $k$ 를 $1$ 개의 $k^2$ 로 바꾸는 작업을 ‘스퀘어’라고 정의합시다. 예를 들어,

\begin{aligned}& [\textcolor{#ff3b57}{2},4,\textcolor{#ff3b57}{2},4,2,2] \\ \rightarrow\, & [4,4,4,\textcolor{#ff3b57}{2},\textcolor{#ff3b57}{2}] \\ \rightarrow\, & [\textcolor{#ff3b57}{4},\textcolor{#ff3b57}{4},\textcolor{#ff3b57}{4},\textcolor{#ff3b57}{4}] \\ \rightarrow\, & [16] \end{aligned}

과 같이 스퀘어 연산을 수행할 수 있습니다.

크기 $N \le 50\,000$ 의 배열이 있습니다. 각 원소는 $1$ 이상 $10^9$ 이하입니다. $Q \le 50\,000$ 개의 쿼리를 처리해야 합니다.

$l$ $r$ : 배열 $a_l$ , $a_{l+1}$ , $\cdots$ , $a_r$ 에서 가능한 ‘스퀘어’의 최대 횟수를 구하여 출력한다.

배열에서 $2$ 미만 및 $50\,000$ 초과인 원소들은 무시해도 된다는 사실과, ‘스퀘어’ 연산의 연쇄 반응은 최대 $4$ 번까지만 일어난다는 사실을 생각해 봅시다. 세그먼트 트리로는 어떻게 풀어야 될지 감이 잘 안 잡히지만, Mo’s는 사용하기 좋아 보입니다. 아래 코드의 시간 복잡도는 $\mathcal{O}\left(N + Q \log Q + Q \sqrt{N} \log \log N \right)$ 입니다.

#include <bits/stdc++.h>

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

const int m = 240;
int a[50001], cnt[50001];
ll ans[50000];

struct query {
    int l, r, i;

    query() : l(0), r(0), i(0) {}

    query(int l, int r, int i) : l(l), r(r), i(i) {}

    bool operator<(const query &rhs) const {
        return pii(l / m, r) < pii(rhs.l / m, rhs.r);
    }
};

void init(ll &val) {
    for (int x = 2; x <= 50000; x++) {
        int t = x * x;
        if (2 <= t && t <= 50000) {
            cnt[t] += cnt[x] / x;
        }
        val += cnt[x] / x;
    }
}

void add(ll &val, int x) {
    while (2 <= x && x <= 50000) {
        cnt[x]++;
        if (cnt[x] % x) return;
        val++;
        x *= x;
    }
}

void remove(ll &val, int x) {
    while (2 <= x && x <= 50000) {
        cnt[x]--;
        if ((cnt[x] + 1) % x) return;
        val--;
        x *= x;
    }
}

// sqrt 50 000 < 224
// sqrt sqrt 50 000 < 15
// sqrt sqrt sqrt 50 000 < 4
// sqrt sqrt sqrt sqrt 50 000 < 2

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

    memset(cnt, 0, sizeof cnt);

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

    int q;
    cin >> q;

    vector<query> qry(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        qry[i] = query(l, r, i);
    }
    sort(qry.begin(), qry.end());

    ll val = 0;
    int l = qry[0].l, r = qry[0].r;
    for (int i = l; i <= r; i++) {
        if (2 <= a[i] && a[i] <= 50000) cnt[a[i]]++;
    }
    init(val);
    ans[qry[0].i] = val;

    for (int i = 1; i < q; i++) {
        while (l < qry[i].l) remove(val, a[l++]);
        while (l > qry[i].l) add(val, a[--l]);
        while (r > qry[i].r) remove(val, a[r--]);
        while (r < qry[i].r) add(val, a[++r]);
        ans[qry[i].i] = val;
    }

    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

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

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

    return 0;
}

Blog ›SCPC 2024 1차 예선에 참가했습니다 (1/3)

1차 1번 – A보다 B가 좋아

1차 2번 – 배달

1차 3번 – 보안망 점검

1차 4번 – 딱 맞게

1차 5번 – 스퀘어

Comments

.css-9d3s5r{color:var(--chakra-colors-fg-muted);font-weight:500;font-size:0.8em;vertical-align:0.1em;-webkit-text-decoration:none;text-decoration:none;margin-right:0.3em;}Blog ›SCPC 2024 1차 예선에 참가했습니다 (1/3)

1차 1번 – A보다 B가 좋아

1차 2번 – 배달

1차 3번 – 보안망 점검

1차 4번 – 딱 맞게

1차 5번 – 스퀘어

Comments

Blog ›SCPC 2024 1차 예선에 참가했습니다 (1/3)