AtCoder Regular Contest 098 F - Donation

お題箱より。

私も公式解説を見て通したので、公式解説の流れで書いていきます。

解法

時間を逆回しにしてみる

考察を進めていく順番ですが、まず「時間を逆回しにする」ことを考えてしまったほうが良いように思います。普通にゲームを進めると寄付をしていくごとに訪れることができる頂点が減っていきますが、頂点が減ることによるグラフの分断は扱いにくいことが多いです。そのため時間を逆回しにすることで頂点が増えるようにして扱いやすくします。

時間を逆回しにすると、 $B_{i}$ 円寄付するという行為は $B_{i}$ 円もらうという行為に変わります。また $A_{i}$ 円ないと頂点 $i$ に入れないという条件は、 $A_{i}$ 円ないとその頂点から出れないという条件に変わります。

では頂点 $i$ に最初に入るための条件はどうなるでしょうか。未訪問の頂点に入ったときには、 $B_{i}$ 円をすぐにもらってしまうのが良いです。それを貰った後に $A_{i}$ 円以上の所持金を持っている必要があるので、入るためには $A_{i} - B_{i}$ 円以上の所持金が必要であることが分かります。所持金が0未満になることはないので、 $C_{i} = \max(A_{i} - B_{i}, 0)$ としておきます。

つまり、 $C_{i}$ が大きい頂点ほど「入りにくい」頂点であるということが言えます。 $C_{i}$ が小さいところから回ってお金を集め、 $C_{i}$ が大きいところを攻略していくような方針になります。

また所持金は増えていく一方なので、一度入った頂点に後から入れなくなるということはありません。そのため「今どこの頂点にいて、どの頂点に寄付済みであるか」という複雑な状態ではなく、「今どの範囲の頂点を動き回ることが可能か（その範囲のお金は全て回収済み）」という視点で状態を管理することができます。この点で思考がシンプルになることが、時間を逆回しにすることの大きなメリットだと思います。

DPを考える

それでは実際に値を求めていきましょう。目的は元々の問題におけるスタート、つまり逆回しした時のゴール時の所持金を最小化することです。

ゲームの流れを追っていくにあたり、ゴール時の所持金はこれから求めるものなので、スタート時の所持金も当然分かりません。ただこれはあまり気にする必要がなくて、スタート時は所持金0円として、必要になったときに追加でお金を足すと考えても良いからです。各頂点でもらうお金の総額は固定なので、この「追加で足す金額の合計」を最小にするように動けばそれが最適になります。

イメージとしては $C_{i}$ が小さいところから回っていくので、まずは $C_{i}$ が小さい頂点だけで構成された連結成分を考え、その連結成分の全頂点のお金をもらうために追加のお金が最小でどれだけ必要かを求めます。その値を利用して、より大きな連結成分に対する答えを求めていくようなDPをします。

より具体的に説明します。以下のようなDPの値を考えます。

$dp\lbrack S \rbrack =$ ある頂点集合 $S$ に対して、 $S$ の全頂点のお金をもらうために必要な追加のお金の最小値

ここで $S$ としては連結であるもの、より正確には $S$ に属する頂点とそれらを結んだ辺だけからなる部分グラフを $G_{S}$ として、 $G_{S}$ が連結であるものだけを考えることにします。

$S$ の中で $C_{i}$ が一番大きい頂点を1つ選んで $x$ とします。そうすると $x$ は $S$ の中で最も「入りにくい」頂点であることが分かります。その頂点を境にして、 $S$ はさらにいくつかの頂点集合に分断されます。これらの頂点集合を $s_{0}, ..., s_{K}$ としておきます。

$S$ に含まれる頂点からもらうお金の合計を $T_{S} = \sum_{i\in S}B_{i}$ と表記することにします。 $s_{0}, ..., s_{K}$ に対して既に $dp\lbrack \cdot \rbrack$ の値が求まっているとします。このときに $S$ の回り方としては、以下のようなものが最適となります。

$s_{0}, ..., s_{K}$ から、スタート地点を含む集合を1つ選ぶ。これを $s_{k}$ とすると、まずは所持金 $T_{s_{k}} + dp\lbrack s_{k} \rbrack$ を持った状態で $s_{k}$ の全頂点を回り終える。
次に頂点 $x$ を訪れる。このとき所持金が足りなければ追加する。ここで追加する金額は $\max(0, C_{x} - (T_{s_{k}} + dp\lbrack s_{k} \rbrack))$ となる。
$s_{k}$ に含まれているもの以外の頂点を訪れ、お金を回収する。頂点 $x$ が最も入りにくい頂点なので、残りの頂点はお金を追加することなく回ることができる。

f:id:betrue12:20190610221926p:plain

ここまでで追加した合計金額を計算すると、 $dp\lbrack s_{k} \rbrack + \max(0, C_{x} - (T_{s_{k}} + dp\lbrack s_{k} \rbrack)) = \max(dp \lbrack s_{k} \rbrack, C_{x} - T_{s_{k}})$ となります。これを全通り試して一番小さいものを $dp\lbrack S \rbrack$ として採用すればよいです。

このDPは「ある集合 $S$ の中で $C_{i}$ が一番大きい頂点 $x$ を1つ選び、 $x$ で分断される部分集合たちのDPの値から計算する」という構成になっています。つまり小さい方から計算していくなら、 $C_{i}$ の値が小さい頂点から1つずつグラフに足していき、それによって出来る連結成分ごとにDPの値を計算していけばよいです。これはUnion-Findを用いて計算していくことができます。