Codeforces Round #624 (Div. 3) E. Construct the Binary Tree

お題箱より。

Problem - E - Codeforces

問題概要

整数 $n, d$ が与えられる。頂点数 $n$ の木であって、根を頂点 $1$ としたときに二分木になっていて、全頂点の深さ（根までの距離）の合計が $d$ であるものを構築せよ。またはそのような二分木が存在しないことを判定せよ。

制約

マルチテストケースであり、ケース数 $t$ について $1 \le t \le 1000$
各ケースについて、 $2 \le n, d \le 5000$
全テストケースにおける $n$ の合計、 $d$ の合計はともに $5000$ 以下

解法

まずは $n$ 頂点の二分木であって、最も深さ合計が大きいものと小さいものを考えましょう。最も大きいものは根から一直線に伸びるグラフであり、最も小さいものは完全二分木（の、最下段の葉がいくつか欠けたもの）です。

方針としては、これらのうち一方のケースから始めて、1つずつ頂点を動かしてもう片方のケースに作り変えるような手順を実行し、その途中の丁度いい所で止める…という風に作ります。

どちらが先でも良いのですが、私は完全二分木のほうから作ったのでそちらで説明します。

まずは完全二分木を作り、その深さ合計を計算します。この時点で $d$ を超えてしまった場合は構築不可能です。

f:id:betrue12:20200229220029p:plain

セグメント木の添字みたいに計算していくと良いでしょう。図では0-indexedにしていますがお好みで。

ここから一番左のパスだけは残しつつ、深い葉から順番に一番左のパスを伸ばすように移していきます。このとき「この葉を一番左のパスの最も深い所に付けると、どれだけ深さ合計が増えるか？」を計算します。それだけ増えても合計が $d$ を超えないときは一番深いところに付けてOK、超えてしまうときはぴったり $d$ になるように途中に付けます。

f:id:betrue12:20200229220551p:plain