SCPC 2024 1차 풀이

문제와 풀이 간략하게만 작성합니다.

1. A보다 B가 좋아

A와 B로만 이루어진 문자열이 주어질 때, 연속이고 길이가 2 이상인 어떤 부분에서도 A의 개수가 B의 개수보다 많지 않기위해 문자열에 끼워넣어야 하는 B개수의 최솟값은?

풀이

두 A사이의 간격을 살펴봅시다. 두 A사이에 B가 0개 혹은 1개 있으면 AA, ABA 문자열에 대해 A의 개수가 B의 개수보다 많게 됩니다. 두 A사이에 B가 2개 이상 있으면, $n$개의 A가 있는 부분문자열을 고르려고 할 때 B를 $2n-2$개 이상 골라야해서, $n \ge 2$에 대해 항상 B의 개수가 A의 개수 이상이 됩니다.

2. 배달

$N$개의 수를 4개씩 $\frac{N}{4}$개의 그룹으로 묶어서, 각 그룹 점수의 합을 최대화 하려고 한다. 그룹 ${a, b, c, d}$ $(a \le b \le c \le d)$의 점수는 $\lvert d−c \rvert + \lvert c−b \rvert + \lvert b−a \rvert + \lvert a−d \rvert$이다.

풀이

$a \le b \le c \le d$가 주어졌으므로, 절댓값으로 주어진 식을 정리하면 $(d-c)+(c-b)+(b-a)+(d-a) = 2(d-a)$가 나옵니다. 즉, $\frac{N}{4}$개의 쌍을 골라서 차이의 합을 최대화 하는 문제로, 가장 큰 수와 가장 작은 수 $\frac{N}{4}$씩을 각각 골라주면 됩니다.

3. 보안망 점검

크기 $N$의 그래프가 하나 주어지는데, 이 그래프는 길이 $N$의 사이클 하나와 추가 간선 하나로 이루어져있다. (중복간선도 존재할 수 있다.) 이 때, 간선 2개를 골라서 끊었을 때, 그래프가 연결그래프가 아니도록 하는 경우의 수를 구하여라.

풀이

하나의 간선을 기준으로 양쪽을 나눠보면, 한쪽에서 $2$개를 끊는게 아닌 이상 그래프의 연결상태가 끊기지 않는다는 것을 알 수 있습니다. 이제, 문제에서 순서 없이 주어진 그래프에서 추가 간선 하나를 찾고, 그 간선 하나로 나뉘어진 양쪽의 간선 개수를 세어서 $a, b$라고 하면, $\frac{a(a-1)+b(b-1)}{2}$가 답이 됩니다. $a, b$는 여러가지 방법으로 찾을 수 있고, 예시는 다음과 같습니다.

1. 정점이 $3$인 두 정점 사이에 간선이 존재합니다.
2. 이 두 정점을 제외한 그래프에 대해서 연결성분의 크기를 구하면, (연결성분의 크기 + 1)이 간선의 개수가 됩니다.

4. 딱 맞게

길이가 $N$으로 같은 두 배열 $A, B$가 주어지는데, 이 두 배열에서 각각 원소 하나씩을 골라서 짝을 $N$개 짓는다. 이때 이 짝의 "불일치도"는 짝지은 두 수의 차이 $N$개 중 최댓값이다. 불일치도를 $L$이하로 유지하면서, 가능한 불일치도의 최댓값을 구하여라. (불가능하면 $-1$)

풀이

불일치도를 최소화 하기 위해서는 두 배열을 정렬하고 차례차례로 짝짓는 것이 이득입니다. (이는 $N=2$일 때 확인하고, 이를 임의의 크기에 대해서 늘려서 증명할 수 있습니다.) 우선 이 방법으로, 두 배열을 정렬해 $A_1, \cdots, A_N$과 $B_1, \cdots, B_N$이라고 하고, $\lvert A_i - B_i \rvert$가 $L$ 초과인 것이 있는지 확인합니다. 이 경우 불일치도를 $L$이하로 유지할 수 없기 때문에, 답은 $-1$이 됩니다.

만약 불일치도를 $L$이하로 유지하는 것이 가능하다면, 이 안에서 불일치도를 최대화 하기 위해서 두 배열에서 차이가 최댓값이 되도록 하는 짝을 하나 고르고, 나머지는 차이를 짝의 차이를 $L$이하로만 유지할 것입니다.

 

$A$와 $B$에서 $A_i, B_j$를 하나씩 골라서 짝지을 수 있는지는 다음과 같이 확인할 수 있습니다.

1. $\lvert A_i-B_j \rvert \le L$
2. 두 배열에서 $A_i, B_j$를 제외하고 정렬해서 차례차례로 짝지어서 불일치도를 최소화하고, 이가 $L$이하인지 확인합니다.

2번 과정에서 해야하는 일을 (일반성을 잃지 않고 $i < j$라 할 때) 살펴봅시다.

$A_i, B_j$가 짝지어지면, $A_1 \sim B_1, \cdots, A_{i-1} \sim B_{i-1}$ 과 $A_{j+1} \sim B_{j+1} , \cdots, A_N \sim B_N$은 그대로 짝이 지어지고 모두 차이가 $L$ 이하입니다. 여기서 $A_i$와 $B_j$가 빠지기 때문에, 나머지 짝은 $A_{i+1} \sim B_i, A_{i+2} \sim B_{i+1}, \cdots, A_j \sim B_{j-1}$과 같은 방식으로 짝지어집니다. 즉, 불일치도를 $L$이하로 만들 수 있는지 확인하기 위해서는 $\lvert A_{i+1} - B_i \rvert, \lvert A_{i+2} - B_{i+1} \rvert , \cdots , \lvert A_{j} - B_{j-1} \rvert$가 모두 $L$이하인지 확인해야합니다.

 

이제 $(i, j)$쌍이 주어졌을 때 이 여부를 빠르게 확인하기 위해서는, $\lvert A_{i+1} - B_i \rvert \le L$인지의 여부를 누적합 배열에 담아서 확인하면 됩니다. (조건을 만족하지 않을 때 $1$을 넣고, 해당 구간의 원소가 모두 $L$이하인지 확인하기 위해서 구간합이 $0$인지 확인하면 됩니다.) 이제, 가능한 $(i, j)$쌍에 대해서 $\lvert A_i - B_j \rvert$의 최댓갑을 구해보면 $O(N^2)$의 풀이를 얻을 수 있습니다.

 

이를 최적화하기 위해서는 $A_i$에서 골라서 짝지을 수 있는 $B_j$가 구간으로 나타나진다는 사실을 이용하면 됩니다. $1$번 조건과 $2$번 조건 모두 $j$와 $B_j$에 대한 조건이 연속된 구간으로 나타나기 때문에, 두 개의 교집합도 구간으로 나타나집니다. 이제 이분탐색을 이용해서 $A_i$와 짝지을 수 있는 최소와 최대 $B_j$를 찾고, 불일치도의 최댓값을 구해주면 됩니다.

5. 스퀘어

$2$ 이상의 정수 $k$에 대해 $k$개의 $k$를 $k^2$하나로 바꾸는 작업을 스퀘어라고 합니다. 수열이 주어지고, 쿼리로 $(l, r)$ 구간이 들어옵니다. $A_l, \cdots, A_r$ 수열에서 가능한 스퀘어 연산의 최대 횟수를 출력하세요.

풀이

해당 수열에서 스퀘어연산으로 가능한 $k$가 그렇게 많지 않습니다. $k$를 스퀘어하기 위해서는 $k$가 제곱수가 아니라면 $k$개의 $k$가 필요합니다. 배열의 길이가 $N$이므로, $k$개가 존재하는 $k$의 개수는 $O(\sqrt N)$이하입니다. ($1+2+\cdots+\sqrt N = O(N)$) 제곱수인 $k$의 개수 역수 $O(\sqrt N)$ 라는 것을 알 수 있습니다.

이렇게 가능한 $k$를 모두 전처리 해줍시다. 이제 각 쿼리에 대해, 누적합을 이용하여 가능한 $k$에 대해 $k$의 개수를 구하고, 스퀘어 연산의 수를 직접 구해주면 됩니다. 각 쿼리에는 $O(\sqrt N)$ 시간이 들기 때문에, 시간복잡도는 $O(Q \sqrt N)$이 됩니다.

코드

1번

#include <bits/stdc++.h>
using namespace std;
int solve(string s)
{
    int r = 0, a = 0;
    for (char c : s)
    {
        if (c == 'A')
            a += max(r, 0), r = 2;
        else
            r--;
    }
    return a;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        int N;
        string s;
        cin >> N >> s;
        cout << "Case #" << i << '\n'
             << solve(s) << endl;
    }
    return 0;
}

2번

#include <bits/stdc++.h>
using namespace std;
long solve(vector<int> A)
{
    sort(A.begin(), A.end());
    int N = A.size();
    long long ans = 0;
    for (int i = 0; i < N / 4; i++)
        ans += 2 * (A[N - i - 1] - A[i]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        int N;
        cin >> N;
        vector<int> A(N);
        for (int &a : A)
            cin >> a;
        cout << "Case #" << i << '\n'
             << solve(A) << endl;
    }
    return 0;
}

3번

#include <bits/stdc++.h>
using namespace std;
struct UFD
{
    vector<int> p;
    UFD(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int Find(int a) { return a == p[a] ? a : p[a] = Find(p[a]); }
    void Union(int a, int b) { p[Find(a)] = Find(b); }
};
long solve(vector<pair<int, int>> E)
{
    int N = E.size() - 1;
    vector<int> deg(N);
    for (auto [a, b] : E)
        deg[a]++, deg[b]++;

    vector<int> s;
    for (int i = 0; i < N; i++)
        if (deg[i] == 3)
            s.push_back(i);

    UFD ufd(N);

    int v1 = s[0], v2 = s[1];
    for (auto [a, b] : E)
    {
        if (a == v1 || a == v2)
            continue;
        if (b == v1 || b == v2)
            continue;
        ufd.Union(a, b);
    }
    vector<int> sz(N);
    for (int i = 0; i < N; i++)
    {
        if (i == v1 || i == v2)
            continue;
        sz[ufd.Find(i)]++;
    }

    long long ans = 0;
    for (int i = 0; i < N; i++)
        ans += 1LL * sz[i] * (sz[i] + 1) / 2;
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        int N;
        cin >> N;
        vector<pair<int, int>> V(N + 1);
        for (auto &[a, b] : V)
            cin >> a >> b, --a, --b;
        cout << "Case #" << i << '\n'
             << solve(V) << endl;
    }
    return 0;
}

4번

#include <bits/stdc++.h>
using namespace std;

int solve(int L, vector<int> A, vector<int> B)
{
    int N = A.size();
    ranges::sort(A);
    ranges::sort(B);
    for (int i = 0; i < N; i++)
        if (abs(A[i] - B[i]) > L)
        {
            return -1;
        }
    vector<int> AD(N), BD(N);
    for (int i = 0; i < N - 1; i++)
    {
        AD[i + 1] = AD[i] + (abs(A[i] - B[i + 1]) > L ? 1 : 0);
        BD[i + 1] = BD[i] + (abs(B[i] - A[i + 1]) > L ? 1 : 0);
    }
    auto can = [&](int a, int b)
    {
        if (abs(A[a] - B[b]) > L)
            return false;
        if (a < b)
            return BD[a] == BD[b];
        else
            return AD[a] == AD[b];
    };
    int ans = 0;
    for (int a = 0; a < N; a++)
    {
        {
            int ng = -1, ok = a;
            while (ng + 1 != ok)
            {
                int mi = (ng + ok) / 2;
                if (can(a, mi))
                    ok = mi;
                else
                    ng = mi;
            }
            ans = max(ans, abs(A[a] - B[ok]));
        }
        {
            int ng = N, ok = a;
            while (ok + 1 != ng)
            {
                int mi = (ng + ok) / 2;
                if (can(a, mi))
                    ok = mi;
                else
                    ng = mi;
            }
            ans = max(ans, abs(A[a] - B[ok]));
        }
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        int N, L;
        cin >> N >> L;
        vector<int> A(N), B(N);
        for (int &a : A)
            cin >> a;
        for (int &b : B)
            cin >> b;
        cout << "Case #" << i << '\n'
             << solve(L, A, B) << endl;
    }
    return 0;
}

5번

#include <bits/stdc++.h>
using namespace std;

vector<int> solve(vector<int> A, vector<pair<int, int>> Q)
{
    int N = A.size();
    vector<int> cnt(N + 1);
    for (int a : A)
        if (2 <= a && a <= N)
            cnt[a]++;

    vector<int> rows;
    vector<int> rowsinv(N + 1, -1);
    for (int i = 2; i <= N; i++)
        if (cnt[i] >= i)
        {
            rowsinv[i] = rows.size();
            rows.push_back(i);
            if (i * i <= N)
                cnt[i * i] += cnt[i] / i;
        }
    vector<vector<int>> accum(rows.size(), vector<int>(N + 1));
    for (int i = 0; i < (int)rows.size(); i++)
        for (int j = 0; j < N; j++)
            accum[i][j + 1] = accum[i][j] + (rows[i] == A[j] ? 1 : 0);
    vector<int> ret;
    for (auto [l, r] : Q)
    {
        vector<int> cnt(rows.size());
        int ans = 0;
        for (int i = 0; i < (int)rows.size(); i++)
        {
            cnt[i] += accum[i][r] - accum[i][l];
            if (cnt[i] >= rows[i])
            {
                int sq = cnt[i] / rows[i];
                ans += sq;
                int nxt = rows[i] * rows[i];
                if (nxt <= N)
                {
                    int nr = rowsinv[nxt];
                    if (nr != -1)
                        cnt[nr] += sq;
                }
            }
        }
        ret.push_back(ans);
    }
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        int N;
        cin >> N;
        vector<int> A(N);
        for (int &a : A)
            cin >> a;
        int Q;
        cin >> Q;
        vector<pair<int, int>> X(Q);
        for (auto &[l, r] : X)
            cin >> l >> r, --l;
        auto ret = solve(A, X);
        cout << "Case #" << i << '\n';
        for (auto x : ret)
            cout << x << '\n';
        cout << flush;
    }
    return 0;
}