読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

Codeforces 三分探索

問題文

codeforces.com

問題概要

制約 \[ 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

最大値の候補が領域の端なのは間違いない。領域の端で点を動かしてみると、マンハッタン距離が凸っぽく変化することが確認できる。 そのため最大値を求めるのに三分探索が使える。
f:id:pekempey:20151210182900p:plain


自分の提出コード。誤差死を恐れてlong doubleを使った。

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

ひとこと

終了5分前にコードが完成して無事AC。ギリギリ通せてよかった。