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를 돌리면 문제를 해결할 수 있다.