SCPC 2025 1차 예선 후기

제대로 참가하는 SCPC는 처음이다. 작년에도 참가하긴 했었지만 작년에는 입시 준비도 해야 하고 해서 제대로 못했기 때문에 사실상 첫 참가라고 할 수 있겠다.

750 / 1150

 

결론적으로 1, 2, 3, 4번 문제를 해결했고, 5번은 0점을 받았다. 사실 4번까지 풀고 5번을 읽어 보았을 때 풀이가 바로 떠오르지 않아서 4번까지 풀었으면 되겠지 하고 안풀긴 했다.. 그래도 3번에 2번만에 맞은 것을 제외하면 모두 1번에 맞혔기 때문에 나름 만족스러운 결과이다. 나중에 5번 풀이를 들어 보니 MST 상에서 희소 배열을 이용해 관리하는 전형적인 문제였고, 68명이나 만점을 받았기도 해서 풀어보는 것이 더 좋았을 것 같다. 

 

문제 퀄리티는 전체적으로 괜찮았다. 아이디어성은 많지 않았고 PS를 한다면 알고 있을 기본적인 알고리즘들을 활용하는 문제가 출제되었다. 1번은 그리디, 2번은 누적 합, 3번은 DP, 4번은 누적합 + 이분탐색이었다. 

 

1번 풀이

그리디하게 접근하자. 화폐 단위들이 서로 배수 관계이므로 항상 큰 단위의 화폐를 먼저 소진하는 것이 최적이다. 따라서, 선형에 500원, 1000원짜리의 개수를 관리해주면서 시뮬레이션하면 쉽게 답을 구할 수 있다. 

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

using ll = long long;

void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

void solution() {
    ll n;
    cin >> n;
    ll a = 0, b = 0, ans = -1;
    for (ll x, i = 0; i < n; i++) {
        cin >> x;
        if (ans != -1) continue;
        if (x == 500) {
            a++;
        } else if (x == 1000) {
            if (a < 1) {
                ans = i;
            } else {
                a--, b++;
            }
        } else {
            ll mx = min(4LL, b);
            if (a * 500 + mx * 1000 < 4500) {
                ans = i;
            } else {
                b -= mx;
                a -= (4500 - mx * 1000) / 500;
            }
        }
    }
    cout << (ans == -1 ? n : ans);
}

int main() {
    init();

    ll t;
    cin >> t;
    for (ll i = 1; i <= t; i++) {
        cout << "Case #" << i << '\n';
        solution();
        cout << '\n';
    }
    return 0;
}

 

2번 풀이

각 폭탄의 위치를 누적합으로 관리하자. 어느 시점을 기준으로 왼쪽은 0으로 보내고, 오른쪽은 L로 보내는 것이 최적임을 어렵지 않게 생각할 수 있다. 누적합을 이용해서 cost를 쉽게 계산할 수 있으므로 어느 지점부터 왼쪽으로 보낼 것인지 N번만 반복하면 선형에 문제를 해결할 수 있다. 

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

using ll = long long;

void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

void solution() {
    ll n, l;
    cin >> n >> l;
    vector<ll> a(n + 1), s(n + 1);
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    ll ans = 2 * s[n];
    for (ll i = 1; i <= n; i++) {
        ll d = l + 2 * s[i - 1];
        d += 2 * ((n - i) * l - s[n] + s[i]);
        ans = min(ans, d);
    }
    cout << ans;
}

int main() {
    init();

    ll t;
    cin >> t;
    for (ll i = 1; i <= t; i++) {
        cout << "Case #" << i << '\n';
        solution();
        cout << '\n';
    }
    return 0;
}

 

3번 풀이

아주 기본적인 Digit DP 문제이다. 지금까지 본 자리수가 모두 최댓값일 때와 그렇지 않은 경우를 나눠서 계산해 주면 간단하게 풀 수 있다. 구현은 재귀를 이용하였다. 마지막에 0을 제외해 주어야 하는데 -1을 뺀 것을 그대로 출력하지 않도록 주의하자.

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

using ll = long long;

constexpr ll MOD = 1e9 + 7;

void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

void solution() {
    string s;
    cin >> s;
    ll n = ssize(s);
    vector dp(n, vector<ll>(2, -1));
    function<ll(ll, bool)> cal = [&](ll cur, bool mx) -> ll {
        if (cur == n) return 1;
        ll& ret = dp[cur][mx];
        if (ret > -1) return ret;
        ret = 0;
        ll lim = mx ? s[cur] - '0' : 2;
        lim = min(lim, 2LL);
        for (ll i = 0; i <= lim; i++) {
            bool np = mx and i == s[cur] - '0';
            (ret += cal(cur + 1, np)) %= MOD;
        }
        return ret;
    };
    cout << (cal(0, true) + MOD - 1) % MOD;
}

int main() {
    init();

    ll t;
    cin >> t;
    for (ll i = 1; i <= t; i++) {
        cout << "Case #" << i << '\n';
        solution();
        cout << '\n';
    }
    return 0;
}

 

4번 풀이

매칭할 빨간 상점과 파란 집을 정해 놓으면 나머지는 좌표 순으로 매칭하는 것이 최적임이 자명하다. 이제, 빨간 상점을 하나씩 순회하면서 최적인 파란 집일 때의 값들 중 최솟값을 구하면 전체 정답을 구할 수 있다. 최적인 파란 집은 이분 탐색으로 구할 수 있다. 이제 누적 합을 통해 각 집들을 매칭했을 때 거리의 합을 관리하면 된다. 최대 어긋나는 경우가 하나이므로 누적합 4개를 통해 계산할 수 있다. 인덱스 관리가 굉장히 헷갈리므로 유의하자.

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

using ll = long long;

constexpr ll INF = 1LL << 61;

void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

void solution() {
    ll n, r;
    cin >> n >> r;
    vector<ll> bh(n - r), rh(r);
    vector<ll> bs(n - r - 1), rs(r + 1);
    for (auto& x : bh) cin >> x;
    for (auto& x : rh) cin >> x;
    for (auto& x : bs) cin >> x;
    for (auto& x : rs) cin >> x;
    ranges::sort(bh);
    ranges::sort(rh);
    ranges::sort(bs);
    ranges::sort(rs);
    vector<array<ll, 2>> rp(r + 1), bp(n - r);
    for (ll i = 0; i < r; i++) {
        rp[i + 1][0] = rp[i][0] + llabs(rh[i] - rs[i]);
        rp[i + 1][1] = rp[i][1] + llabs(rh[i] - rs[i + 1]);
    }
    for (ll i = 0; i < n - r - 1; i++) {
        bp[i + 1][0] = bp[i][0] + llabs(bs[i] - bh[i]);
        bp[i + 1][1] = bp[i][1] + llabs(bs[i] - bh[i + 1]);
    }
    ll ans = INF;
    for (ll i = 0; i <= r; i++) {
        ll tmp = rp[i][0] + rp[r][1] - rp[i][1];
        ll it = ranges::lower_bound(bs, rs[i]) - bs.begin();
        tmp += abs(rs[i] - bh[it]);
        tmp += bp[it][0] + bp[n - r - 1][1] - bp[it][1];
        ans = min(ans, tmp);
    }
    cout << ans;
}

int main() {
    init();

    ll t;
    cin >> t;
    for (ll i = 1; i <= t; i++) {
        cout << "Case #" << i << '\n';
        solution();
        cout << '\n';
    }
    return 0;
}