見た目や diff 以上に手間取ってしまったので記録．
問題概要
$ N $ 個の点の座標 $ (x_i, y_i) $ と $ N $ 個の正整数定数 $ c_i $ が与えられる． $ i $ 番目の点が座標 $ (X,Y) $ に移動するには $ c_i * \max({|x_i-X|, |y_i-Y|}) $ 秒を要する．
全ての点が同時に動き始めて $ 1 $ つの点に集まるのにかかる最小の時間を求めよ．
制約
- $ 2 \leq N \leq 1000 $
- $ -10^{5} \leq x_i, y_i \leq 10^{5} $
- $ 1 \leq c_i \leq 1000 $
考察
集まる先の点を最適化して最小の時間を求めることは難しい．
というのも，$ c_i $ という係数があり単純な最適化は難しく単峰性もないため三分探索もできない．
というわけで，こういう時の伝家の宝刀であるところの答え決め打ち二分探索をする． そもそも問題自体が max-min 問題なので二分探索を疑った，という方針の人も多そう．
$ t $ 秒で全ての点が $ 1 $ つの点に集まれるかどうかを判定する問題を考えることになる． $ i $ 番目の点が動ける $ x $ 座標の区間を考えると， $ [x_i-t/c, x_i+t/c] $ となる． $ y $ 座標に関しても同様である． すなわち，各点の $ t $ 秒の可動域は正方形の領域になっている．
したがって，判定問題は「 $ N $ 個の正方形領域の全てに含まれる点が存在するか」と言い換えられる． これは， $ x $ 座標と $ y $ 座標を独立に考えて動ける区間の共通部分を取っていけば良い． この実装は区間 $ [l,r] $ を「$ l $ 以上 かつ $ r $ 以下」という制約に置き換えると簡単な最大最小の更新でできる．
以上により判定問題を $ O(N) $ で解くことができた． 二分探索とあわせて $ O(N log \, t_{max}) $ でこの問題を解けた．
余談
制約が $ 2 \leq N \leq 1000 $ なので，判定が $ O(N^{2}) $ の解法が存在するのではないかと考えた． よく考えると，正方形領域 $ A $ と $ B $ ， $ B $ と $ C $ ， $ C $ と $ A $ が共通部分があるときに $ A, B, C $ の共通部分は必ず存在する． このことは正方形領域が $ x,y $ 座標軸に平行な辺しか持たないことからわかる．
したがって，全ての正方形領域の組に対して共通部分が存在するかチェックすれば良い． これで $ O(N^{2}) $ で判定問題を解くことができた．
個人的ポイント
- 係数が付いていたりすると距離っぽい max-min 問題を解くのは難しい．
- 答えを決めうって二分探索をすることで大体うまくいく．
- Yakiniku Optimization Problem もこれだった気がする．
- 区間の共通部分を求める実装は，最大最小の更新で行える．
- 存在しない場合 最大 < 最小 になるので判定も楽．
