A - Range Product

주어진 구간 [A, B]에 속한 모든 정수의 곱의 부호를 판별하는 문제입니다. 구간에 0이 포함되면 곱은 0이 됩니다. 모든 수가 양수라면 결과는 양수입니다. 모든 수가 음수라면 음수의 개수(B - A + 1)가 짝수일 때 양수, 홀수일 때 음수가 됩니다.

#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    long long start_val, end_val;
    std::cin >> start_val >> end_val;

    if (start_val <= 0 && end_val >= 0) {
        std::cout << "Zero\n";
    } else if (start_val > 0) {
        std::cout << "Positive\n";
    } else {
        long long count = end_val - start_val + 1;
        if (count % 2 == 0) std::cout << "Positive\n";
        else std::cout << "Negative\n";
    }
    return 0;
}

B - Box and Ball

N개의 상자가 있고, 초기에 1번 상자에만 빨간색 공이 들어있습니다. M번의 연산을 통해 한 상자의 공을 다른 상자로 이동시킬 때, 최종적으로 빨간색 공이 들어있을 가능성이 있는 상자의 수를 구해야 합니다. 각 상자의 공의 개수와 빨간색 공의 존재 가능성(0: 없음, 1: 확실함, 2: 가능성 있음)을 추적하여 시뮬레이션하면 됩니다.

#include <iostream>
#include <vector>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n, m;
    std::cin >> n >> m;

    std::vector<int> ball_count(n + 1, 1);
    std::vector<int> red_state(n + 1, 0);
    red_state[1] = 1;

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        if (ball_count[u] == 1) {
            if (red_state[u] == 1) red_state[v] = 1;
            else if (red_state[u] == 2) red_state[v] = 2;
            red_state[u] = 0;
        } else {
            if (red_state[u] != 0) {
                red_state[u] = 2;
                red_state[v] = 2;
            }
        }
        ball_count[u]--;
        ball_count[v]++;
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (red_state[i] > 0) ans++;
    }
    std::cout << ans << "\n";
    return 0;
}

C - Knot Puzzle

N개의 밧줄을 인접한 것끼리 묶어나가는 과정입니다. 이를 역순으로 사고하면, 길이의 합이 L 이상이 되는 인접한 두 밧줄을 먼저 찾고, 나머지를 이 둘을 기준으로 좌우로 차례대로 묶어 나가는 그리디 접근이 가능합니다. 합이 L 이상인 인접한 쌍이 하나도 없다면 불가능한 경우입니다.

#include <iostream>
#include <vector>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n, l;
    std::cin >> n >> l;
    std::vector<int> len(n);
    for (int i = 0; i < n; ++i) std::cin >> len[i];

    int pivot = -1;
    for (int i = 0; i < n - 1; ++i) {
        if (len[i] + len[i + 1] >= l) {
            pivot = i;
            break;
        }
    }

    if (pivot == -1) {
        std::cout << "Impossible\n";
        return 0;
    }

    std::cout << "Possible\n";
    for (int i = 0; i < pivot; ++i) {
        std::cout << i + 1 << "\n";
    }
    for (int i = n - 2; i >= pivot; --i) {
        std::cout << i + 1 << "\n";
    }
    return 0;
}

D - Stamp Rally

간선이 순차적으로 추가되는 그래프에서, 특정 두 정점이 속한 연결 요소의 크기가 Z 이상이 되는 최초의 간선 번호를 찾는 쿼리들을 처리해야 합니다. 이는 전체 이분 탐색(Parallel Binary Search)과 롤백(Undo)이 가능한 서로소 집합(DSU) 자료구조를 결합하여 효율적으로 해결할 수 있습니다.

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

struct DSU {
    std::vector<int> parent, sz;
    std::vector<std::pair<int, int>> history;

    DSU(int n) : parent(n + 1, 0), sz(n + 1, 1) {}

    int find(int u) {
        while (parent[u]) u = parent[u];
        return u;
    }

    void unite(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return;
        if (sz[u] < sz[v]) std::swap(u, v);
        parent[v] = u;
        sz[u] += sz[v];
        history.push_back({v, sz[v]});
    }

    int get_size(int u) { return sz[find(u)]; }

    void rollback(int target_size) {
        while (history.size() > target_size) {
            auto [v, old_sz] = history.back();
            history.pop_back();
            sz[parent[v]] -= old_sz;
            parent[v] = 0;
        }
    }
};

int n, m, q;
std::vector<int> edge_u, edge_v;
std::vector<int> qx, qy, qz, qid, ans;

void solve(int l, int r, int ql, int qr, DSU& dsu) {
    if (ql > qr) {
        for (int i = l; i <= r; ++i) dsu.unite(edge_u[i], edge_v[i]);
        return;
    }
    if (l == r) {
        for (int i = ql; i <= qr; ++i) ans[qid[i]] = l;
        dsu.unite(edge_u[l], edge_v[l]);
        return;
    }
    int mid = (l + r) / 2;
    int saved_state = dsu.history.size();
    for (int i = l; i <= mid; ++i) dsu.unite(edge_u[i], edge_v[i]);

    std::vector<int> left_q, right_q;
    for (int i = ql; i <= qr; ++i) {
        int id = qid[i];
        int u = dsu.find(qx[id]), v = dsu.find(qy[id]);
        int total_sz = (u == v) ? dsu.get_size(u) : dsu.get_size(u) + dsu.get_size(v);
        if (total_sz >= qz[id]) left_q.push_back(id);
        else right_q.push_back(id);
    }

    dsu.rollback(saved_state);

    int mid_q = ql + left_q.size() - 1;
    for (int i = 0; i < left_q.size(); ++i) qid[ql + i] = left_q[i];
    for (int i = 0; i < right_q.size(); ++i) qid[mid_q + 1 + i] = right_q[i];

    solve(l, mid, ql, mid_q, dsu);
    solve(mid + 1, r, mid_q + 1, qr, dsu);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cin >> n >> m;
    edge_u.resize(m + 1); edge_v.resize(m + 1);
    for (int i = 1; i <= m; ++i) std::cin >> edge_u[i] >> edge_v[i];
    std::cin >> q;
    qx.resize(q + 1); qy.resize(q + 1); qz.resize(q + 1); qid.resize(q + 1); ans.resize(q + 1);
    for (int i = 1; i <= q; ++i) {
        std::cin >> qx[i] >> qy[i] >> qz[i];
        qid[i] = i;
    }
    DSU dsu(n);
    solve(1, m, 1, q, dsu);
    for (int i = 1; i <= q; ++i) std::cout << ans[i] << "\n";
    return 0;
}

E - Candy Piles

두 플레이어가 번갈아 가며 가장 큰 사탕 더미를 제거하거나, 모든 더미에서 사탕을 하나씩 가져가는 게임입니다. 이는 2차원 격자에서의 게임 이론 문제로 모델링할 수 있으며, P-포지션(필패)과 N-포지션(필승)의 패턴을 분석하면 됩니다. 정렬된 더미의 크기를 기준으로 연속된 N-포지션을 큐로 관리하여 상태 전이를 최적화할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    std::sort(a.begin(), a.end());

    std::deque<int> n_states;
    int last_color = 0;

    for (int i = 1; i < n; ++i) {
        if (a[i] == a[i - 1]) {
            last_color ^= 1;
        } else {
            int c = ~(a[i] - a[i - 1]) & 1;
            if (c != last_color) {
                n_states.push_back(a[i - 1] - last_color + i);
            }
            last_color = 0;
        }
        while (!n_states.empty() && n_states.front() <= i) {
            n_states.pop_front();
        }
    }

    int parity = n_states.size() % 2;
    bool first_wins = last_color ^ (a[n - 1] % 2) ^ parity;
    std::cout << (first_wins ? "First" : "Second") << "\n";
    return 0;
}

F - Leftmost Ball

N가지 색의 공이 각각 K개씩 있을 때, 각 색의 가장 왼쪽에 있는 공을 흰색(0번 색)으로 칠하는 경우의 수를 구합니다. 이는 특정 조건을 만족하는 수열의 개수를 세는 문제이며, 위상 정렬 개수를 구하는 동적 계획법(DP)으로 변환할 수 있습니다. DP 상태는 남은 흰색 공의 수와 색상 그룹의 수로 정의하며, 조합(Combinatorics)을 사용하여 전이합니다.

#include <iostream>
#include <vector>

const int MOD = 1000000007;

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

long long modInverse(long long n) {
    return power(n, MOD - 2);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n, k;
    std::cin >> n >> k;

    if (n == 1 || k == 1) {
        std::cout << 1 << "\n";
        return 0;
    }

    int max_val = n * k + 5;
    std::vector<long long> fact(max_val), inv_fact(max_val);
    fact[0] = 1;
    for (int i = 1; i < max_val; ++i) fact[i] = (fact[i - 1] * i) % MOD;
    inv_fact[max_val - 1] = modInverse(fact[max_val - 1]);
    for (int i = max_val - 2; i >= 0; --i) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }

    auto nCr = [&](int n, int r) -> long long {
        if (r < 0 || r > n) return 0;
        return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
    };

    std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(n + 1, 0));
    dp[0][0] = 1;
    for (int j = 1; j <= n; ++j) {
        dp[0][j] = (dp[0][j - 1] * nCr(j * (k - 1) - 1, k - 2)) % MOD;
    }

    for (int i = 1; i <= n; ++i) {
        dp[i][i] = dp[i - 1][i];
        for (int j = i + 1; j <= n; ++j) {
            long long ways = (dp[i][j - 1] * nCr(i + j * (k - 1) - 1, k - 2)) % MOD;
            dp[i][j] = (dp[i - 1][j] + ways) % MOD;
        }
    }

    long long ans = (dp[n][n] * fact[n]) % MOD;
    std::cout << ans << "\n";
    return 0;
}