東京海上日動プログラミングコンテスト2020 D - Knapsack Queries on a tree

D - Knapsack Queries on a tree

Editorialと同じ解法で解いたのでそっちを書きます。クエリごとに独立に解く方法もあって、そっちで解いた人のほうが多そうな印象です。

解法

$N$ が十分大きいという前提で解説をします。また扱う重みの最大値を $M = 100000$ 、最大深さの半分の値を $K=9$ とします。（Editorialに合わせています）

本質となる考え方は、以下の図のように深さ $18$ 以下の木を上側の $9$ と下側の $9$ に分けることです。

f:id:betrue12:20200614151748p:plain

上側をDPで前計算

まず上側については、頂点数が $511$ 個です。これらの頂点について、ナップサック問題ではお馴染みの以下のDPを行います。

$dp\lbrack i \rbrack\lbrack w\rbrack =$ 根から頂点 $i$ までのアイテムを使って、重さ $w$ 以下になるように選んだときの価値の最大値

遷移元は親なので $dp\lbrack \lfloor\frac{i}{2}\rfloor \rbrack$ から遷移します。頂点番号を1-indexedで取って、初期状態は $dp\lbrack 0 \rbrack$ としておくと都合が良いです。

また $w$ 以下としておくと後で便利で、そのためには初期状態を $dp\lbrack 0 \rbrack\lbrack 0\rbrack = dp\lbrack 0 \rbrack\lbrack 1\rbrack = \cdots = dp\lbrack 0 \rbrack\lbrack M\rbrack = 0$ とすれば良いです。

この時点でクエリ $(v, L)$ のうち $v \le 511$ であるものには答えられます。DPパートの計算量は $O(2^{K}M)$ です。

下側を全探索

クエリ $(v, L)$ のうち $v \gt 511$ であるものを処理します。このとき図の深さ $9$ まではDPで計算できているので、 $v$ から遡って深さ $10$ までの頂点のアイテムを集めます。これは $9$ 個以下なので、最大 $2^{9}$ 通りの選び方を全探索できます。

ある1つの選び方 $b$ について、その価値合計が $v_{b}$ 、重みが $w_{b}$ だったとします。そして頂点 $v$ から遡ってぶつかる深さ $9$ の頂点番号が $t$ だったとすると、この選び方で実現可能な最大価値は $dp\lbrack t \rbrack\lbrack L-w_{b}\rbrack + v_{b}$ であることが分かります。 $L \lt w_{b}$ のときは無視します。

これを全ての選び方について計算して最大値を取ったものが答えになります。

後半パートの計算量はクエリあたり $O(2^{K})$ にすることができます。各選び方について独立に $v_{b}, w_{b}$ を計算していると余分に $K$ が掛かってしまうので少し工夫しましょう。ビット全探索で実装したときに、選び方のビット列 $b$ に対応する値 $v_{b}, w_{b}$ を $O(1)$ で求めたいです。これは $b$ のMSB（最上位ビット）を管理しておくことで、 $b^{\prime} = b - msb(b)$ のときの結果 $v_{b^{\prime}}, w_{b^{\prime}}$ から差分更新できます。これで選び方1つあたりの計算量を $O(1)$ にできます。