LGCPC 2024 본선 후기

프리즈 후, 최종 42등

 

예선에서 겨우겨우 41등을 하고 본선에 다녀왔다. 팀노트를 챙겨와야 하는지를 몰라서 당황했지만, 다행히 팀노트가 필요한 문제는 나오지 않았다(D가 그런 문제였을 수도 있다). B까지는 무난하게 풀고, D를 먼저 긁었다. 그리고 남은 시간 동안 C의 풀태를 바로 시도했는데, 예제가 나오지 않으면서 끝났다. C를 대회 중에 풀기는 어려웠을 것 같아서 아쉽지는 않다.

 

LG가 첫 대회라 그런지 준비를 많이 해와서, 문제 외적으로도 기분 좋은 대회였다. 문제 풀 시간을 조금만 더 줬으면 좋겠다.

 

 

A. 셔플 기계

사이클을 여러 번 시행하는 것은 다양한 방법으로 할 수 있는데, 나는 그중 가장 생각 없이 코딩할 수 있는 희소 배열을 택하였다.

 

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;

int a[N][N], f[N][30];

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m, k; cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) cin >> a[i][j];
    }
    
    vector<int> ans(n + 1);
    iota(ans.begin(), ans.end(), 0);
    while (k--) {
        int x, y; cin >> x >> y;
        for (int i = 1; i <= n; i++) f[i][0] = a[x][i];
        for (int j = 1; j < 30; j++) {
            for (int i = 1; i <= n; i++) {
                f[i][j] = f[f[i][j - 1]][j - 1];
            }
        }
        vector<int> tmp(n + 1);
        for (int i = 1; i <= n; i++) {
            int j = i;
            for (int b = 0; b < 30; b++) {
                if (y & (1 << b)) j = f[j][b];
            }
            tmp[j] = ans[i];
        }
        swap(ans, tmp);
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}

 

 

B. 마법 구슬

그림을 열심히 그려보면 계단 구간들을 잘 관리하면 된다는 걸 알 수 있다. 구현하다 보니 구간의 병합(삭제)이 필요해서, 셋으로 관리할까 하다가 연결 리스트를 썼다. 처음에 인덱스들을 더하고 시작하면 구현이 간단해지는 모양이다.

 

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

struct info {
    int l, r; ll s;
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<info> v;
    for (int i = 1; i <= n; i++) {
        if (i > 1 && a[i - 1] - a[i] == 1) v.back().r++;
        else v.push_back({i, i, a[i]});
    }
    n = v.size();

    int k = 0;
    for (int i = 0; i + 1 < n; i++) {
        if (v[i].s - v[i].r + v[i].l > v[i + 1].s) k = i + 1;
        else break;
    }

    vector<int> L(n), R(n);
    for (int i = 0; i < n; i++) L[i] = i - 1, R[i] = i + 1;
    L[0] = -1, R[n - 1] = -1;

    ll x = 0;
    while (q--) {
        int t; cin >> t;
        if (t & 1) {
            ll y; cin >> y; x += y;
            while (1) {
                ll p = ~L[k] ? v[L[k]].s - v[L[k]].r + v[L[k]].l - v[k].s - 1 : 1e12;
                ll q = ~R[k] ? v[R[k]].s - v[k].s + v[k].r - v[k].l + 1 : 1e12;
                ll z = v[k].r - v[k].l + 1;
                if (x < min(p, q) * z) {
                    v[k].s += x / z, x %= z;
                    break;
                }
                if (p <= q) {
                    x -= p * z;
                    v[L[k]].r = v[k].r;
                    R[L[k]] = R[k];
                    if (~R[k]) L[R[k]] = L[k];
                    k = L[k];
                }
                if (p >= q) {
                    if (p > q) x -= q * z;
                    v[k].r = v[R[k]].r;
                    if (p > q) v[k].s += q;
                    if (~R[R[k]]) L[R[R[k]]] = k;
                    R[k] = R[R[k]];
                    while (~R[k] && v[k].s - v[k].r + v[k].l > v[R[k]].s) k = R[k];
                }
            }
        }
        else {
            cout << v.front().s << '\n';
        }
    }
}

 

 

C. 도시

내 풀이는 정해와 많이 다른데, 이는 내가 bitmask DP를 풀어본 적이 없어서다. $dp[i][j][mask][k]$를 정의하고($mask$는 끝의 $3 \times 3$개의 칸을 관리한다), 2차원 누적합을 계산하는 것처럼 인접한 3개의 dp값을 이용해 전이할 수 있다. 나중에 생각해봤는데, 전이할 때 $dp[i][j][*][k]$의 최댓값을 또 전처리해야 $O(K^2)$에 전이할 수 있다. 사실 이건 입풀이고 진짜 되는지는 구현해봐야 안다. 아래는 대회 중에 구현하다 실패한 코드.

 

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

int a[13][13], c[13][13], dp[13][13][512][51];
int dx[] = {-2, -2, -2, -1, -1, -1, 0, 0, 0};
int dy[] = {-2, -1, 0, -2, -1, 0, -2, -1, 0};

int st(vector<int> v) {
    int ret = 0;
    for (int i = 0; i < 8; i++) if (v[i]) ret += 1 << i;
    return ret;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> c[i][j];
    int bb = (1 << 1) + (1 << 3) + (1 << 4) + (1 << 5) + (1 << 7);

    memset(dp, -1, sizeof dp);
    for (int i = 0; i <= n; i++) dp[i][0][0][m] = dp[0][i][0][m] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int b = 0; b < 512; b++) {
                if (i < 3 && b & 1 + 2 + 4) continue;
                if (i < 2 && b & 8 + 16 + 32) continue;
                if (j < 3 && b & 1 + 8 + 64) continue;
                if (j < 2 && b & 2 + 16 + 128) continue;
                for (int k = 0; k <= m; k++) {
                    int fl = 0;
                    for (int t = 0; t < 9; t++) {
                        int pi = i + dx[t], pj = j + dy[t];
                        if (pi > 0 && pj > 0) fl |= a[pi][pj] << t;
                    }
                    if ((b & fl) != fl) continue;
                    for (int lb = 0; lb < 8; lb++) {
                        for (int lk = 0; lk <= m; lk++) {
                            for (int ub = 0; ub < 8; ub++) {
                                for (int uk = 0; uk <= m; uk++) {
                                    for (int db = 0; db < 2; db++) {
                                        int dk = lk + uk + (!a[i][j] && (b & (1 << 8))) - k;
                                        if (dk < 0 || dk > m) continue;
                                        int llb = st({lb & 1, b & 1, b & 2, lb & 2, b & 8, b & 16, lb & 4, b & 64, b & 128});
                                        int uub = st({ub & 1, ub & 2, ub & 4, b & 1, b & 2, b & 4, b & 8, b & 16, b & 32});
                                        int ddb = st({db & 1, ub & 1, ub & 2, lb & 1, b & 1, b & 2, lb & 2, b & 8, b & 16});
                                        if (~dp[i][j - 1][llb][lk] && ~dp[i - 1][j][uub][uk] && ~dp[i - 1][j - 1][ddb][dk]) {
                                            int val = (b & bb) == bb ? c[i - 1][j - 1] : 0;
                                            dp[i][j][b][k] = max(dp[i][j][b][k], dp[i][j - 1][llb][lk] + dp[i - 1][j][uub][uk] - dp[i - 1][j - 1][ddb][dk] + val);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    int ans = 0;
    for (int b = 0; b < 512; b++) {
        for (int k = 0; k <= m; k++) {
            ans = max(ans, dp[n][n][b][k]);
        }
    }
    cout << ans << '\n';
}

 

 

D. 연결하기

섭태 1은 다익스트라, 섭태 2, 3은 MST로 해결할 수 있다. 섭태 5까지도 어렵지 않게 풀 수 있지만 C를 볼 시간을 확보하기 위해 짜지 않았다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
const int N = 10001;

int n, m, k;
vector<pair<int, int>> ad[N];
int a[N];

void solve1() {
    vector<ll> dp(n + 1, 1e18); dp[a[1]] = 0;
    priority_queue<pli, vector<pli>, greater<pli>> pq; pq.push({0, a[1]});
    while (pq.size()) {
        auto [dst, u] = pq.top(); pq.pop();
        if (dp[u] != dst) continue;
        for (auto &[v, w] : ad[u]) if (dst + w < dp[v]) {
            dp[v] = dst + w; pq.push({dp[v], v});
        }
    }
    cout << dp[a[2]] << '\n';
}

int par[N];

int fnd(int v) {
    if (par[v] == v) return v;
    return par[v] = fnd(par[v]);
}
bool uni(int u, int v) {
    u = fnd(u), v = fnd(v);
    if (u == v) return 0;
    par[v] = u;
    return 1;
}

void solve2() {
    vector<pair<int, pair<int, int>>> e;
    for (int u = 1; u <= n; u++) {
        for (auto &[v, w] : ad[u]) if (u < v) {
            e.push_back({w, {u, v}});
        }
    }
    sort(e.begin(), e.end());
    iota(par, par + n + 1, 0);
    ll ans = 0;
    for (auto &[w, uv] : e) {
        auto &[u, v] = uv;
        if (uni(u, v)) ans += w;
    }
    cout << ans << '\n';
}

void solve3() {
    vector<int> chk(n + 1);
    for (int i = 1; i <= k; i++) chk[a[i]] = 1;
    vector<int> vt;
    for (int i = 1; i <= n; i++) if (!chk[i]) vt.push_back(i);
    
    int nn = vt.size(); ll ans = 1e18;
    for (int i = 0; i < 1 << nn; i++) {
        int t = nn;
        for (int j = 0; j < nn; j++) if (i & (1 << j)) chk[vt[j]] = 1, t--;
        vector<pair<int, pair<int, int>>> e;
        for (int u = 1; u <= n; u++) if (chk[u]) {
            for (auto &[v, w] : ad[u]) if (u < v && chk[v]) {
                e.push_back({w, {u, v}});
            }
        }
        sort(e.begin(), e.end());
        iota(par, par + n + 1, 0);
        ll sum = 0; int cnt = 1;
        for (auto &[w, uv] : e) {
            auto &[u, v] = uv;
            if (uni(u, v)) sum += w, cnt++;
        }
        if (cnt == n - t) ans = min(ans, sum);
        for (int j = 0; j < nn; j++) if (i & (1 << j)) chk[vt[j]] = 0;
    }
    cout << ans << '\n';
}

void solve5() {

}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    while (m--) {
        int u, v, w; cin >> u >> v >> w;
        ad[u].push_back({v, w});
        ad[v].push_back({u, w});
    }
    cin >> k;
    for (int i = 1; i <= k; i++) cin >> a[i];

    if (k == 2) solve1();
    else if (k == n) solve2();
    else if (n <= 30 && k >= n - 20) solve3();
    else if (m == n - 1) solve5();
}