Codeforces Round #335 (Div. 1) C. Freelancer's Dreams

問題文

問題概要

制約 \[ a_1 x_1 + a_2x_2 + \cdots + a_n x_n \ge P \] \[ b_1 x_1 + b_2x_2 + \cdots + b_n x_n \ge Q \] \[ x_i \ge 0 \] のもとで、\(x_1+x_2+\cdots+x_n\)を最小化せよ。ただし\(x_i \in \mathbb{R} \)。

解法

蟻本にはこんなことが書いてある。

最大化問題 \[ \max\{c^Tx:Ax\le b, x\ge 0, x \in \mathbb{R}^n\} \] の双対問題は \[ \min\{b^Ty:A^Ty\ge c, y\ge 0, y \in \mathbb{R}^n\} \] となる。最適解が存在するなら両方の最適解は一致する。

どうして成り立つのかは置いといて、今回のLPの双対を取ってみると次の問題に変化する。

制約 \[ a_1 y_1 + b_1 y_2 \le 1 \] \[ a_2 y_1 + b_2 y_2 \le 1 \] \[ \vdots \] \[ a_n y_1 + b_n y_2 \le 1 \] のもとで、\(Py_1+Qy_2\)を最大化せよ。

2変数になった。\(P\)と\(Q\)が邪魔なので、適当に変換して\(y_1+y_2\)を最大化する問題にしておこう。

幾何的に考えると、領域中のマンハッタン距離の最大値を求める問題になる。
f:id:pekempey:20151210182641p:plain