A - STring

스택을 이용한 시뮬레이션으로 해결합니다. 문자열을 순회하면서 'S'는 스택에 추가하고, 'T'가 등장할 때 스택 상단이 'S'이면 제거합니다. 최종적으로 남은 스택 크기가 정답입니다.

#include <iostream>
#include <stack>
using namespace std;

int main() {
    string str;
    cin >> str;
    stack<char> stk;
    
    for (char c : str) {
        if (!stk.empty() && stk.top() == 'S' && c == 'T') {
            stk.pop();
        } else {
            stk.push(c);
        }
    }
    
    cout << stk.size();
    return 0;
}

B - Minimum Sum

분할 정복과 세그먼트 트리를 이용해 최소값 위치를 찾습니다. 각 원소가 최소값인 구간의 개수를 계산하여 누적합니다. 구간 [l, r]에서 최소값 위치 p에 대한 점화식은 (p-l+1)*(r-p+1)*arr[p]입니다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

struct SegTree {
    vector<int> tree;
    int size;
    
    SegTree(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.resize(2*size, 0);
    }
    
    void build(vector<int>& arr, int n) {
        for (int i=0; i<n; i++) tree[size+i] = i;
        for (int i=size-1; i>0; i--) {
            int l = tree[2*i], r = tree[2*i+1];
            tree[i] = (arr[l] < arr[r]) ? l : r;
        }
    }
    
    int query(vector<int>& arr, int l, int r, int n) {
        l += size; r += size;
        int res = l;
        while (l <= r) {
            if (l%2 == 1) res = (arr[tree[l]] < arr[res]) ? tree[l] : res;
            if (r%2 == 0) res = (arr[tree[r]] < arr[res]) ? tree[r] : res;
            l = (l+1)/2;
            r = (r-1)/2;
        }
        return res;
    }
};

ll calc(vector<int>& arr, SegTree& st, int l, int r) {
    if (l > r) return 0;
    int p = st.query(arr, l, r, arr.size());
    ll left = calc(arr, st, l, p-1);
    ll right = calc(arr, st, p+1, r);
    return left + right + 1LL*arr[p]*(p-l+1)*(r-p+1);
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i=0; i<n; i++) cin >> arr[i];
    
    SegTree st(n);
    st.build(arr, n);
    cout << calc(arr, st, 0, n-1);
    return 0;
}

C - Tree Restoring

트리 지름의 특성을 활용합니다. 주어진 배열의 최대값이 지름 길이 d입니다. d의 홀짝성에 따라 중앙값의 개수 조건이 달라지며, 나머지 값들은 특정 범위 내에 분포해야 합니다.

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

int main() {
    int n;
    cin >> n;
    vector<int> cnt(n+1, 0);
    int max_val = 0;
    
    for (int i=0; i<n; i++) {
        int a;
        cin >> a;
        cnt[a]++;
        max_val = max(max_val, a);
    }
    
    if (max_val == 1) {
        cout << (n == 1 ? "Possible" : "Impossible");
        return 0;
    }
    
    int mid = (max_val+1)/2;
    for (int i=mid; i<=max_val; i++) {
        int req = (i == mid && max_val%2==0) ? 1 : 2;
        if (cnt[i] < req) {
            cout << "Impossible";
            return 0;
        }
    }
    
    for (int i=1; i<mid; i++) {
        if (cnt[i]) {
            cout << "Impossible";
            return 0;
        }
    }
    
    cout << "Possible";
    return 0;
}

D - ~K Perm Counting

포함배제 원리와 조합론을 적용합니다. 금지된 위치를 체인으로 모델링한 후, 각 체인에서 DP를 수행하여 충돌 없는 배치 수를 계산합니다. 최종 결과는 (-1)^i * f_i * (N-i)!의 합입니다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll MOD = 924844033;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> fact(n+1, 1), inv(n+1, 1);
    
    for (int i=1; i<=n; i++) {
        fact[i] = fact[i-1] * i % MOD;
        inv[i] = i==1 ? 1 : MOD - (MOD/i)*inv[MOD%i]%MOD;
    }
    
    vector<ll> dp(n+1, 0);
    dp[0] = 1;
    int chain_cnt = 0;
    
    for (int i=1; i<=k; i++) {
        for (int j=0; j<2; j++) {
            if (i+j*k > n) break;
            chain_cnt++;
            for (int s=n; s>=1; s--) {
                dp[s] = (dp[s] + dp[s-1]) % MOD;
            }
        }
    }
    
    ll ans = 0;
    for (int i=0; i<=n; i++) {
        ll term = fact[n-i] * dp[i] % MOD;
        if (i % 2) ans = (ans - term + MOD) % MOD;
        else ans = (ans + term) % MOD;
    }
    
    cout << ans;
    return 0;
}

E - Sugigma: The Showdown

두 트리 간 거리 비교를 통한 게임 이론 문제입니다. 빨간 트리에서 파란 트리로의 거리 비율을 분석해 도달 가능한 최대 거리를 계산합니다. 안전한 정점이 존재하면 무한히 게임을 지속할 수 있습니다.

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

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    vector<vector<int>> red(n+1), blue(n+1);
    
    for (int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        red[u].push_back(v);
        red[v].push_back(u);
    }
    
    for (int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        blue[u].push_back(v);
        blue[v].push_back(u);
    }
    
    vector<int> blue_dist(n+1, -1);
    queue<int> q;
    q.push(y);
    blue_dist[y] = 0;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : blue[u]) {
            if (blue_dist[v] == -1) {
                blue_dist[v] = blue_dist[u] + 1;
                q.push(v);
            }
        }
    }
    
    int max_dist = 0;
    vector<int> red_dist(n+1, -1);
    q.push(x);
    red_dist[x] = 0;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (red_dist[u] < blue_dist[u]) {
            max_dist = max(max_dist, blue_dist[u]);
            for (int v : red[u]) {
                if (red_dist[v] == -1) {
                    red_dist[v] = red_dist[u] + 1;
                    q.push(v);
                }
            }
        }
    }
    
    cout << (max_dist >= n ? -1 : 2*max_dist);
    return 0;
}

F - Many Easy Problems

정점별 기여도를 조합 공식으로 변환합니다. NTT를 이용해 다항식 곱셈을 최적화합니다. 각 크기 y에 대한 답은 N * C(N,y) - Σ(a_x * C(x,y)) 형태로 표현됩니다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll MOD = 924844033, root = 5;

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i=1, j=0; i<n; i++) {
        int bit = n/2;
        while (j & bit) j ^= bit, bit /= 2;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    
    for (int len=2; len<=n; len*=2) {
        ll wlen = 1, angle = (MOD-1)/len;
        if (inv) angle = MOD-1-angle;
        wlen = pow(root, angle);
        
        for (int i=0; i<n; i+=len) {
            ll w = 1;
            for (int j=0; j<len/2; j++) {
                ll u = a[i+j], v = a[i+j+len/2]*w % MOD;
                a[i+j] = (u+v) % MOD;
                a[i+j+len/2] = (u-v+MOD) % MOD;
                w = w*wlen % MOD;
            }
        }
    }
    
    if (inv) {
        ll inv_n = pow(n, MOD-2);
        for (ll& x : a) x = x*inv_n % MOD;
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n+1);
    vector<ll> fact(n+1,1), inv_fact(n+1,1);
    
    for (int i=1; i<=n; i++) {
        fact[i] = fact[i-1]*i % MOD;
        inv_fact[i] = pow(fact[i], MOD-2);
    }
    
    for (int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    vector<ll> poly(n+1,0);
    function<int(int,int)> dfs = [&](int u, int p) {
        int sz = 1;
        for (int v : graph[u]) {
            if (v == p) continue;
            int ch_sz = dfs(v, u);
            poly[ch_sz]++;
            poly[n-ch_sz]++;
            sz += ch_sz;
        }
        return sz;
    };
    
    dfs(1,0);
    poly[0] = 0;
    
    vector<ll> A(n+1), B(n+1);
    for (int i=0; i<=n; i++) {
        A[i] = poly[i] * fact[i] % MOD;
        B[i] = inv_fact[n-i];
    }
    
    ntt(A, false);
    ntt(B, false);
    for (int i=0; i<A.size(); i++) A[i] = A[i]*B[i] % MOD;
    ntt(A, true);
    
    for (int k=1; k<=n; k++) {
        ll term1 = n * fact[n] % MOD * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
        ll term2 = A[n+k] * inv_fact[k] % MOD;
        cout << (term1 - term2 + MOD) % MOD << '\n';
    }
    return 0;
}