개요

COTS 2025 대회에서 출제된 6개 문제(A~F)의 풀이와 구현 코드를 정리합니다. 각 문제는 서로 다른 알고리즘 기법을 요구하며, 복잡도와 구현 세부사항에 중점을 둡니다.

[COTS 2025] A - 상 배분 / Hijerarhija

트리 DP와 배낭 문제를 결합한 문제입니다. 각 노드에서 자식 노드들의 상태를 합치며 최적해를 구합니다.

const int MAXN = 5e3 + 5;
const int INF = 1e9 + 7;
int n, m, parent[MAXN], val[MAXN], cost[MAXN];
vector<int> children[MAXN];
int dp[MAXN][MAXN], cur[MAXN], nxt[MAXN];

void dfs(int u) {
    fill(nxt, nxt + m + 1, -INF);
    for (int i = 0; i < m; ++i) nxt[i + 1] = max(nxt[i + 1], cur[i]);
    for (int i = 0; i + cost[u] <= m; ++i)
        nxt[i + cost[u]] = max(nxt[i + cost[u]], cur[i] + val[u]);
    copy(nxt, nxt + m + 1, cur);
    copy(cur, cur + m + 1, dp[u]);
    for (int v : children[u]) {
        dfs(v);
        for (int i = 0; i <= m; ++i) cur[i] = max(cur[i], dp[u][i]);
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 2; i <= n; ++i) {
        cin >> parent[i];
        children[parent[i]].push_back(i);
    }
    for (int i = 1; i <= n; ++i) cin >> val[i];
    for (int i = 1; i <= n; ++i) cin >> cost[i];
    fill(cur, cur + m + 1, -INF);
    cur[0] = 0;
    dfs(1);
    int ans = 0;
    for (int i = 0; i <= m; ++i) ans = max(ans, cur[i]);
    cout << ans << endl;
}

[COTS 2025] B - 그래프 세기 / Promet

조합론과 DP를 활용하여 특정 성질을 만족하는 그래프의 개수를 세는 문제입니다. 뫼비우스 변환과 유사한 아이디어가 사용됩니다.

const int MAXN = 2e3 + 5;
int n, MOD;

int add(int a, int b) { return (a + b) % MOD; }
int sub(int a, int b) { return (a - b + MOD) % MOD; }
int mul(int a, int b) { return 1LL * a * b % MOD; }
int sgn(int x) { return (x & 1) ? MOD - 1 : 1; }
int pow2[MAXN];
int dp[MAXN][MAXN], f[MAXN];
int g[MAXN][MAXN], h[MAXN][MAXN];
int result[MAXN];

void solve() {
    cin >> n >> MOD;
    pow2[0] = 1;
    for (int i = 1; i <= n; ++i) pow2[i] = mul(pow2[i - 1], 2);
    dp[1][0] = 1;
    for (int i = 2; i <= n; ++i)
        for (int j = 0; j < i; ++j) {
            int val = dp[i - 1][j];
            if (j) val = add(val, dp[i - 1][j - 1]);
            dp[i][j] = mul(val, sub(pow2[i - 1 - j], 1));
        }
    for (int i = 2; i <= n; ++i)
        for (int j = 0; j < i; ++j)
            f[i] = add(f[i], mul(dp[i][j], sgn(j)));
    // ... (전체 코드는 생략, 핵심만 제시)
    for (int i = 0; i <= n; ++i) cout << result[i] << " ";
    cout << endl;
}

[COTS 2025] C - 최적 위치 찾기 / Vrsta

분할 정복과 쿼리 인터랙션을 이용하여 구간 내 최댓값의 위치를 효율적으로 찾는 문제입니다.

const int MAXN = 2048 + 5;
int n, q;
int visited[MAXN][MAXN], answer[MAXN][MAXN];

int query(int l, int r) {
    cout << "? " << l << " " << r << endl << flush;
    int x; cin >> x;
    return x;
}

void divide(int l, int r, int mid) {
    if (l >= r || visited[l][r]) return;
    int pos = query(l, r);
    if (pos < mid) {
        for (int i = l; i <= pos; ++i)
            for (int j = mid; j <= r; ++j)
                answer[i][j] = pos;
        divide(l, mid - 1, pos);
        divide(pos + 1, r, mid);
    } else {
        for (int i = l; i <= mid; ++i)
            for (int j = pos; j <= r; ++j)
                answer[i][j] = pos;
        divide(l, pos - 1, mid);
        divide(mid + 1, r, pos);
    }
    visited[l][r] = 1;
}

void solve() {
    // ... (전체 코드는 생략)
}

[COTS 2025] D - 나무 베기 / Stablo

분할 정복 기반의 트리 구성 문제로, 쿼리를 통해 노드 간 관계를 파악하며 트리를 복원합니다.

const int MAXN = 1e3 + 5;
const int INF = 1e9 + 7;
int n, parent[MAXN], idx[MAXN], values[MAXN];
vector<int> edges[MAXN];
int visited[MAXN], sz[MAXN], best, pre;

int query(int a, int b, int c) {
    cout << "? " << a << " " << b << " " << c << endl << flush;
    int x; cin >> x;
    return x;
}

void merge_sort(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int p = l, q = mid + 1, k = 0;
    while (p <= mid || q <= r) {
        if (q > r || (p <= mid && query(1, idx[p], idx[q]) <= 1))
            values[++k] = idx[p++];
        else
            values[++k] = idx[q++];
    }
    for (int i = 1; i <= k; ++i) idx[l + i - 1] = values[i];
}

void add_edge(int u, int v) { /* edges 추가 */ }

void find_centroid(int u, int f, int total) { /* 중심 찾기 */ }

void solve() {
    // ... (전체 코드는 생략)
}

[COTS 2025] E - 잔디 관찰 / Trava

세그먼트 트리와 펜윅 트리를 함께 사용하여 구간 내 원소 값의 변화를 추적하고 쿼리를 처리합니다.

const int MAXN = 5e5 + 5;
int n, q, arr[MAXN];

struct SegTree {
    int left[MAXN * 4], right[MAXN * 4], maxv[MAXN * 4];
    void build(int u, int l, int r) {
        left[u] = l; right[u] = r;
        if (l == r) { maxv[u] = arr[l]; return; }
        int mid = (l + r) / 2;
        build(u * 2, l, mid);
        build(u * 2 + 1, mid + 1, r);
        maxv[u] = max(maxv[u * 2], maxv[u * 2 + 1]);
    }
    void update(int u, int p) {
        if (left[u] == right[u]) { maxv[u]++; return; }
        int mid = (left[u] + right[u]) / 2;
        if (p <= mid) update(u * 2, p);
        else update(u * 2 + 1, p);
        maxv[u] = max(maxv[u * 2], maxv[u * 2 + 1]);
    }
    int query_left(int u, int r, int x) { /* ... */ }
    int query_right(int u, int l, int x) { /* ... */ }
} seg;

struct Fenwick {
    long long bit[MAXN];
    void add(int idx, long long val) { for (; idx <= n; idx += idx & -idx) bit[idx] += val; }
    void range_add(int l, int r, long long val) { add(l, val); add(r + 1, -val); }
    long long sum(int idx) { long long res = 0; for (; idx; idx -= idx & -idx) res += bit[idx]; return res; }
} fen[2];

void solve() {
    // ... (전체 코드는 생략)
}

[COTS 2025] F - 청소기 / Usisavač

트리에서 깊이 정보를 활용하여 주어진 제약 내에서 최소 이동 거리를 계산하는 문제입니다.

const int MAXN = 5e5 + 5;
int n, q;
int head[MAXN], nxt[MAXN * 2], to[MAXN * 2], edge_cnt;
int depth[MAXN], cnt[MAXN];

void add_edge(int u, int v) {
    nxt[++edge_cnt] = head[u];
    to[edge_cnt] = v;
    head[u] = edge_cnt;
}

void dfs(int u, int p) {
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == p) continue;
        dfs(v, u);
        depth[u] = max(depth[u], depth[v] + 1);
    }
}

void solve() {
    cin >> n >> q;
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        add_edge(u, v); add_edge(v, u);
    }
    dfs(1, 0);
    for (int i = 2; i <= n; ++i) cnt[depth[i]]++;
    for (int i = n; i >= 0; --i) cnt[i] += cnt[i + 1];
    while (q--) {
        int x; cin >> x;
        if (depth[1] <= x) {
            cout << 2 * (n - 1) - depth[1] << " ";
        } else {
            long long ans = 2 * (n - 1) + 2 * cnt[x];
            ans -= x + (depth[1] - x);
            cout << ans << " ";
        }
    }
}