yukicoder 1467 Selling Cars Θ((M + N) M + N log (N))

概要

No.1467 Selling Cars - yukicoder の非常に雑な解説

解法

を固定して最小費用流にエンコードすると以下のようになります。 頂点の数値は湧き出しの量です。

実際には適切に座標圧縮します。 これは series-parallel graph なので最小費用流が効率的に計算できます。

tokoharupage/advent2019.pdf at master · tokoharu/tokoharupage · GitHub

この時点で にはなりますが、log を落とすことができます。

区分線形凸関数に対して必要な操作をグラフに対する操作で雑に表現すると以下の 3 つです。

• の加算
• 負の方向に 1 ずらす
• 最小値から 正の方向に長さ の 軸に平行な線分を差し込む

最小値を取る が常に非正なので、関数を と に分けて、線分の列として管理します。 の折れ線の本数をポテンシャルにすると償却できて、線形です。