ARC049-B：高橋ノルム君
問題
https://beta.atcoder.jp/contests/arc049/tasks/arc049_b
N 点が与えられ、各座標は(x_i, y_i) である。また定数 c_i が与えられ、i 番目の点について、ある点(X, Y) に移動するためには c_i * max(|X-x_i|, |Y-y_i|)の時間がかかる。座標(X, Y)に集まるために必要な時間の最小値を求めよ。
考え方
「解が得られたと仮定するとどんな前提から導かれるか」という考え方が重要。よく出てくる。最小時間 t が得られたとすると、それぞれの座標 (x_i, y_i) と c_i から時間 t で移動できる座標が定まる。
c_i * max(|x_i - X|, |y_i - Y|) = y
X = x_i ± t/c_i
Y = y_i ± t/c_i
である。
すべての座標について1点に移動できるということは、任意の2点について共通部分をもつことと同値であるから、この条件を満たすように t を探索する。共通部分の判定は、x 軸、y 軸ごとに独立して考えてよい。
t は二分探索で求めることができるので解を求めることができた。
Submission #3508698 - AtCoder Regular Contest 049
ポイント
- 解を仮定したら、どんな前提から導かれるか
