歩くサンタクロース 解説
この記事は 解説 Advent Calendar 2017 - Adventar の8日目の記事です。
https://adventar.org/calendars/2398
問題概要
格子上にN個の地点があり、その全てを1回ずつ訪れなければいけない。
訪れるのにかかる時間は現在地と目的地のマンハッタン距離である。
開始地点は格子点であればどこでもよい。
各地点を訪れる時は開始地点から往復しなければならない。
ただし最後に訪れる地点のみは片道でよい。
開始地点を上手く決めて各地点に訪れる移動距離の和を最小化したい。
N <= 10^5
各地点のx, y <= 10^9
解説
(X, Y)を開始地点としたときの移動距離の和をS1、(X+1, Y)を開始地点としたときの移動距離の和をS2とすると、それぞれの距離の和はマンハッタンで求めるので、
S1 + [x座標がX以下の地点の数] - [x座標がXより大きい地点の数] = S2
が成り立つ。同じように(X, Y+1)を開始地点としたときの移動距離の和をS3とすると、
S1 + [y座標がY以下の地点の数] - [y座標がYより大きい地点の数] = S3
も成り立つ。
Nが奇数の場合
結論から言うと、開始地点を(全地点のx座標の中央値, 全地点のy座標の中央値)にすると移動距離の和が最小になる。
何故最小になるのか
この地点を(A, B)とし、この時の移動距離の和をSとする。この時、開始地点を(A+1, B)にした時の移動距離の和をS'とすると、
S + [x座標がA以下の地点の数] - [x座標がAより大きい地点の数] = S'
となる。ここで、Aは全地点のx座標の中央値なので、[x座標がA以下の地点の数]は(N-1)/2+1以上になり、[x座標がAより大きい地点の数]は(N-1)/2以下になる。よって、
S + [(N-1)/2+1以上] - [(N-1)/2以下] = S'
S + [1以上] = S'
となる。これは、開始地点を「全地点のx座標の中央値」からx方向に+1した地点から始めると、「全地点のx座標の中央値」から始めた時と比べて移動距離の和が大きくなる、ということを表している。同じように(A-1, B), (A, B+1), (A, B-1)から始めた場合も移動距離の和は大きくなる。つまり、(A, B)から始めると移動距離の和が最小になる。
Nが偶数の場合
奇数の時と同じように(全地点のx座標の中央値, 全地点のy座標の中央値)を開始地点にすれば良い。
良くない。
全地点のx座標は偶数個あるので、真ん中は2つある。xとyでそれぞれ2個ずつあるので、開始地点の候補は2*2で4個出来てしまう。
ここでどうすればよいか。
開始地点の候補は4個しか無いので、4箇所それぞれの移動距離の和を求めて、その中から最小値を選べば良い。
移動距離の和を求める
基本的には開始地点と各地点を往復しなければならないが、最終地点のみ片道で良い。
どの地点を最終地点にすれば良いか。
開始地点から最も遠い点を最終地点にすれば、最小の「移動距離の和」が求められる。
計算量は、ソートする時にかかるO(NlogN)である。
