총점: \(100+100+30+45=275\) 시작 10분 동안 문제 A에 접근했으나, 한 시간 후 포기하고 다른 문제로 이동. 문제 B를 빠르게 해결한 후 C에 도전하였으나 실패. D의 폭력적인 해법을 작성하고 남은 30분 동안 다시 A를 시도.

A: H 군의 블록

상단과 하단의 숫자를 모두 세그먼트 트리에 추가합니다. 만약 숫자가 두 번 이상 등장하면 이를 후보로 설정하며, 각 단계에서 최소 값을 선택하면서 그와 인접한 숫자들을 포함시키는 방식으로 진행합니다.

코드 보기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct SegmentTree {
    int l, r, cnt;
    pair<int, int> mn;
} tr[800005];

void build(int l, int r, int i) {
    tr[i] = {l, r, 0, {INT_MAX, 0}};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, i << 1);
    build(mid + 1, r, i << 1 | 1);
}

void update(int p, int k, int i) {
    if (tr[i].l == tr[i].r) {
        tr[i].cnt += k;
        if (tr[i].cnt >= 2) tr[i].mn = {p, tr[i].l};
        else tr[i].mn = {INT_MAX, 0};
        return;
    }
    if (p <= tr[i << 1].r) update(p, k, i << 1);
    else update(p, k, i << 1 | 1);
    tr[i].mn = min(tr[i << 1].mn, tr[i << 1 | 1].mn);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a[m + 1], pos[n + 1];
    for (int i = 1; i <= m; ++i) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            cin >> x;
            a[i].push_back(x);
            pos[x].push_back({i, a[i].size() - 1});
        }
    }
    for (int i = 1; i <= n; ++i) sort(pos[i].begin(), pos[i].end());
    build(1, n, 1);
    for (int i = 1; i <= m; ++i) {
        update(a[i][0], 1, 1);
        if (a[i].size() > 1) update(a[i].back(), 1, 1);
    }
    // 결과 출력 부분 생략
}

B: H 군의 트리

해결 방법은 트리의 간선을 끊거나 사이클을 분리하는 것입니다. 사이클을 체인으로 변환하여 투 포인터 기법을 사용할 수 있습니다.

코드 보기

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

struct Edge { int to, next; };
Edge e[400005];
int head[200005], idx = 0, size[200005], ans = INT_MAX;

void addEdge(int u, int v) {
    e[++idx] = {v, head[u]};
    head[u] = idx;
}

void dfs(int u, int fa) {
    size[u] = a[u];
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v != fa) {
            dfs(v, u);
            size[u] += size[v];
        }
    }
    if (!inCycle[u]) ans = min(ans, abs(sum - 2 * size[u]));
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], sum += a[i];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }
    // DFS 및 결과 처리 부분 생략
    cout << ans;
    return 0;
}

C: H 군의 문자열

문제의 답이 여러 가지 연산에 대응될 수 있음을 발견했습니다. 경쟁 중에는 가능한 모든 연산을 고려하려고 했지만 성공하지 못했습니다. 대신 가능한 모든 유효한 결과를 카운팅하는 방식으로 접근하였습니다.

D: H 군의 케이크

WQS 이진 탐색을 활용하여 문제를 해결하였습니다.