문제 A: 점 쌍의 각도 최적화

이 문제는 두 점 사이의 관계를 최적화하는 전형적인 그리디 알고리즘 문제입니다. 데이터 범위를 고려했을 때 $O(n \log n)$ 시간 복잡도가 필요하며, 정렬을 활용해야 합니다.

핵심 아이디어는 좌표축을 45도 회전시키는 것입니다. 기존 좌표 $(x, y)$를 $(x+y, x-y)$로 변환하면, $y=x$ 또는 $y=-x$에 가장 가까운 값을 찾는 문제가 됩니다. 변환된 좌표를 기준으로 정렬한 뒤 인접한 두 점만 확인하면 최적의 해를 구할 수 있습니다.

• 40pts: 모든 점 쌍을 전수 조사하여 $O(n^2)$으로 해결합니다.
• 80pts: $x=y$ 혹은 $x=-x$일 때 최댓값 $\sqrt{2}$를 가짐을 이용합니다. 즉, $x_i + y_i = x_j + y_j$ 또는 $x_i - y_i = x_j - y_j$인 경우를 찾습니다.
• 100pts: 모든 점을 $x_i + y_i$ 기준 또는 $x_i - y_i$ 기준으로 정렬합니다. 그 후 인접한 노드들 사이의 값 중 최댓값을 선택합니다. 이는 두 점의 연결선이 $45^\circ$ 또는 $135^\circ$에 가까울수록 유리하다는 성질을 이용한 것입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point {
    long long x, y;
    int id;
};

double calculate_val(const Point& p1, const Point& p2) {
    double manhattan = abs(p1.x - p2.x) + abs(p1.y - p2.y);
    double euclidean = sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
    return manhattan / euclidean;
}

void solve_a() {
    int n;
    if (!(cin >> n)) return;
    vector<Point> pts(n);
    for (int i = 0; i < n; ++i) {
        cin >> pts[i].x >> pts[i].y;
        pts[i].id = i;
    }

    auto solve_with_sort = [&](auto field_func) {
        vector<pair<long long, int>> transformed(n);
        for (int i = 0; i < n; ++i) {
            transformed[i] = {field_func(pts[i]), i};
        }
        sort(transformed.begin(), transformed.end());
        double local_max = -1.0;
        for (int i = 1; i < n; ++i) {
            local_max = max(local_max, calculate_val(pts[transformed[i-1].second], pts[transformed[i].second]));
        }
        return local_max;
    };

    double ans = max(solve_with_sort([](Point p) { return p.x + p.y; }),
                     solve_with_sort([](Point p) { return p.x - p.y; }));
    
    printf("%.15lf\n", ans);
}

int main() {
    int t;
    if (scanf("%d", &t) != EOF) {
        while (t--) solve_a();
    }
    return 0;
}

문제 B: 트리 구성 (Construction)

수론적 성질을 이용한 구성 문제입니다. $n$이 짝수일 때는 조건을 만족하는 홀수 개의 간선을 가질 수 없으므로 해가 존재하지 않습니다.

$n$이 홀수일 때, $\gcd(n, k)$를 기준으로 행렬을 구성하여 생각할 수 있습니다. 예를 들어 $n=25, k=5$라면 각 원소를 $5$의 배수 차이로 배열합니다. 모든 점을 오른쪽 아래 대각선 방향의 점과 연결하면 여러 개의 대각선 체인이 생깁니다. 이 체인들을 다시 적절히 연결하여 하나의 트리를 완성합니다.

#include <iostream>
#include <vector>

using namespace std;

void solve_b() {
    int n, k;
    cin >> n >> k;
    if (n % 2 == 0) {
        cout << -1 << endl;
        return;
    }
    cout << n / 2 << endl;

    vector<int> next_node(n);
    for (int i = 0; i < n; ++i) next_node[i] = (i + k) % n;

    int cycle_len = 1;
    int curr = k;
    while (curr != 0) {
        curr = (curr + k) % n;
        cycle_len++;
    }
    int group_cnt = n / cycle_len;

    if (group_cnt == 1) {
        int u = 0;
        for (int i = 1; i < cycle_len; i += 2) {
            cout << u << " " << next_node[u] << endl;
            u = next_node[next_node[u]];
        }
        return;
    }

    for (int i = 0; i < group_cnt - 1; ++i) {
        int u = i, v = next_node[i + 1];
        for (int j = 2; j < cycle_len; j += 2) {
            cout << u << " " << v << endl;
            u = next_node[next_node[u]];
            v = next_node[next_node[v]];
        }
    }
    int u_top = next_node[0], v_top = next_node[1];
    for (int i = 2; i <= cycle_len; i += 2) {
        cout << u_top << " " << v_top << endl;
        u_top = next_node[next_node[u_top]];
        v_top = next_node[next_node[v_top]];
    }
    for (int i = 1; i < group_cnt; i += 2) {
        cout << i << " " << i + 1 << endl;
    }
}

int main() {
    solve_b();
    return 0;
}

문제 C: 괄호 시퀀스 확률 DP

괄호 시퀀스가 생성될 때, 최소 접두사 합이 0 이상이고 최종 합이 0이어야 한다는 조건을 활용합니다. '()' 삽입은 접두사 합 $x$를 $[x, x+1, x]$로, ')(' 삽입은 $[x, x-1, x]$로 바꿉니다.

$f_{n,x}$를 현재 접두사 합이 $x$일 때 $n$번의 조작 후 모든 원소가 0 이상일 확률로 정의합니다. $O(n^4)$ DP를 보조 배열 $g$를 이용해 $O(n^3)$으로 최적화할 수 있습니다.

#include <iostream>
#include <vector>

using namespace std;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= 998244353;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 998244353;
        base = (base * base) % 998244353;
        exp /= 2;
    }
    return res;
}

const int MOD = 998244353;
long long f[505][505], g[505][505], comb[505][505];

void solve_c() {
    int n;
    long long x_val, y_val;
    cin >> n >> x_val >> y_val;
    long long p = (x_val * power(y_val, MOD - 2)) % MOD;

    for (int i = 0; i <= n; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; j++)
            comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
    }

    for (int i = 0; i <= n; i++) f[0][i] = g[0][i] = 1;

    for (int i = 1; i <= n; i++) {
        for (int x = 0; x <= n; x++) {
            for (int j = 0; j < i; j++) {
                long long term = (p * f[j][x + 1]) % MOD;
                if (x > 0) term = (term + (MOD + 1 - p) * f[j][x - 1]) % MOD;
                f[i][x] = (f[i][x] + term * comb[i - 1][j] % MOD * g[i - j - 1][x]) % MOD;
            }
            for (int j = 0; j <= i; j++)
                g[i][x] = (g[i][x] + comb[i][j] * f[j][x] % MOD * f[i - j][x]) % MOD;
        }
    }

    long long total_ways = 1;
    for (int i = 1; i < 2 * n; i += 2) total_ways = (total_ways * i) % MOD;
    cout << (f[n][0] * power(total_ways, MOD - 2)) % MOD << endl;
}

int main() {
    solve_c();
    return 0;
}

문제 D: 마법 수열의 최소 비용

이 문제는 수열의 총 변동량(Total Variation)을 제한하면서 합을 최소화하는 문제입니다. 조건 $\sum |b_i - b_{i+1}| \leq 2M$을 만족하도록 원본 수열 $a$를 수정해야 합니다.

탐욕적인 방법으로, 변동량을 줄이기 위해 가장 짧은 구간부터 값을 증가시켜 인접한 값과 맞추는 과정을 반복합니다. 이는 데카르트 트리(Cartesian Tree) 구조와 유사하며, 우선순위 큐를 사용하여 효율적으로 구현할 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>

using namespace std;

struct Segment {
    int length;
    long long diff;
    int left_idx;
    bool operator>(const Segment& other) const {
        return length > other.length;
    }
};

void solve_d() {
    int n;
    cin >> n;
    vector<long long> a(n + 2);
    a[0] = a[n + 1] = 3e9;
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> L(n + 2), R(n + 2);
    iota(L.begin(), L.end(), 0);
    iota(R.begin(), R.end(), 0);

    auto find_root = [](int x, vector<int>& parent) {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    };

    long long current_tv = 0;
    for (int i = 0; i <= n; i++) current_tv += abs(a[i + 1] - a[i]);

    priority_queue<Segment, vector<Segment>, greater<Segment>> pq;
    for (int i = 1; i <= n; i++) {
        if (a[i] < a[i-1] && a[i] < a[i+1]) {
            int r = i;
            while(r + 1 <= n && a[r+1] == a[i]) r++;
            pq.push({r - i + 1, min(a[i-1], a[r+1]) - a[i], i});
            i = r;
        }
    }

    long long target_tv = 6e9;
    while (current_tv > target_tv && !pq.empty()) {
        Segment seg = pq.top(); pq.pop();
        int l = seg.left_idx;
        int r = l + seg.length - 1;
        long long h = min(a[l-1], a[r+1]);
        
        if (current_tv - (h - a[l]) * 2 <= target_tv) {
            a[l] += (current_tv - target_tv + 1) / 2;
            break;
        }
        current_tv -= (h - a[l]) * 2;
        // 구간 병합 로직 생략 (핵심 아이디어 위주)
    }
    // 최종 합 계산 후 출력
}