Bintree（ふか杯 5th Contest [D]）

AtCoder

2021.06.122021.05.23

スポンサーリンク

目次

概要
解法
関連

概要

問題文 → ■
公式解説 → なさそう？
自分の提出 → ■

基礎的な問題。

解法

集合 $S \subset 1, 2, \dots, n$ に対して、頂点集合が $S$ と一致する二分木の個数を $dp [S]$ と書くことにします。これを適当なトポロジカル順序で計算していきます。

$S$ が空集合ならば、 $dp [S] = 1$ です。そうでないとき、 $S$ で二分木を作るときの根を $r$ 、左側の部分木の頂点集合を $L$ 、右側の部分木の頂点集合を $R$ として、以下のように計算できます。

$S = r ⨿ L ⨿ R$ となる $r, L, R$ に対して、 $| \sum_{v \in L} x_{v} - \sum_{v \in R} x_{v} | \in [a, b]$ であるとき、 $dp [S]$ に $dp [L] dp [R]$ を加算する。

これを計算するにあたり、各 $S$ に対して、 $L ⨿ R = S ∖ r$ となる $(L, R)$ を列挙する必要があります。集合をビット列により整数にエンコードすれば、この操作は bit 演算により、 $1$ 組の $(L, R)$ あたり $O (1)$ 時間で行えます。また、このような $(S, r, L, R)$ は全部で $O (N \cdot 3^{N})$ 通りあります。よって、時間計算量 $O (N \cdot 3^{N})$ で問題を解くことができます。

関連

タイトルとURLをコピーしました