2021 Jan-Feb Problem Solving

글 쓰는 법을 까먹을 것 같으니, 몇 개 되지 않는 문제들을 줏어담아보자.

 

BOJ 20556. 둥둥섬 다리 재정비하기

20556번: 둥둥섬 다리 재정비하기

루트가 \(r\)로 고정되어 있다고 할 때, \(a\)개의 다리를 재정비해서 얻을 수 있는 최적의 결과는 가장 큰 \(a\)개 서브트리의 크기 합이라는 사실을 간단하게 알 수 있다. 따라서 "가장 큰 \(k\)개의 합"이 지원되는 자료구조에 서브트리들의 크기들을 전부 넣고 다니면 되고, 이건 segment tree나 fenwick tree로 된다. 루트가 바뀌는 경우에는 관리해야 하는 서브트리 크기들이 바뀌는데, 이 변화는 Persistent Segment Tree로 충분히 관리해줄 수 있다.

BOJ 18746. Exp

18746번: Exp

차수가 \(k\)로 작은 다항식 \(f\)가 있고, \(f^{n}\)의 계수들을 구하는 문제다.

편의상 \(f_{0} = 1\)이라고 두자. \(g = f^{n}\)이라고 두면 \(g' = nf^{n-1} = ng / f\)가 성립한다. \(g = \frac{fg'}{n}\)으로 변형하고 각 항의 계수를 비교하면

$$ g_{m} = \frac{1}{n}\sum_{i = 0}^{m} f_{i}(g')_{m - i} = \frac{1}{n} \sum_{i = 0}^{m} (m - i) f_{i}g_{m - i - 1} $$

정도로 생겨먹은 식이 나온다. (문제를 풀 때 이용한 식과 다르며, 계산 오류가 있을 수 있다) 그런데 $i \le k$ 정도만 의미 있으니 저 식을 이용하여 \(g\)의 \(n\)차항 계수를 \(\mathcal{O}(nk)\)시간에 계산할 수 있다.

 

BOJ 17440. 코포빵 토너먼트

17440번: 코포빵 토너먼트

그냥 할 일이 많은 문제다. Linearity of Expectation을 적용해서 각 노드에 대해 문제를 따로 풀면 되고, 답의 기댓값을 "답이 \(i\)이상일 확률의 합"으로 푸는 트릭도 유명하고, 확률문제는 이항계수 써서 식을 전개하고...

 

Csacademy round 72. Diamond Dogs

CS Academy

Distinct한 수들 \(a_{1}, \cdots, a_{n}\)이 일렬로 있을 때, 각 구간 \(L_{i}\)마다 \(\sum_{j \in L_{i}} 2^{a_j}\)의 순서를 비교하는 문제이다. 구간 \(L, L'\)을 비교하기 위해서는 각각 \(L - L', L' - L\)을 비교하면 되고, 수들이 distinct하다는 조건 때문에 두 집합의 max값끼리만 비교하면 된다. Sparse table로 미리 만들어두면 상수 시간에 두 집합의 비교가 가능하다. 전체 시간복잡도는 \(O(n\log n)\).

 

BOJ 17421. 빗물이 넘쳐흘러

17421번: 빗물이 넘쳐흘러

바닥면을 기준으로 "물 덩어리"들이 들어갈 컴포넌트들을 정점으로 하는 트리로 만들 수 있다. 자식 정점은 언제나 부모 정점보다 먼저 물이 차며, 두 개 이상의 자식을 가진 컴포넌트에 물이 차면 컴포넌트가 하나로 합쳐지는 식이다.

컴포넌트는 언제나 늘어날 때 하나씩 늘어나기 때문에, 컴포넌트가 줄어들면서 \(K\)개가 되는 순간을 고려할 필요는 없다. 이 사실을 파악하고 DFS를 돌리면 문제를 해결할 수 있다.