天下一プログラマーコンテスト2016予選A B - PackDrop
お題箱より。
解法
まずは問題をシンプルに
みたいなのがややこしいですね。まずは問題をシンプルに言い換えましょう。
ネットワーク全体は機器を頂点、その間を接続する経路を辺とするグラフとみなせます。より具体的には機器0を根とする根付き木になります。子機器を持たない 台の機器は葉であり、機器0から各葉 への到達率が と指定されています。
間に複数辺がある場合の到達率を考えましょう。仮に機器0と葉 の間に直列に辺が2本あり、それぞれPackDropが 個、 個含まれているとします。このときそれぞれの辺における到達率は と であり、機器0と葉 の間の到達率は問題文より掛け算になるので となります。これは指数法則によるものであり、辺の本数が3本以上になっても同様のことが成り立ちます。
つまり機器0から各葉 への到達率を にしたいのであれば、経路上の辺に含まれているPackDropの個数を全て足し算したものを にすることが必要十分となります。これで のようなものを考えずに問題を言い換えることができます。
- 頂点0を根とする頂点数 の根付き木が与えられる。
- それぞれの葉 について、頂点0からの「距離」 が指定されている。
- 上記距離を満たすように、各辺に非負整数値の「長さ」を割り当てる。(元々、PackDropの個数だったもの)
- 全ての辺の長さ合計を最小にしたい。その最小値はいくつか?
これで整数で考えられるグラフの問題になりました。
最小値の求め方を考える
実際にどのような割り当て方をすれば長さ合計を最小にできるのか考えてみます。
シンプルな例として、以下のグラフを考えてみましょう。
これを実現する長さの割り当て方として以下のようなものが考えられます。
これらは全て条件を満たしていますが、辺の長さ合計が違います。この例を見ると、できるだけ根に近いところに長さを大きく割り当てたほうが長さ合計を節約できそうです。
これはより複雑なグラフでも一般的に成り立ち、根に近いところに長さをできるだけ大きく割り当てるのが常に最適です。図の左側のように根以外の頂点から下に伸びる辺が全て正の重みを持っている場合は、図の右側のように上の辺に移すことで条件を満たしたまま長さ合計を減らせる(少なくとも増えはしない)からです。これはグラフが根付き木であることから成り立ちます。
そのため根に近いところから順番に辺の長さを決めていって、それぞれの長さは許される最大値まで割り当てることにしましょう。その辺の下にいる葉について、葉と根の距離が与えられた値 を超えてはいけないので、それを超えないギリギリまで取ります。つまり辺の長さは、
として決めることができます。
あとはこれを実際に計算していきます。各辺について、その辺の下にいる葉についての の最小値を求めておかないといけないので、これは下から順番に木DPのように求めておきましょう。それを予め求めた後で、辺の長さは上から順番に決めていきます。実装上は2回DFSをすることになります。