ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

CPSCO2019 Session2 E - Mogu Mogu Gummi

お題箱より。

E - Mogu Mogu Gummi

解法

木DPを考えてみる

「連結成分の個数」よりも「切った辺の本数」のほうが遷移を組みやすいので、そっちで考えます。連結成分の個数は切った辺の本数に1を足したものです。

シンプルなグラフを例にして考えてみましょう。頂点0が根です。

f:id:betrue12:20190719005533p:plain

このグラフにおいて、 H_{2} H_{3} の辺を切ろうとして頂点2や3を操作するときには必ず  H_{1} の辺がダメージを受けます。その途中で  H_{1} の辺のほうが切れてしまった場合、もうそれ以上頂点2や3は操作できません。

上側の辺が切れてしまうともう下側を操作できない…と考えると、例えば頂点1に注目したときには「なるべく上の辺  H_{1} に与えるダメージを少なくしつつ、下側の辺  H_{2}, H_{3} を多く切りたい」という気持ちになります。これを元に以下のようなDPを考えます。

  •  dp\lbrack i \rbrack\lbrack j \rbrack = 頂点  i 以下の部分木で辺を  j 本切るために必要な、頂点  i から根までの辺に与える最小のダメージ

ここでは最小のダメージしか覚えておく必要はありません。ダメージが小さいぶんには、頂点  i 自身を操作することでダメージを追加で与えることができるからです。

例えば上の図において頂点1についてこのDPを考えると、

  •  dp\lbrack 1 \rbrack\lbrack 0 \rbrack = 0
  •  dp\lbrack 1 \rbrack\lbrack 1 \rbrack = \min(H_{2}, H_{3})
  •  dp\lbrack 1 \rbrack\lbrack 2 \rbrack = H_{2} + H_{3}

こんな感じです。

遷移を詰める

より一般的にDPの遷移を詰めていきます。

頂点  i についてのDPの値を求めるときには、まず頂点  i を頂点数1の木とみなし  dp\lbrack i \rbrack\lbrack 0 \rbrack = 0 とします。その他の  j については  dp\lbrack i \rbrack\lbrack j \rbrack = \infty としておきます。 \infty はその部分木で辺を  j 本切るのが不可能であることを示します。ここに1つずつ子の情報をマージしていきます。

親頂点を  i 、子頂点を  c とします。親側で既に切っている辺の本数  j_{i} と子側で既に切っている辺の本数  j_{c} の組み合わせそれぞれについて遷移を試します。

f:id:betrue12:20190719021136p:plain

このとき遷移のパターンとしては、

  •  dp\lbrack c \rbrack\lbrack j_{c} \rbrack \gt H_{c} のとき:これは  c 以下で操作をしている途中で  H_{c} の辺が切れてしまうことを意味する。そのため、そもそもこの遷移は不可能。
  •  dp\lbrack c \rbrack\lbrack j_{c} \rbrack \le H_{c} のとき、以下の2つがあり得る:
    •  H_{c} の辺を切らない:切った辺の本数が  j_{i} + j_{c} になり、 H_{i} には合計で  dp\lbrack i \rbrack\lbrack j_{i} \rbrack + dp\lbrack c \rbrack\lbrack j_{c} \rbrack のダメージが入る。
    •  H_{c} の辺を切る:切った辺の本数が  j_{i} + j_{c} + 1 になり、 H_{i} には合計で  dp\lbrack i \rbrack\lbrack j_{i} \rbrack + H_{c} のダメージが入る。

このようにすればマージ後のDPテーブルを計算できます。同じ  (i, j) に対して複数の遷移が来た場合にはダメージが少ない方を採用すれば良いです。

このDPを根0まで計算します。そうすると最終結果である  dp\lbrack 0 \rbrack\lbrack j \rbrack は、「 dp\lbrack 0 \rbrack\lbrack j \rbrack \ne \infty のときは、木全体で辺を  j 本切ることが可能である」と捉えることができます。これで答えを求めることができます。

「二乗の木DP」の話

今回組んだDPは、実装を適切にしてあげると全体計算量  O(N^{2}) で動作します。通称「二乗の木DP」と呼ばれているものです。

こちらの記事で計算量解析がされていますが、まずは知識として覚えてしまって良いと思います。適用できる問題の特徴として、以下の点が挙げられます。

  • 木DPのテーブルに、どの頂点まで見たかだけでなく「頂点や辺の個数」に関するようなインデックスがある。
  • 遷移において子を1つずつマージする際に、さきほどの「頂点や辺の個数」を親子それぞれについて回す2重ループがある。
  • 実装においてこの2重ループを毎回  N N-1 まで回すのではなく、その部分木のサイズまでしかループしないようにすることができる。

つまりDPの状態を「頂点  i 以下の部分木で、○○な頂点が  j 個であるときの△△」や「頂点  i 以下の部分木で、○○な辺が  j 本であるときの△△」のように取れる時に適用しやすいです。このようなDPが組めて、かつ制約上  O(N^{2}) が許容されそうであれば、二乗の木DPを疑ってみましょう。

ACコード

Submission #6435777 - CPSCO2019 Session2

変数名はある程度は上記の解説に合わせています。再帰関数の中でコメントを付けているところが二乗の木DPのキモで、どの問題でも割と似たような実装になるので慣れておくと良いと思います。

細かい実装上の注意として、子をマージするときに  dp\lbrack i \rbrack から  dp\lbrack i \rbrack を更新するような格好になるので、遷移元と遷移先が混ざらないようにしないといけません。例えばナップサックDPを一次元配列でやろうとする時と似たような注意が必要です。

単純なのは上記コードのように別途一時配列を用意して遷移先をそっちに書き、後でコピーする方法。または今回の遷移であれば  j_{i}, j_{c} についてループの方向を逆順にすることで一時配列なしで上手くできたりしますが、慣れないうちは混乱しにくい前者がオススメです。