CF577B: Modulo Sum

주어진 수열에서 연속되지 않은 부분 수열을 선택하여 그 합이 특정 수 m으로 나누어 떨어지는지 판단하는 문제입니다.

해결의 핵심은 비둘기집 원리 (Pigeonhole Principle) 에 있습니다. 수열의 길이 n이 모듈로 값 m보다 크다면,PREFIX 합을 m으로 나눈 나머지는 총 m가지 경우しか 존재하지 않습니다. 따라서 n > m인 상황에서는 반드시 같은 나머지를 갖는 두 PREFIX 합이 존재하게 되며, 이 두 지점 사이의 부분 수열 합은 m의 배수가 됩니다. 이 경우 무조건 조건을 만족합니다.

만약 n ≤ m이라면, 동적 계획법을 적용하여 가능한 나머지 값들을 추적합니다. 각 숫자를 사용할지 말지를 결정하며 m으로 나눈 나머지가 0이 되는 조합이 존재하는지 확인합니다.

void solve() {
    int len, mod;
    std::cin >> len >> mod;
    std::vector<int> nums(len);
    for(int i = 0; i < len; ++i) {
        std::cin >> nums[i];
        nums[i] %= mod;
    }

    if(len > mod) {
        std::cout << "YES\n";
        return;
    }

    std::vector<std::vector<bool>> dp(len + 1, std::vector<bool>(mod, false));
    
    for(int i = 0; i < len; ++i) {
        dp[i][nums[i]] = true;
        for(int j = 0; j < mod; ++j) {
            if(i > 0 && dp[i-1][j]) {
                dp[i][j] = true;
                dp[i][(j + nums[i]) % mod] = true;
            }
        }
        if(dp[i][0]) {
            std::cout << "YES\n";
            return;
        }
    }
    std::cout << "NO\n";
}

CF25D: Roads not only in Berland

그래프 구조에서 불필요한 간선을 제거하고 새로운 간선을 추가하여 모든 노드가 연결되도록 만드는 문제입니다.

Union-Find 자료구조를 활용하여 그래프의 연결 상태를 관리합니다. 간선을 추가하다가 이미 연결된 노드 사이에 간선이 들어오면 이는 사이클을 형성하는 중복 간선으로 기록합니다. 이후 연결된 컴포넌트의 대표 노드들을 추출하고, ранее 기록된 중복 간선들을 이용하여 서로 다른 컴포넌트들을 연결합니다.

class UnionFind {
public:
    std::vector<int> parent;
    UnionFind(int n) {
        parent.resize(n + 1);
        for(int i = 0; i <= n; ++i) parent[i] = i;
    }
    int findRoot(int x) {
        if(parent[x] == x) return x;
        return parent[x] = findRoot(parent[x]);
    }
    bool join(int u, int v) {
        int rootU = findRoot(u);
        int rootV = findRoot(v);
        if(rootU != rootV) {
            parent[rootV] = rootU;
            return true;
        }
        return false;
    }
};

void solve() {
    int n;
    std::cin >> n;
    UnionFind uf(n);
    std::vector<std::pair<int, int>> redundantEdges;
    
    for(int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        if(!uf.join(u, v)) {
            redundantEdges.push_back({u, v});
        }
    }

    std::vector<int> components;
    for(int i = 1; i <= n; ++i) {
        if(uf.parent[i] == i) {
            components.push_back(i);
        }
    }

    std::cout << components.size() - 1 << "\n";
    for(size_t i = 0; i < components.size() - 1; ++i) {
        std::cout << redundantEdges[i].first << " " 
                  << redundantEdges[i].second << " " 
                  << components[i] << " " 
                  << components[i + 1] << "\n";
    }
}

CF1691D: Max GEQ Sum

부분 배열의 최대값이 해당 부분 배열의 합보다 크거나 같은 조건을 모든 부분 배열에 대해 만족하는지 검증하는 문제입니다.

각 요소 data[i]가 구간 내 최대값이 되는 범위를 모노토닉 스택 (Monotonic Stack) 을 사용하여 찾습니다.确定了 범위 내에서 PREFIX 합의 최대값과 최소값의 차이가 data[i]보다 큰지 세그먼트 트리를 통해 효율적으로 확인합니다. 조건을 위반하는 구간이 하나라도 존재하면 조건을 만족하지 않습니다.

class RangeTree {
    int size;
    std::vector<long long> treeMax;
    std::vector<long long> lazyVal;
    const long long INF = 4e18;

public:
    RangeTree(int n) : size(n) {
        treeMax.assign(4 * n, 0);
        lazyVal.assign(4 * n, 0);
    }

    void apply(int node, long long val) {
        treeMax[node] += val;
        lazyVal[node] += val;
    }

    void push(int node) {
        if(lazyVal[node] != 0) {
            apply(node * 2, lazyVal[node]);
            apply(node * 2 + 1, lazyVal[node]);
            lazyVal[node] = 0;
        }
    }

    void build(int node, int start, int end, const std::vector<long long>& arr) {
        if(start == end) {
            treeMax[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(node * 2, start, mid, arr);
        build(node * 2 + 1, mid + 1, end, arr);
        treeMax[node] = std::max(treeMax[node * 2], treeMax[node * 2 + 1]);
    }

    long long query(int node, int start, int end, int l, int r) {
        if(r < start || end < l) return -INF;
        if(l <= start && end <= r) return treeMax[node];
        push(node);
        int mid = (start + end) / 2;
        return std::max(query(node * 2, start, mid, l, r), 
                        query(node * 2 + 1, mid + 1, end, l, r));
    }
};

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> data(n + 1);
    std::vector<long long> prefix(n + 1, 0);
    
    for(int i = 1; i <= n; ++i) {
        std::cin >> data[i];
        prefix[i] = prefix[i - 1] + data[i];
    }

    std::vector<long long> maxVals(n + 2), minVals(n + 2);
    for(int i = 0; i <= n; ++i) {
        maxVals[i + 1] = prefix[i];
        minVals[i + 1] = -prefix[i];
    }

    RangeTree stMax(n + 1), stMin(n + 1);
    stMax.build(1, 1, n + 1, maxVals);
    stMin.build(1, 1, n + 1, minVals);
    
    std::vector<int> leftBound(n + 1), rightBound(n + 1);
    std::stack<int> stk;

    for(int i = 1; i <= n; ++i) {
        while(!stk.empty() && data[stk.top()] < data[i]) {
            rightBound[stk.top()] = i - 1;
            stk.pop();
        }
        leftBound[i] = stk.empty() ? 0 : stk.top();
        stk.push(i);
    }
    while(!stk.empty()) {
        rightBound[stk.top()] = n;
        stk.pop();
    }

    for(int i = 1; i <= n; ++i) {  
        long long maxPs = stMax.query(1, 1, n + 1, i + 1, rightBound[i] + 1);
        long long minPs = -stMin.query(1, 1, n + 1, leftBound[i] + 1, i);
        if(maxPs - minPs > data[i]) {
            std::cout << "No\n";
            return;
        }
    }
    std::cout << "Yes\n";
}