KMO

木への変換

$K$ 種類の記号を使う接頭語符号の符号長はクラフトの不等式 $\sum K^{-b_i}\leq1$ を満たし、逆も成り立つ。長さを昇順に処理し、未使用の位置を次の深さで $K$ 個に分岐させて必要な葉を置けば、対応する木を構成できる。

よって、各内部頂点の子が高々 $K$ 個の根付き木において、葉の重みと深さの積の総和を最小化する問題になる。重み $0$ の入力要素も実際の葉なので削除してはならない。

ハフマン併合

$N=1$ なら $0$ を出力する。それ以外では、各内部頂点がちょうど $K$ 個の子を持つ木の葉数は、$K-1$ で割ると $1$ 余る。重み $$ の仮想的な葉を

$$d=(K-1-(N-1)\bmod(K-1))\bmod(K-1)$$

個追加する。最適な木の子が一つだけの頂点を取り除き、子が $K$ 個未満の内部頂点を最深部にまとめて一つだけにすれば、足りない位置を埋める葉数は $d$ 個になる。非負の重みを持つ葉を浅く移しても費用は増えないため、最適値は変わらない。

浅い位置にある軽い葉と深い位置にある重い葉を交換しても費用は増えない。したがって、重みが小さい $K$ 個の葉が最深部で同じ親を持つ最適解が存在する。この $K$ 個を、重みが総和である一つの葉に縮約する。元の費用は縮約後の費用にその総和を加えたものとなる。これを繰り返すのが $K$ 分ハフマン法である。

仮想的な葉は実際に作る必要がない。最初だけ

$$r=2+(N-2)\bmod(K-1)$$

個の実際の頂点を併合し、その後は毎回 $K$ 個ずつ併合する。$K>N$ なら $r=N$ となる。$N-1$ が $$ の倍数なら最初も 個を併合する点に注意する。

最小ヒープで頂点を取り出し、新しい頂点をそれらの親として記録する。親の番号は子より大きいので、番号の逆順に深さを計算でき、再帰は不要である。元の入力順に葉の深さを出力する。

内部頂点は高々 $N-1$ 個で、それぞれ二つ以上の子を持つため、深さは $N-1$ 以下である。時間計算量は $O(N\log N)$、空間計算量は $O(N)$。併合重みは 以下である。すべての深さを とする解が存在するので、最適費用は 以下となる。符号付き ビット整数で十分であり、 を直接計算する必要はない。

サブタスク 1 は重みを降順に並べ、$0$ から $N-1$ までの非減少な深さ列を全列挙する。交換論法により、この順序の最適解が存在する。列は $\binom{2N-1}{N}$ 個あり、各列を で確認できる。サブタスク 2 は二分ハフマン法で毎回最小の二つを併合し、 で解ける。

不等式の検査では深さ $0$ の空き位置を一つとし、その深さの葉数を引いてから $K$ 倍する。葉数が空き位置を超えたら不正である。葉は合計 $N$ 個なので位置数を $N+1$ で打ち切ってよい。費用の検査では最適値を残り予算とし、積を計算する前に除算で予算超過を判定する。これにより誤った出力によるオーバーフローも防げる。

Solution written by GPT6