JOI2011 本戦 D - 歩くサンタクロース

• 問題
• AC

ひとまず一次元の問題として考える。つまり、数直線上のある地点$t$に降り立って、各点$x_1, x_2, ..., x_n$に行って帰る問題である。さらに$x_1 \le x_2 \le ...\le x_n$と仮定する。最後に訪れる点を$x_k$とする時、総距離は

$$\ 2|t-x_1| + .... + 2|t-x_{k-1}| + |t-x_{k}| + 2|t-x_{k+1}| + ... +2|t-x_n|$$

となる。絶対値関数の和は下に凸になり、区分する点の中央値で最小値を取ることを使えそうな気がする。しかし、係数が邪魔なので開いて並べる:

$$|t-x_1|, |t-x_1|, ... , |t-x_{k-1}|, |t-x_{k}|, |t-x_{k+1}|, ... , |t-x_n|, |t-x_n|$$

これら$2n-1$個の点の真ん中にある点$x_l$は（奇数個だから）一点に定まるので、上の式に$t=x_l$を代入すると最小値が求まる。具体的には、右側にある$n-1$個の$x_i$を足して左側にある$n-1$個の$x_i$を引けばよい。最後に訪れる点を$n$通り試せば答えがわかる。二次元の場合もまったく同じで、$x$方向と$y$方向について独立に求めてから和を取ればよい。

実装について。いろいろやり方はありそうだけど、ソートされた列に順序を保って挿入・削除する操作があって、さらに区間の和が高速に求まれば直接的にシミュレーションできるのでそれがもっとも簡単に見える。平衡二分木ならどちらも${O}(\log N)$でできる。

---

けっきょく真ん中になりえる点は1個か2個しかないので、それを試すだけでよいらしい。途中で気づきたかった。