ARMERIA

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

KUPC2020Spring F ボタンの木

AOJ プログラミング 競技プログラミング

お題箱より。

Aizu Online Judge Arena

解法

公式解説と逆になってしまいますが、与えられる a_{i} - b_{i} を改めて A_{i} と定義します。これが正である頂点は「過剰なので減らす必要がある」、負である頂点は「不足しているので増やす必要がある」ことになり、全ての A_{i} を 0 にするのが目標です。

適当に根を決め、木DPのように葉から操作していきます。実装方法は何通りかありそうですが、私の場合は以下のようにしました。

頂点 i を操作する時には、

  • 頂点 i の子孫である（頂点 i 自身を除く）頂点 k については、全て A_{k} = 0 となっている。
  • 頂点 i 自身については、 A_{i} \le 0 となっている。

という条件が満たされるまで操作をすることにします。具体的にどういう操作になるのか考えましょう。

まず頂点 i の直接の子である頂点 j は A_{j} \lt 0 となっている可能性があるので、まずこれを 0 にする必要があります。子の不足分の最大値と同じ回数だけ頂点 i を操作します。

このとき、不足分が最大である子以外には余分に値を送ってしまうので、それを「押し返す」必要があります。この押し返しにかかるコストは後で計算します。

f:id:betrue12:20200328131038p:plain

直接の子全てについて A_{j} = 0 となったら、その時点での A_{i} の値を確認します。これが正でなければこれで終わりですが、もし正であればさらにこれを親側に押し出す操作をします。このときやはり子には余分に値を送ってしまうので、「押し返し」が発生します。

押し返しのコストについて考えましょう。頂点 i の親から余分に値 1 が送られた時に、頂点 i より下の値を変えずにその 1 を親側に送り返すためにかかる合計操作回数を C_{i} とします。これは頂点 i を操作する 1 回と、頂点 i の全ての子 j に入ってしまう 1 をさらに押し返すための C_{j} の合計として計算できます。

これを根まで続けると、「必ず目的を達成できる」という制約から根 r についてちょうど A_{r} = 0 となり、それまでの全ての操作回数の合計として答えが求められます。

ACコード

Aizu Online Judge Arena