Code Festival Team Relay (Parallel) - D 数直線
雑でごめんなさい
問題
cf18-relay-open.contest.atcoder.jp
数直線上に N 個の点があり、i 番目の点の座標は x_i です。また、N 個の整数 w_i が与えられます。
次の条件を満たす点 p の座標を求めてください。条件を満たす点が複数ある場合は、最も座標が小さいものを求めてください。
条件: 「1≤i≤N を満たす整数 i に対する (p から点 i までの距離) × w_i の最大値が最小になる。」
解説
「1≤i≤N を満たす整数 i に対する (p から点 i までの距離) × w_i」 の最大値 を f と置くと，次のような線形計画問題っぽいものになる．
minimize f
subject to w_i × |p - x_i| ≦f for all i in {1..N}
f を二分探索で求めたい．f を適当な値に固定すると，それぞれの i について，次のような p の区間が定まる．
p ≦ x_i + f / w_i p ≧ x_i - f / w_i
全ての i について，共通の p の区間を求め，その区間が存在するかどうか確かめる二分探索が得られる．
以上で最適な f が見つかった．得た f から再び p の区間を計算して，最小値が答え．
