SRM 613 div1 easy TaroFriends

概要

太郎くんの友達がいる位置が1次元座標として与えられる。友達はそれぞれ1回、左か右にX動かなければならない。最長の友達の距離を最小化する。

考えたこと

とりあえず入力をソートして考える。最初任意の回数移動できるのかと思い距離Dを達成できるかを二分探索していくような解法を考えたがよく読むと一回しか移動しなさそう。ソートしておけば右に移動すべき人と左に移動すべき人が切り替わる位置は一個しかありえない。n<=50ならO(n^2)で全探索でも余裕。実装したら通った。

学び

左に移動するのに切り替わる位置がi番目とすると、左になりうる位置はmin(pos[0]+X, pos[i]-X)で右になりうる位置はmax(pos[i-1]+X, pos[n-1]-X)のいずれかなのでこれはO(1)で求まる。全体でO(n)でできる。