최근 진행된 Codeforces 대회들의 주요 문제 풀이를 모아서 정리했습니다. 각 문제는 배열 처리, 구간 합, 그리디 알고리즘 등의 기법을 활용하여 효율적으로 해결할 수 있습니다.

Educational Codeforces Round 132 (Div. 2) – B번

수열이 주어질 때 특정 구간에서 인접 원소 간 차이의 합을 구하는 문제입니다. 오른쪽으로 이동할 때 증가 폭과 감소 폭을 각각 별도로 누적합(precomputation prefix sum)으로 계산하고, 질의에 따라 방향성을 고려하여 차이를 출력합니다.

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100005;
long long arr[MAX], incSum[MAX], decSum[MAX];
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%lld", &arr[i]);

    for (int i = 1; i < n; ++i) {
        if (arr[i] < arr[i+1]) incSum[i] = arr[i+1] - arr[i];
        else decSum[i] = arr[i] - arr[i+1];
    }

    for (int i = 1; i < n; ++i) incSum[i] += incSum[i-1];
    for (int i = n-1; i >= 1; --i) decSum[i] += decSum[i+1];

    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        if (l < r) printf("%lld\n", incSum[r-1] - incSum[l-1]);
        else printf("%lld\n", decSum[r] - decSum[l]);
    }
    return 0;
}

CodeTON Round 2 (Div. 1 + Div. 2) – B번

각 원소가 특정 범위 [a - m, a + m] 내에 있도록 전체 배열을 최소 개수의 구간으로 나누는 문제입니다. 현재 구간의 범위를 유지하면서 다음 원소를 포함할 수 없으면 새 구간을 시작하는 그리디한 방식으로 해결합니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m, val;
        scanf("%d%d", &n, &m);
        int leftBound = -1e9, rightBound = 1e9, cnt = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &val);
            leftBound = max(leftBound, val - m);
            rightBound = min(rightBound, val + m);
            if (leftBound > rightBound) {
                cnt++;
                leftBound = val - m;
                rightBound = val + m;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

Codeforces Round #813 (Div. 2) – B번

1부터 n까지의 수를 재배열하여 각 위치 i에서 i+1과 i-1의 위치에 있는 수가 교차하는 패턴을 만드는 문제입니다. n이 짝수인 경우와 홀수인 경우를 나누어 인접한 두 수를 서로 바꾸는 방식으로 처리합니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        if (n == 1) printf("1");
        else if (n == 2) printf("2 1");
        else if (n % 2 == 0) {
            for (int i = 1; i <= n; ++i) {
                if (i % 2) printf("%d ", i + 1);
                else printf("%d ", i - 1);
            }
        } else {
            printf("1 3 2 ");
            for (int i = 4; i <= n; ++i) {
                if (i % 2) printf("%d ", i + 1);
                else printf("%d ", i - 1);
            }
        }
        printf("\n");
    }
    return 0;
}

Codeforces Round #814 (Div. 2) – C번

쿼리마다 특정 원소가 처음으로 최댓값이 되는 위치와 그 시점 이후에 등장하는 횟수를 묻는 문제입니다. 각 원소에 대해 최댓값이 처음 등장하는 인덱스와 최댓값으로 유지되는 구간을 전처리하여 쿼리를 O(1)에 처리합니다.

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100005;
int arr[MAX], firstPos[MAX], endPos[MAX];
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(firstPos, 0, sizeof(firstPos));
        memset(endPos, 0, sizeof(endPos));
        int n, q;
        scanf("%d%d", &n, &q);
        int mx = 0, idx = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &arr[i]);
            if (arr[i] > mx) {
                firstPos[arr[i]] = i;
                endPos[mx] = i;
                mx = arr[i];
            }
        }
        while (q--) {
            int x, k;
            scanf("%d%d", &x, &k);
            if (arr[x] == mx) {
                if (firstPos[arr[x]] > 2) printf("%d\n", max(0, k - firstPos[arr[x]] + 2));
                else if (firstPos[arr[x]] == 1) printf("%d\n", max(0, k - firstPos[arr[x]] + 2) - 1);
                else printf("%d\n", max(0, k - firstPos[arr[x]] + 2));
            } else {
                if (firstPos[arr[x]] == 0) printf("0\n");
                else {
                    int limit = min(k + 2, endPos[arr[x]]);
                    if (firstPos[arr[x]] == 1) printf("%d\n", max(0, limit - firstPos[arr[x]] - 1));
                    else printf("%d\n", max(0, limit - firstPos[arr[x]]));
                }
            }
        }
    }
    return 0;
}