SCPC 2024 2차 예선 풀이

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

1. 연속 1

$0$과 $1$로 구성된 수열이 주어집니다. 수열에 있는 $0$을 $1$로 바꾸는 데에는 한 번에 비용 $S$가 들고, $1$을 $0$으로 바꾸는 데에는 한번에 비용 $E$가 듭니다. 수열의 값을 바꿔서 $1$이 연속으로 나오는 부분이 $1$개 이하가 되도록 하고 싶습니다. 이 때의 최소 비용을 계산하세요.

풀이

수열을 앞에서부터 보고 다음과 같이 정의합니다.

• 앞 $i$개의 원소에 대해 수열을 모두 $0$으로 만드는 비용: $X_i$
• 수열을 $0...01...1$의 꼴로 만드는 비용: $Y_i$
• 수열을 $0...01...10...0$의 꼴로 만드는 비용: $Z_i$

이 때 $X_{i+1} = X_i + V_i \times E; Y_{i+1} = \min(X_{i+1}, Y_i + S \times (1-V_i)); Z_{i+1} = \min(Y_{i+1}, Z_i + E \times V_i$ 와 같이 점화식을 쓸 수 있습니다.

2. 라운드 로빈

$1, \cdots, N$의 수로 이루어진 수열을 만듭니다. $i$는 $W_i$개의 수를 쓰려고 합니다. $i = 1, \cdots, N$ 순으로 반복하면서 $W_i > 0$ 이면 수열에 $i$를 추가하고 $W_i$에다가 $1$을 뺍니다. 이렇게 수열을 만들 때 $X$번째 수를 구하세요 ($X$는 쿼리로 주어집니다)

$W_1 = 2, W_2 = 1, W_3 = 3$이면 $1, 2, 3; 1, 3; 3$과 같이 수열이 쓰입니다.

풀이

수열을 $N$개의 수가 반복되는 구간, $N-1$개의 수가 반복되는 구간, ..., $1$개의 수가 반복되는 구간으로 $N$개의 구간으로 만들 수 있습니다.

각 구간은 $W$를 크기 순으로 정렬한 이후 먼저 소모되는 것을 구간에서 빼주면서 개수를 세어주면 됩니다.

$i$개의 수가 반복되는 구간이 $S$에서 시작하고 $S+ki$에서 끝나면 $S \le T < S+ki$ 에 대해 남아있는 수 중에서 $(1 + T \bmod i)$번째 수가 답입니다. 남아있는 수는 $W_i$순으로 정렬한 후 OS-rank 등을 이용해서 문제를 풀면 됩니다.

3. 방범 시스템

사건이 일어날 가능성이 있는 $n$개의 위치 $a_1, a_2, \cdots, a_n$과 각각의 위치에서 사건이 일어날 확률이 $p_1, p_2, \cdots, p_n$입니다. 여기서 $\sum_{i=1}^n p_i = 1$입니다.

각 경찰관의 위치 $q$가 주어지면, $q$에서 일어날 사건과의 거리의 기댓값을 출력합니다. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$의 거리는 $\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert$입니다.

풀이

$x$와 $y$에 대해 독립적으로 풀면 됩니다. 각 $1$차원 좌표에 대해서 푸는 방법은 $n$개의 위치와 $q$개의 경찰관의 위치를 모두 정렬한 이후 스위핑을 한 번 돌려주면 됩니다.

4. 수열 탈집중화

$N$개의 수로 이루어진 수열 $A_1, A_2, \cdots, A_N$이 있습니다. 한 번의 연산으로 연속된 구간을 잡고 해당 구간의 원소를 모두 해당 구간의 최솟값으로 바꾸거나 최댓값으로 바꿀 수 있습니다.

$\sum_{1 \le i, j \le n} (A_i-A_j)^2$ 을 최대로 하기 위한 연산 수열을 출력하세요. 만약 해당하는 연산 수열이 여러개면 가장 길이가 짧은 연산 수열을 출력하세요.

풀이

관찰을 열심히 하면, 해당 수열의 모든 원소를 $A_i$들의 최댓값인 $mx$, $A_i$들의 최솟값인 $mn$만 남기고 $mx$와 $mn$의 개수의 차이를 $1$이하로 만드는 것이 필요함을 알 수 있습니다.

수열이 $..., mn, ..., mx, ...$ 과 같이 존재할 경우 이 수열의 오른쪽 부분에 연산을 해서 $..., mn, mx, mx, ..., mx$와 같이 바꾸고 왼쪽 부분에 연산을 해서 $mn, ..., mn, mx, ..., mx$와 같이 만들어서 해당 연산을 만들 수 있으므로, 연산을 한 번만 하는 것이 가능한가 확인해 보면 됩니다.

$mn$과 $mx$이외의 수가 존재하지 않으면 한 번에 가능하고 (왼쪽부터 $mn$과 $mx$중 큰 쪽의 수를 없애는 방향으로 합니다.) 이외의 수가 존재하면 $mn$과 $mx$이외의 수를 포함하지 않는 구간을 잡고 구간을 양쪽으로 늘려가면서 조건을 만족하도록 할 수 있는지 체크하면 됩니다.

코드가 더러운데 수정해보겠습니다...

5. 보물찾기

모든 정점의 차수가 $1$ 이상인 양방향 단순 그래프가 주어집니다. 각 정점은 Alice 혹은 Bob의 소유이고 정점 중 일부에는 보물이 존재합니다.

그래프의 한 정점에 말을 놓고 게임을 하는데, 각 턴이 시작할 때 해당 말이 올린 정점을 소유한 사람이 이웃한 간선 하나를 선택해 반대쪽 끝점으로 이동시킵니다. 이 때 보물이 있는 정점에 방문하면 보물을 하나 얻습니다.

$10^{100}$턴간 게임을 진행했을 때 $10^{90}$턴 이상에서 보물을 얻는다면 Alice의 승리, 아니면 Bob의 승리입니다.

모든 정점 각각에 대해 각 정점에 말을 놓고 게임을 시작할 때 누가 승리하는지 출력하세요.

풀이

• $A$만으로 연결된 크기 $2$ 이상의 컴포넌트에 보물이 있으면 해당 컴포넌트에서 시작하면 $A$가 이깁니다.
• $A$만으로 연결된 크기 $1$의 컴포넌트에 보물이 있으면 이웃한 정점 중 $A$가 승리하는 정점이 있으면 $A$가 이깁니다.
• $B$만으로 연결된 컴포넌트에 양쪽에 보물이 없는 간선이 존재하면 해당 컴포넌트에서 시작하면 $B$가 이깁니다.

이제 $A$만으로 연결된 보물이 없는 정점과, $B$만으로 연결된 양쪽에 보물이 없는 간선이 존재하지 않는 컴포넌트 두 개가 존재합니다. 이 나머지 컴포넌트에 대해서는 다음 전략을 취합니다.

• $A$는 $B$의 정점 중 보물이 있는 정점으로만 보내려고 합니다. (아니면, $B$가 단순히 이전 간선으로 돌려보내면 됩니다.)
• $B$는 보물이 없는 정점에서 시작해서, $A$의 보물이 없는 정점으로 보내려고 합니다. (아니면, $A$와 $B$가 단순히 이전 간선으로 돌려보내면 됩니다.)

이 나머지에 대해서

• $A$에서 나오는 정점이 존재하지 않거나, 모든 정점에서 $A$가 지면 $A$가 집니다.
• $B$에서 나오는 정점 중 $A$가 지는 정점이 존재하면 $A$가 집니다.

나머지는 결정되지 않은 정점들입니다. 이 경우 항상 $A$가 $B$의 정점 중 보물이 있는 정점으로 보낼 수 있음로, 무한번 보물을 모을 수 있고, $A$가 이기게 됩니다.

코드

1번

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

long long solve(vector<int> V, int S, int E)
{
    int N = V.size();
    vector<long long> X(N + 1, LLONG_MAX / 2), Y(N + 1, LLONG_MAX / 2), Z(N + 1, LLONG_MAX / 2);
    X[0] = Y[0] = Z[0] = 0;
    for (int i = 0; i < N; i++)
    {
        X[i + 1] = X[i] + (V[i] == 0 ? 0 : E);
        Y[i + 1] = min(X[i + 1], Y[i] + (V[i] == 1 ? 0 : S));
        Z[i + 1] = min(Y[i + 1], Z[i] + (V[i] == 0 ? 0 : E));
    }
    return Z[N];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t)
    {
        cout << "Case #" << t << '\n';
        int N, S, E;
        cin >> N >> S >> E;
        vector<int> V(N);
        for (int &v : V)
            cin >> v;
        cout << solve(V, S, E) << endl;
    }
}

2번

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

long long solve(vector<long long> W, vector<long long> Q)
{
    sort(Q.begin(), Q.end());
    int N = W.size();
    vector<int> V(N);
    iota(V.begin(), V.end(), 0);
    sort(V.begin(), V.end(), [&](int a, int b)
         { return W[a] < W[b]; });

    oset S;
    for (int i = 0; i < N; i++)
        S.insert(i);

    long long T = 0;
    long long until = 0;
    long long tp = 0;
    long long ans = 0;
    for (auto x : V)
    {
        long long ts = 1LL * (W[x] - T) * S.size();
        while (tp < (int)Q.size() && Q[tp] < until + ts)
        {
            int ret = *S.find_by_order((Q[tp] - until) % S.size());
            ans += ret;
            ++tp;
        }
        T = W[x];
        until += ts;
        S.erase(x);
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t)
    {
        cout << "Case #" << t << '\n';
        int N, Q;
        cin >> N >> Q;
        vector<long long> W(N);
        for (long long &w : W)
            cin >> w;
        vector<long long> Qry(Q);
        for (long long &q : Qry)
            cin >> q, --q;
        auto ret = solve(W, Qry) + Q;

        cout << ret << endl;
    }
}

3번

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

vector<double> rsolve(vector<int> X, vector<double> P, vector<int> pos)
{
    int N = X.size(), M = pos.size();
    vector<double> ans(M);
    vector<pair<bool, int>> V;
    for (int i = 0; i < N; i++)
        V.emplace_back(false, i);
    for (int j = 0; j < M; j++)
        V.emplace_back(true, j);
    auto gK = [&](pair<bool, int> A)
    {
        if (!A.first)
            return X[A.second];
        return pos[A.second];
    };
    sort(V.begin(), V.end(), [&](auto A, auto B)
         { return gK(A) < gK(B); });

    double accs = 0, accp = 0;
    for (auto [tp, id] : V)
    {
        if (tp)
        {
            ans[id] += accp * pos[id] - accs;
        }
        else
        {
            accs += P[id] * X[id];
            accp += P[id];
        }
    }
    accs = accp = 0;
    for (auto [tp, id] : V | views::reverse)
    {
        if (tp)
        {
            ans[id] += accs - accp * pos[id];
        }
        else
        {
            accs += P[id] * X[id];
            accp += P[id];
        }
    }
    return ans;
}

vector<double> solve(vector<pair<int, int>> XY, vector<double> P, vector<pair<int, int>> ZW)
{
    int N = XY.size(), M = ZW.size();
    vector<int> X, Y, Z, W;
    for (auto &[x, y] : XY)
        X.push_back(x), Y.push_back(y);
    for (auto &[z, w] : ZW)
        Z.push_back(z), W.push_back(w);
    auto r1 = rsolve(X, P, Z);
    auto r2 = rsolve(Y, P, W);
    vector<double> V(M);
    for (int i = 0; i < M; i++)
        V[i] = r1[i] + r2[i];
    return V;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t)
    {
        cout << "Case #" << t << '\n';
        int N;
        cin >> N;
        vector<pair<int, int>> XY(N);
        for (auto &[x, y] : XY)
            cin >> x >> y;
        vector<double> P(N);
        for (auto &p : P)
            cin >> p;
        int M;
        cin >> M;
        vector<pair<int, int>> ZW(M);
        for (auto &[z, w] : ZW)
            cin >> z >> w;
        auto ret = solve(XY, P, ZW);
        for (auto x : ret)
            cout << fixed << setprecision(7) << x << '\n';
        cout << flush;
    }
}

4번

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

const int MIN_OP = 1, MAX_OP = 2;

vector<tuple<int, int, int>> rsolve(vector<int> V)
{
    int N = V.size();
    int c1 = ranges::count(V, 1), cm1 = ranges::count(V, -1), c0 = ranges::count(V, 0);

    if (c0 == 0 && abs(c1 - cm1) <= 1)
        return {};

    if (c0 == 0)
    {
        int targ, ch;
        if (c1 > cm1)
            targ = 1, ch = (c1 - cm1) / 2;
        else
            targ = -1, ch = (cm1 - c1) / 2;

        // targ -> non_targ
        int op = targ == 1 ? MIN_OP : MAX_OP;

        int idx_non_targ = ranges::find(V, -targ) - V.begin();
        int l = idx_non_targ, r = idx_non_targ;
        int targ_cnt = 0;
        while (l > 0 && targ_cnt != ch)
        {
            if (V[--l] == targ)
                ++targ_cnt;
        }
        while (r < N - 1 && targ_cnt != ch)
        {
            if (V[++r] == targ)
                ++targ_cnt;
        }
        return {{op, l, r}};
    }
    if (c0 == 1 && c1 == cm1)
    {
        int idx_0 = ranges::find(V, 0) - V.begin();
        int l, r, op;
        if (idx_0 == 0)
            l = 0, r = 1, op = V[1] == 1 ? MAX_OP : MIN_OP;
        else
            l = idx_0 - 1, r = idx_0, op = V[idx_0 - 1] == 1 ? MAX_OP : MIN_OP;
        return {{op, l, r}};
    }
    {
        int l = N - 1, r = 0;
        for (int i = 0; i < N; i++)
            if (V[i] == 0)
                l = min(l, i), r = max(r, i);
        int targ = c1 > cm1 ? 1 : -1;
        int op = targ == 1 ? MIN_OP : MAX_OP;
        // targ -> non_targ

        // set rng_targ
        const int fr = max(c1, cm1) - (N + 1) / 2, to = max(c1, cm1) - N / 2;
        int targ_cnt = 0;
        for (int i = l; i <= r; i++)
            if (V[i] == targ)
                ++targ_cnt;
        const int cl = l, cr = r, ctarg_cnt = targ_cnt;

        for (int targ_mat : vector<int>({fr, to}))
        {
            for (bool ord : vector<bool>({true, false}))
            {
                int l = cl, r = cr, targ_cnt = ctarg_cnt;
                if (ord)
                    while (r < N - 1 && (targ_cnt != targ_mat || V[r + 1] != targ))
                    {
                        if (V[++r] == targ)
                            ++targ_cnt;
                    }
                while (l > 0 && (targ_cnt != targ_mat || V[l - 1] != targ))
                {
                    if (V[--l] == targ)
                        targ_cnt++;
                }
                if (!ord)
                    while (r < N - 1 && (targ_cnt != targ_mat || V[r + 1] != targ))
                    {
                        if (V[++r] == targ)
                            ++targ_cnt;
                    }
                if (targ_cnt == targ_mat)
                {
                    bool e_non_targ = false;
                    for (int i = l; i <= r; i++)
                        if (V[i] == -targ)
                            e_non_targ = true;
                    if (e_non_targ)
                    {
                        return {{op, l, r}};
                    }
                }
            }
        }
    }
    int mn_pos = ranges::find(V, -1) - V.begin(), mx_pos = ranges::find(V, 1) - V.begin();

    // [0, ..., c] [c+1, ..., N-1]
    int c = N / 2 - 1;
    if (mn_pos < mx_pos)
    {
        if (mn_pos <= c)
            return {{MAX_OP, mn_pos + 1, N - 1}, {MIN_OP, 0, c}};
        else
            return {{MIN_OP, 0, mn_pos}, {MAX_OP, c + 1, N - 1}};
    }
    else
    {
        if (mx_pos <= c)
            return {{MIN_OP, mx_pos + 1, N - 1}, {MAX_OP, 0, c}};
        else
            return {{MAX_OP, 0, mx_pos}, {MIN_OP, c + 1, N - 1}};
    }
}

bool verify(vector<int> V, vector<tuple<int, int, int>> R)
{
    for (auto [op, l, r] : R)
    {
        if (op == MIN_OP)
        {
            int mn = *min_element(V.begin() + l, V.begin() + r + 1);
            for (int i = l; i <= r; i++)
                V[i] = mn;
        }
        else
        {
            int mx = *max_element(V.begin() + l, V.begin() + r + 1);
            for (int i = l; i <= r; i++)
                V[i] = mx;
        }
    }
    return ranges::count(V, 0) == 0 && abs((int)ranges::count(V, 1) - (int)ranges::count(V, -1)) <= 1;
}


vector<tuple<int, int, int>> solve(vector<int> V)
{
    int mx = ranges::max(V);
    int mn = ranges::min(V);
    if (mx == mn)
        return {};
    vector<int> U;
    for (int v : V)
    {
        if (v == mx)
            U.push_back(+1);
        else if (v == mn)
            U.push_back(-1);
        else
            U.push_back(0);
    }
    return rsolve(U);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t)
    {
        cout << "Case #" << t << '\n';
        int N;
        cin >> N;
        vector<int> V(N);
        for (int &v : V)
            cin >> v;
        auto ret = solve(V);
        cout << ret.size() << endl;
        for (auto [tp, l, r] : ret)
            cout << tp << " " << l + 1 << " " << r + 1 << '\n';
        cout << flush;
    }
}

5번

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

enum STATE
{
    WIN,
    LOSE,
    UNK,
};

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

string solve(string AB, string T, vector<pair<int, int>> E)
{
    int N = AB.size();
    UFD ufd(N);
    vector<bool> non_star_edge(N);
    for (auto [u, v] : E)
        if (AB[u] == AB[v])
        {
            ufd.Union(u, v);
            if (T[u] == '.' && T[v] == '.' && AB[u] == 'B')
                non_star_edge[u] = non_star_edge[v] = true;
        }
    vector<int> sz(N), star(N), non_star(N);
    for (int i = 0; i < N; i++)
    {
        sz[ufd.Find(i)] += 1;
        if (T[i] == 'T')
            star[ufd.Find(i)] += 1;
        if (non_star_edge[i])
            non_star[ufd.Find(i)] += 1;
    }
    vector<STATE> ans(N, UNK);
    vector<int> As, Bs;
    for (int i = 0; i < N; i++)
        if (ufd.Find(i) == i)
        {
            if (AB[i] == 'A')
            {
                if (sz[i] >= 2 && star[i] >= 1)
                    ans[i] = WIN;
                // sz[i] == 1 && star[i] == 1: calculate after
                if (sz[i] >= 1 && star[i] == 0)
                {
                    As.push_back(i);
                    ans[i] = UNK; // (only outgoing to star)
                }
            }
            else
            {
                if (non_star[i])
                    ans[i] = LOSE;
                else
                    ans[i] = UNK, Bs.push_back(i); // outgoing only accounts for (non_star B -> non_star component A)
            }
        }
    vector<vector<int>> G(N), iG(N);
    vector<int> req_lose(N);
    for (auto b : Bs)
        req_lose[b] = 1;
    for (auto [u, v] : E)
        for (int i = 0; i < 2; ++i, swap(u, v))
        {
            int ux = ufd.Find(u), vx = ufd.Find(v);
            if (ux == vx)
                continue;
            assert(AB[ux] != AB[vx]);
            if (AB[u] == 'A' && star[ux] == 0 && T[v] == 'T' && !non_star[vx])
                G[ux].push_back(vx);
            if (AB[u] == 'B' && !non_star[u] && T[u] != 'T' && star[vx] == 0)
                G[ux].push_back(vx);
        }
    for (int i = 0; i < N; i++)
    {
        sort(G[i].begin(), G[i].end());
        G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end());
        for (int j : G[i])
            iG[j].push_back(i);
    }
    queue<int> Q;
    for (auto a : As)
    {
        req_lose[a] = G[a].size();
        if (req_lose[a] == 0)
            Q.emplace(a);
    }
    while (!Q.empty())
    {
        int a = Q.front();
        Q.pop();
        ans[a] = LOSE;
        for (auto b : iG[a])
            if (--req_lose[b] == 0)
                Q.push(b);
    }
    for (auto a : As)
        if (ans[a] == UNK)
            ans[a] = WIN;
    for (auto b : Bs)
        if (ans[b] == UNK)
            ans[b] = WIN;
    vector<vector<int>> rG(N);
    for (auto [u, v] : E)
        rG[u].push_back(v), rG[v].push_back(u);
    for (int i = 0; i < N; i++)
        if (AB[i] == 'A' && sz[i] == 1 && star[i] == 1)
        {
            for (auto x : rG[i])
                if (ans[ufd.Find(x)] == WIN)
                    ans[i] = WIN;
            if (ans[i] == UNK)
                ans[i] = LOSE;
        }

    string s;
    for (int i = 0; i < N; i++)
    {
        assert(ans[ufd.Find(i)] != UNK);
        if (ans[ufd.Find(i)] == WIN)
            s += 'A';
        else
            s += 'B';
    }

    return s;
}

int main()
{
    // check();
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t)
    {
        cout << "Case #" << t << '\n';
        int N, M;
        cin >> N >> M;
        string S, T;
        cin >> S >> T;
        vector<pair<int, int>> E(M);
        for (auto &[a, b] : E)
            cin >> a >> b, --a, --b;
        auto ret = solve(S, T, E);
        cout << ret << endl;
    }
}