라운드 #77 - 20250521
A. 직렬 연결 (link)
문제 요약
각 정점에 두 가중치 \(a_i, b_i\)를 가진 트리가 주어진다. 단순 경로가 "좋은 경로"가 되려면 경로상의 \(b\) 합계와 경로상의 최소 \(a\) 값의 곱이 상수 \(V\) 이상이어야 한다. 모든 좋은 경로 중 \(\sum b\)의 최솟값을 구한다.
핵심 아이디어
정점 분할을 적용하면 조건은 \((B_u+B_v)\min(A_u,A_v) \ge V\)로 변환된다. \(A_u \le A_v\)라 가정하면, \(B_v \ge \left\lceil \frac{V}{A_u}\right\rceil - B_u\)를 만족하는 최소 \(B_v\)를 찾아야 하며, \(u\)와 \(v\)는 서로 다른 서브트리에서 와야 한다.
\(A\)를 내림차순으로 정렬하여 경로를 추가하고, \(B\)를 이산화하여 펜윅 트리를 구축한다. 각 서브트리별로 최솟값과 차솟값을 관리하여 서로 다른 색(서브트리) 조건을 처리한다.
시간 복잡도: \(\mathcal O(n\log^2 n)\)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
const ll INF=2e18;
struct NodeInfo {
ll firstVal, secondVal;
int firstColor, secondColor;
friend NodeInfo operator+(NodeInfo left, NodeInfo right) {
if(left.firstVal > right.firstVal) swap(left, right);
if(right.firstColor == left.firstColor) {
if(right.secondVal < left.secondVal)
left.secondVal = right.secondVal, left.secondColor = right.secondColor;
} else if(right.firstVal < left.secondVal) {
left.secondVal = right.firstVal, left.secondColor = right.firstColor;
}
return left;
}
} bit[MAXN], EMPTY={INF,INF,0,0};
int n, uniqueCnt, subtreeSize[MAXN], colorId[MAXN];
ll threshold, weightA[MAXN], weightB[MAXN], answer=INF;
vector<int> adj[MAXN];
bool processed[MAXN];
ll coordVals[MAXN];
void processCenter(int center) {
if(weightA[center]*weightB[center] >= threshold)
answer = min(answer, weightB[center]);
vector<array<ll,3>> candidates;
for(int nxt : adj[center]) if(!processed[nxt]) {
function<void(int,int,ll,ll)> collect = [&](int u, int par, ll minA, ll sumB) {
minA = min(minA, weightA[u]);
sumB += weightB[u];
candidates.push_back({minA, sumB, nxt});
subtreeSize[u] = 1;
for(int v : adj[u]) if(!processed[v] && v != par) {
collect(v, u, minA, sumB);
subtreeSize[u] += subtreeSize[v];
}
};
collect(nxt, center, weightA[center], weightB[center]);
}
uniqueCnt = 0;
sort(candidates.begin(), candidates.end(), greater<>());
for(auto &cand : candidates) coordVals[++uniqueCnt] = cand[1];
sort(coordVals+1, coordVals+uniqueCnt+1);
uniqueCnt = unique(coordVals+1, coordVals+uniqueCnt+1) - coordVals - 1;
fill(bit, bit+uniqueCnt+1, EMPTY);
auto update = [&](int idx, NodeInfo val) {
for(; idx; idx &= idx-1) bit[idx] = bit[idx] + val;
};
auto query = [&](int idx) {
NodeInfo res = EMPTY;
for(; idx <= uniqueCnt; idx += idx & -idx) res = res + bit[idx];
return res;
};
for(auto &cand : candidates) {
ll curMinA = cand[0], curSumB = cand[1], curColor = cand[2];
ll need = (threshold + curMinA - 1) / curMinA;
if(curSumB >= need) answer = min(answer, curSumB);
int pos = lower_bound(coordVals+1, coordVals+uniqueCnt+1,
need - curSumB + weightB[center]) - coordVals;
NodeInfo best = query(pos);
ll candidate = curSumB + (best.firstColor == curColor ? best.secondVal : best.firstVal)
- weightB[center];
answer = min(answer, candidate);
pos = lower_bound(coordVals+1, coordVals+uniqueCnt+1, curSumB) - coordVals;
update(pos, {curSumB, INF, (int)curColor, 0});
}
}
void decompose(int entry) {
processCenter(entry);
processed[entry] = true;
for(int nxt : adj[entry]) if(!processed[nxt]) {
int newRoot = 0;
function<void(int,int)> findCenter = [&](int u, int par) {
colorId[u] = subtreeSize[nxt] - subtreeSize[u];
for(int v : adj[u]) if(v != par && !processed[v]) {
findCenter(v, u);
colorId[u] = max(colorId[u], subtreeSize[v]);
}
if(!newRoot || colorId[u] < colorId[newRoot]) newRoot = u;
};
findCenter(nxt, entry);
decompose(newRoot);
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> threshold;
for(int i=1; i<=n; ++i) cin >> weightA[i] >> weightB[i];
for(int i=1, u, v; i<n; ++i) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
decompose(1);
cout << answer << "\n";
return 0;
}B. 음악 (desive)
문제 요약
길이 \(2^n\)의 배열 \(a_i \in [0, 2^n)\)이 주어진다. \(f(l,r)\)를 \(\max_x \mathrm{mex}(a_l \oplus x, a_{l+1} \oplus x, \ldots, a_r \oplus x)\)로 정의한다. 구간 리와 모든 부분구간의 \(f\)값 합 쿼리를 처리한다.
핵심 아이디어
트라이 트리에서 \(f\)의 특성을 분석한다. 각 서브트리가 가득 차면 \(f_p = f_{ls} + f_{rs}\), 아니면 \(f_p = \max(f_{ls}, f_{rs})\)이다.
\(f\)의 본질은 트라이에서 한 정점을 선택하여 루트까지의 경로를 제거하고 남은 가득 찬 서브트리 크기의 합이다. 스위핑과 분할 함수를 활용하여 각 리프의 가중치를 \(n\)개의 구간으로 표현하고, 세그먼트 트리로 구간 할당과 이력 합을 관리한다.
시간 복잡도: \(\mathcal O(n^2 2^n + nq)\)
C. 문자열 (string)
문제 요약
길이 \(n\)의 문자열 \(s\)가 주어진다. 각 쿼리 \((x,v)\)에 대해 \(k \in [1,v]\) 중 \(s[x,x+k-1]\)이 \(s[x+k,x+2k-1]\)보다 사전순으로 작은 \(k\)의 개수를 센다.
핵심 아이디어
조건은 \(\mathrm{rk}_x < \mathrm{rk}_{x+k}\)이고 두 부분문자열이 다를 것을 요구한다. 먼저 첫 조건만 만족하는 \(k\)의 수를 2D counting으로 계산하고, 제곱 문자열(반복되는 패턴)인 경우를 뺀다.
제곱 문자열은 \(\mathcal O(n\log n)\)개의 \(x\) 구간으로 표현 가능하다. 구간 내에서의 순위 비교는 구간 끝점 하나만 확인하면 되므로, 2D counting으로 효율적으로 처리한다.
시간 복잡도: \(\mathcal O(n\log^2 n)\)
라운드 #78 - 20250522
A. 그래프 (graph)
문제 요약
\(n\)개 정점 \(m\)개 간선의 무방향 그래프에서, 구간 \([l,r]\)의 각 정점의 이웃 정점 가중치를 \(+x\)하거나 정점 가중치 합을 쿼리한다.
핵심 아이디어
시퀀스 제곱근 분할을 적용한다. 완전한 블록과 불완전한 블록 간의 기여를 분리하여 처리한다. 정점의 차수에 따른 가중 분할을 사용하여 \(\sum \deg = 2m\) 특성을 활용한다.
시간 복잡도: \(\mathcal O((n+m+q)\sqrt{m})\)
B. 버킷 효과 (bucket)
문제 요약
\(m \times n\) 격자에서 각 행은 \(1\sim n\) 순열이어야 한다. 가중치는 각 의 최솟값의 곱이다. \(q\)개 위치의 값이 고정되어 있을 때, 모든 가능한 배치의 가중치 곱을 구한다.
핵심 아이디어
\(q=0\)인 경우, 열 최솟값 \(a_1\sim a_n\)을 선택하는 방식으로 DP한다. 고정된 위치가 있는 경우, 미확정 은 일반 DP로, 확정 열은 상태압축으로 처리한다.
시간 복잡도: \(\mathcal O(2^q q^2 n^2 + 2^q n^3)\)
C. 인간세상 다시 눈내리네 (snow)
문제 요약
\([1,m]\) 범위의 수열 \(a_1\sim a_n\)이 주어진다. 한 번의 연산에서 \(a_i\)를 \(c+1\)만큼 감소시키고, \(a[1,i-1]\) 또는 \(a[i+1,n]\)을 전부 \(-1\)한다. 모든 원소를 음수로 만드는 최소 연산 횟수를 구한다.
핵심 아이디어
최적해에서는 접두사 연산과 접미사 연산이 특정 위치에서 분리된다. 이분 탐색으로 답 \(k\)를 검증하고, DP를 통해 각 위치에서의 최대 처리 가능 범위를 계산한다. 펜윅 트리로 차분을 관리하며 효율적으로 전이한다.
시간 복잡도: \(\mathcal O((n+m)\log m)\)
라운드 #79 - 20250526
A. 트리 위 경로 (path)
문제 요약
\(m\)개 정점의 트리와 \(n\)개의 경로 가중치 추가 연산이 주어진다. 구간 \([l,r]\)의 연산을 각각 한 번 실행하거나, 트 변경 및 서브트리 합 쿼리를 처리한다.
핵심 아이디어
루트 변경은 서브트리 보수의 합으로 변환된다. 연산 구간 분할을 적용하여 완전한 블록은 미리 계산된 기여를, 불완전한 블록은 2D counting으로 처리한다.
시간 잡도: \(\mathcal O((n+m+q)\sqrt{n})\)
B. 세그먼트 트리와 구간 덧셈 (segt)
문제 요약
임의 분할(중점 분할 아님)로 구축된 \([1,n]\) 세그먼트 트리에서 구간 덧셈을 지원하고, \(\sum_u tg_u \cdot a_u + s_u \cdot b_u\)를 동적으로 유지한다.
핵심 아이디어
세그먼트 트리의 \(s_u\)는 실제 원소 합에서 조상의 lazy标记 합을 뺀 값으로 표현된다. zkw 세그먼트 트리와 유사한 방식으로 pushdown과 marking을 처리하고, 경량 분할로 효율적으로 관리한다.
시간 복잡도: \(\mathcal O(n + q\log^2 n)\)
C. 자릿수 DP (digit)
문제 요약
연산자 시퀀스 \(s_1\sim s_{n-1}\) (AND/OR/XOR)가 주어진다. 각 쿼리 \(m\)에 대해, \(c_1\sim c_n \in [0,2^k)\) 중 존재성 조건을 만족하는 쌍의 수를 \(2^{32}\)로 나눈 나머지를 구한다.
핵심 아이디어
표현 가능한 \(m\)의 집합은 항상 \([0,x]\) 형태의 접두사이다. AND/OR 연산만 고려하고, 역방향으로 탐색하여 각 비트의 독립성을 활용한다. 상태를 분할 수 형태로 압축하여 효율적으로 전이한다.
시간 복잡도: \(\mathcal O((n+q)k|S|)\), \(|S| \le 7.2 \times 10^4\)
라운드 #80 - 20250529
A. 부패 (corrupt)
문제 요약
\(0\sim 2^n-1\)을 두 개씩 짝지어 \((x,y)\)로 만든다. 모든 \(x \oplus y\)가 2의 거듭제곱이고, \(\sum[x \oplus y = 2^k] = a_k\)를 만족하는 매칭을 찾는다.
핵 아이디어
최상위 비트로 분할하여 재귀적으로 해를 구성한다. 모든 \(a_i\)가 짝수일 때 해가 존재하고, \(a_i \bmod 4 = 2\)인 경우를 특별 처리하여 \(2^{n-1}\) 매칭으로 조정한다. 작은 \(n\)에 대해서는 완전 탐색을 사용한다.
시간 잡도: \(\mathcal O(2^n)\)
B. 생명의 순환 (cycle)
문제 요약
\(n\)개 정점 \(m\)개 가중치 간선의 방향 그래프에서, \(1 \to n\) 길이 \(x\)의 경로 존재성을 나타내는 \(s_x\)의 주기를 구한다.
심 아이디어
충분히 큰 \(x\)에 대해 경로는 반드시 사이클을 포함한다. SCC 압축 후 각 경로의 주기를 \((p,r)\) 쌍으로 표현하고, 중국인의 나머지 정리를 활용하여 전체 주기를 계산한다. \(K=2520\)을 선택하여 효율적으로 병합한다.
시간 복잡도: \(\mathcal O((n+m+B^2)K)\)
C. 룰렛 도박 (bet)
문제 요약
길이 \(n\)의 환형 배열에서 \(i\)에서 \(1-p_i\) 확률로 멈추거나 \((i+d) \bmod n\)로 이동한다. 주기적 \(p\) 배열에 대한 단일 수정 쿼리를 처리하며, 기대 이동 횟수를 계산한다.
핵심 아이디어
\(d=1\)인 경우를 선형 함수 합성으로 해결한다. 유클리드 알고리즘을 확장하여 큰 \(n\)에 대해 세그먼트 트리 유사 구조를 구축하고, 영구적 세그먼트 트리로 수정을 관리한다.
시간 복잡도: \(\mathcal O((m+q)\log n)\)
라운드 #81 - 20250605
A. 볼리비아 (Bolivia)
문제 요약
중앙 열이 가장 높은 히스토그램이 주어진다. 단일 열만 남겼을 때 대칭이 되는 구간 \([l,r]\)의 개수를 구하고, 단점 수정 쿼리를 처리한다.
핵심 아이디어
대칭 위치의 높이 \(x < y\)인 경우, 유효한 구간은 \(r \le x\) 또는 \(l > y\)여야 한다. 이를 \([l,r]\)와 \([x+1,y]\)가 교차하지 않는 조건으로 변환하여 세그먼트 트리로 관리한다. 덮개되지 않은 최대 연속 구간 길이의 제곱 합을 유지한다.
시간 복잡도: \(\mathcal O((n+q)\log n)\)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
struct SegInfo {
int leftLen, rightLen;
ll sum;
bool fullCover;
friend SegInfo operator+(const SegInfo& L, const SegInfo& R) {
return {L.leftLen + (L.fullCover ? R.leftLen : 0),
R.rightLen + (R.fullCover ? L.rightLen : 0),
L.sum + R.sum + 1LL * L.rightLen * R.leftLen,
L.fullCover && R.fullCover};
}
};
const SegInfo ZERO = {0,0,0,false};
struct SegTree {
static const int MAXS = 1<<21 | 5;
SegInfo tree[MAXS];
int lazy[MAXS];
void pull(int p) {
tree[p] = (lazy[p<<1] ? ZERO : tree[p<<1])
+ (lazy[p<<1|1] ? ZERO : tree[p<<1|1]);
}
void build(int l=1, int r=maxHeight, int p=1) {
if(l==r) { tree[p]={1,1,1,true}; return; }
int mid=(l+r)>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
pull(p);
}
void update(int ul, int ur, int delta, int l=1, int r=maxHeight, int p=1) {
if(ul<=l && r<=ur) { lazy[p]+=delta; return; }
int mid=(l+r)>>1;
if(ul<=mid) update(ul,ur,delta,l,mid,p<<1);
if(mid<ur) update(ul,ur,delta,mid+1,r,p<<1|1);
pull(p);
}
ll query() { return lazy[1] ? 0 : tree[1].sum; }
} seg;
int n, queryCnt, heights[MAXN], maxHeight;
void modify(int pos, int delta) {
int left = heights[pos], right = heights[n-pos+1];
if(left > right) swap(left, right);
if(left < right) seg.update(left+1, right, delta);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> queryCnt;
for(int i=1; i<=n; ++i) cin >> heights[i];
maxHeight = heights[(n+1)/2];
seg.build();
for(int i=1; i<(n+1)/2; ++i) modify(i, 1);
cout << seg.query() << "\n";
while(queryCnt--) {
int pos, val; cin >> pos >> val;
modify(pos, -1);
heights[pos] = val;
modify(pos, 1);
cout << seg.query() << "\n";
}
return 0;
}B. 부분집합 합 (subset)
문제 요약
\(n\)개 원소 \((a_i, b_i)\)가 주어진다. \(f(S)\)는 \(S\)의 각 원소가 \(0, a_i, b_i\) 중 하나를 선택하여 합이 \(m\)으로 나누어 떨어지는 방법의 수이다. 두 구간에서 각각 하나씩 원소를 제거한 경우의 \(f\) 합을 쿼리한다.
핵심 아이디어
고양이 트리(세그먼트 트리의 변형)를 활용하여 중간점을 기준으로 양쪽 정보를 합성한다. CDQ 분할 정복으로 각 위치에서 하나를 제거한 경우의 다항식 정보를 효율적으로 계산한다.
시간 복잡도: \(\mathcal O((n\log^2 n + q)m)\)
C. 체인 커버 (chain)
문제 요약
\(n\)개 정점의 라벨링된 트리(루트 1)에서 \(k\)개의 루트-단말 경로를 선택하여 그 합집합의 크기가 \(m\)이 되는 경우의 수를 모든 \(m, k\)에 대해 계산한다.
핵심 아이디어
깊이 분포 \(c_x\) (깊이 \(x\)인 정점 수)를 기준으로 DP한다. \(c\) 배열은 감소해야 하며, 각 깊이에서의 부모-자식 연결 방식을 조합적으로 계산한다. 전치 원리를 적용하여 답 계산을 최적화한다.
시간 복잡도: \(\mathcal O(n^3)\)