CF1534H - 루트 탐색 최적화

트리에서 두 노드 a, b를 찾기 위한 최소 질의 횟수를 분석한다. 루트 r를 고정했을 때, 각 노드 u에 대해 서브트리 내에서 탐색하는 최악의 비용 cost[u]를 정의한다.

잎 노드의 경우 확인 비용은 1이다. 내부 노드에서는 자식들을 cost 기준 내림차순으로 정렬하여 탐색하며, i번째 자식을 탐색할 때의 비용은 cost[child_i] + i - 1이 된다. 전체 최악의 경우는 최대 두 서브트리를 탐색해야 하므로, 정렬된 자식들 중 상위 두 개의 조합을 고려한다.

루트를 바꿔가며 모든 경우를 계산하기 위해 재루팅 기법을 적용한다. 시간 복잡도는 O(n log n)이다.

const int MAXN = 1e5 + 5;
int n, subtreeCost[MAXN], answer[MAXN];
vector<int> adj[MAXN], orderedChildren[MAXN];

void computeCost(int u, int parent) {
    vector<int> childCosts;
    for (int v : adj[u]) {
        if (v == parent) continue;
        computeCost(v, u);
        childCosts.push_back(subtreeCost[v]);
    }
    sort(childCosts.rbegin(), childCosts.rend());
    subtreeCost[u] = 1;
    for (int i = 0; i < childCosts.size(); i++) {
        subtreeCost[u] = max(subtreeCost[u], childCosts[i] + i);
    }
}

void reroot(int u, int parent, int parentCost) {
    vector<pair<int,int>> allCosts;
    for (int v : adj[u]) {
        if (v == parent) allCosts.push_back({parentCost, v});
        else allCosts.push_back({subtreeCost[v], v});
    }
    sort(allCosts.rbegin(), allCosts.rend());
    
    // Calculate answer for current root
    answer[u] = 1;
    if (allCosts.size() >= 2) {
        answer[u] = max(answer[u], allCosts[0].first + allCosts[1].first + 1);
    }
    
    // Prepare prefix/suffix maximums for rerooting
    int m = allCosts.size();
    vector<int> prefix(m), suffix(m);
    for (int i = 0; i < m; i++) {
        prefix[i] = max(i ? prefix[i-1] : 0, allCosts[i].first + i);
    }
    for (int i = m-1; i >= 0; i--) {
        suffix[i] = max(i+1 < m ? suffix[i+1] : 0, allCosts[i].first + i);
    }
    
    for (int i = 0; i < m; i++) {
        int v = allCosts[i].second;
        if (v == parent) continue;
        int newParentCost = max(1, max(i ? prefix[i-1] : 0, i+1 < m ? suffix[i+1]-1 : 0));
        reroot(v, u, newParentCost);
    }
}

CF1510B - 버튼 잠금 최소화

비트마스크 상태들 사이의 포함 관계를 이용해 DAG를 구성한다. 상태 S에서 T로 이동 가능하려면 S & T == S이며, 이때 비용은 popcount(S)만큼 절감된다. 리셋 버튼을 고려해 가상의 루트에서 모든 상태로의 간선을 추가한다.

최소 경로 덮개 문제로 변환 후, 최소 비용 최대 유량으로 해결한다. 정점 분할을 통해 in(u) → out(v) 형태의 간선을 구성하고, 비용이 작은 간선부터 단계적으로 추가하여 효율적으로 계산한다.

struct MinCostFlow {
    struct Edge { int to, rev, cap, cost; };
    vector<vector<Edge>> g;
    vector<int> dist, pv, pe;
    
    void addEdge(int u, int v, int cap, int cost) {
        Edge a{v, (int)g[v].size(), cap, cost};
        Edge b{u, (int)g[u].size(), 0, -cost};
        g[u].push_back(a);
        g[v].push_back(b);
    }
    
    pair<int,int> maxFlow(int s, int t, int maxCost) {
        int flow = 0, cost = 0;
        while (true) {
            fill(dist.begin(), dist.end(), INF);
            dist[s] = 0;
            priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
            pq.push({0, s});
            while (!pq.empty()) {
                auto [d, u] = pq.top(); pq.pop();
                if (d != dist[u]) continue;
                for (int i = 0; i < g[u].size(); i++) {
                    auto &e = g[u][i];
                    if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                        dist[e.to] = dist[u] + e.cost;
                        pv[e.to] = u;
                        pe[e.to] = i;
                        pq.push({dist[e.to], e.to});
                    }
                }
            }
            if (dist[t] > maxCost) break;
            int add = INF;
            for (int v = t; v != s; v = pv[v]) {
                add = min(add, g[pv[v]][pe[v]].cap);
            }
            for (int v = t; v != s; v = pv[v]) {
                auto &e = g[pv[v]][pe[v]];
                e.cap -= add;
                g[v][e.rev].cap += add;
                cost += add * e.cost;
            }
            flow += add;
        }
        return {flow, cost};
    }
};

CF1336E - 인형 선택과 선형 기반

쉬운 버전: n개의 수를 선형 기반에 삽입하면, 기반의 크기를 k라 할 때 각 값은 2^(n-k)가지 방법으로 표현 가능하다. 기반을 고위/저위 비트로 분할하여 FWT(고속 월시-아다마르 변환)로 합성수를 계산한다.

어려운 버전: 기반의 크기 k가 클 때는 쌍대 기반(dual basis)을 활용한다. 기반 A에 대해 직교 기반 B를 구성하여, B의 원소들을 완전 탐색한다. 두 방법(O(2^k) vs O(2^(m-k))) 중 작은 쪽을 선택하여 균형 잡힌 복잡도 O(2^(m/2))를 달성한다.

const int MOD = 998244353;
const int INV2 = (MOD + 1) / 2;

void fwht(vector<int>& a, bool invert) {
    int n = a.size();
    for (int len = 1; len < n; len <<= 1) {
        for (int i = 0; i < n; i += len << 1) {
            for (int j = 0; j < len; j++) {
                int u = a[i+j], v = a[i+j+len];
                a[i+j] = (u + v) % MOD;
                a[i+j+len] = (u - v + MOD) % MOD;
            }
        }
    }
    if (invert) {
        for (int& x : a) x = 1LL * x * INV2 % MOD;
    }
}

// Dual basis construction
void buildDualBasis(vector<ll>& basis, int m) {
    vector<ll> dual(m);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            if (basis[j] >> i & 1) dual[i] |= 1LL << j;
        }
    }
    // Gaussian elimination on dual
    int rank = 0;
    for (int i = 0; i < m; i++) {
        if (!dual[i]) continue;
        for (int j = i+1; j < m; j++) {
            if (dual[j] >> i & 1) dual[j] ^= dual[i];
        }
        rank++;
    }
}

AT NOMURA2020F - 정렬 게임

배열 a의 인접 교환으로 정렬하는 비용을 분석한다. 역순 쌍 (i,j)에 대해 a_i와 a_j는 정확히 한 비트만 달라야 한다. 이는 a_i XOR a_j가 2의 거듭제곱이어야 함을 의미한다.

비트를 높은 자리부터 낮은 자리로 처리하는 DP를 설계한다. dp[n][m]을 길이 m, 값 범위 [0, 2^n)의 답으로 정의하고, 최상위 비트의 패턴에 따라 전이를 구성한다:

• 분할 없이 00...011...1 형태: (m+1) * dp[n-1][m]
• 분할 존재: sum_{i=1}^{m-1} i * 2^(m-i+1) * dp[n-1][i]

const int MAXN = 5005;
int dp[2][MAXN], pref[2][MAXN];

void solve(int n, int m) {
    dp[0][0] = 1;
    for (int len = 1; len <= m; len++) {
        dp[0][len] = 1;
        pref[0][len] = (2LL * pref[0][len-1] + len * dp[0][len]) % MOD;
    }
    
    for (int bits = 1; bits <= n; bits++) {
        int cur = bits & 1, prev = cur ^ 1;
        for (int len = 1; len <= m; len++) {
            // No split: choose split point among len+1 positions
            dp[cur][len] = 1LL * (len + 1) * dp[prev][len] % MOD;
            // With split: use prefix sum
            dp[cur][len] = (dp[cur][len] + pref[prev][len-1]) % MOD;
            
            pref[cur][len] = (2LL * pref[cur][len-1] + 1LL * len * dp[cur][len]) % MOD;
        }
    }
    cout << dp[n&1][m] << endl;
}

JOISC 2017E - 고장난 장치

고장난 비트는 0으로 고정되므로, 1을 사용하여 정보를 인코딩해야 한다. 두 비트쌍으로 삼진수를 표현하는 기본 아이디어에서 발전하여, 무작위 순열과 선형 기반을 활용한 강력한 방법을 설계한다.

랜덤한 60비트 수들로 선형 기반을 구성하고, 목표 값 x를 이 기반으로 표현한다. 각 기반 벡터에 대응하는 위치에 1을 기록하면, 브루노는 수신된 1들의 XOR로 원래 값을 복원한다.

// Anna's encoding
void encode(int n, ll target, int k, int* broken) {
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<ll> randomVals(n);
    for (int i = 0; i < n; i++) randomVals[i] = rng();
    
    // Build basis from non-broken positions
    vector<ll> basis(61);
    vector<int> basisPos(61, -1);
    vector<ll> basisMask(61);
    
    for (int i = 0; i < n; i++) {
        if (broken[i]) continue;
        ll x = randomVals[i], mask = 1LL << i;
        ll rep = 0;
        for (int b = 60; b >= 0; b--) {
            if (!(x >> b & 1)) continue;
            if (!basis[b]) {
                basis[b] = x;
                basisPos[b] = i;
                basisMask[b] = rep | (1LL << b);
                break;
            }
            x ^= basis[b];
            rep ^= basisMask[b];
        }
    }
    
    // Represent target in basis
    ll repr = 0;
    for (int b = 60; b >= 0; b--) {
        if (target >> b & 1) {
            target ^= basis[b];
            repr ^= basisMask[b];
        }
    }
    
    // Set bits according to representation
    for (int b = 0; b <= 60; b++) {
        if (repr >> b & 1) Set(basisPos[b], 1);
    }
}

SYSUCPC 2024 Final M - 순열 최적화

길이 n의 순열에서 인접한 세 원소 a[i-1], a[i], a[i+1]에 대해 lcm(a[i-1], a[i]) + lcm(a[i], a[i+1])의 합을 최대화한다. 환형 구조를 고려하면 답은 ceil(n/2) - 1이 된다.

짝수 위치에 [1, floor(n/2)]의 수를, 수 위치에 나머지 수를 배치한다. 짝수 위치는 오름차순으로 채우고, 홀수 위치는 양 끝에서 중앙으로 번갈아 가며 큰 수를 배치한다. 환형 조건을 만족하기 위해 첫 두 원소를 교환한다.

void construct(int n) {
    vector<int> res(n);
    int half = n / 2;
    
    // Fill even positions (0-indexed: 1, 3, 5, ...)
    for (int i = 1, val = 1; i < n; i += 2, val++) {
        res[i] = val;
    }
    
    // Fill odd positions with alternating pattern
    int left = half + 1, right = n;
    for (int i = 0; i < n; i += 4) {
        if (i < n) res[i] = right--;
        if (i + 2 < n) res[i+2] = left++;
    }
    for (int i = n-1; i >= 0; i -= 4) {
        if (i >= 0 && res[i] == 0) res[i] = right--;
        if (i - 2 >= 0 && res[i-2] == 0) res[i-2] = left++;
    }
    
    // Adjust for circular condition
    swap(res[0], res[1]);
    
    for (int x : res) cout << x << " ";
    cout << endl;
}