AOJ0563 Walking Santa

問題リンク Walking Santa

• 解法

x座標方向とy座標方向について独立に考えます。
ある点Xと、N個のx座標の差の絶対値の総和が最小になる場所はど真ん中の座標です。例えば、Nが奇数なら中央のx座標、Nが偶数個なら中央2つのx座標の区間内が最小になる場所です。
ここまでは分かったのですがWAを連発したのでジャッジデータを拾ってきたところ、答えの座標は総和が最小になる点の組み合わせのどれかになりそうな雰囲気だったので、それで試したところAcceptしました。
なんでじゃと思って色々調べたらおおよそ以下のような理由になりそうです。
「家を1個だけ往復しない」が非常に厄介なので、家を2倍し、そのうち1つの家に訪れないという風に解釈を変更します。
2*N個の点について、上記と同じ議論をします。つまり、x座標についての総和が最小になる場所はどこかを考えます。ここで、1つの家は訪れないので考える点は必ず2*N-1個と奇数になり、最小になる場所は1点しかないことが分かります。これはつまり、サンタの降りる場所はどこかの家の真上になるということです。訪れない家はN通りあるわけですが、どこを取り除いても、最小となる場所は大して変化しないでしょう。なので、サンタが降りるべき場所はかなり限られ、「総和が最小になる点の組み合わせ」だけ調べるだけで答えが発見できた、といえそうです。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Walking Santa
public class AOJ0563 {

	long res, rx, ry;
	int n;
	int[] x, y;
	int[][] p;
	
	void f(int px, int py){
		long max = 0, sum = 0;
		for(int i=0;i<n;i++){
			long len = Math.abs(px-p[i][0])+Math.abs(py-p[i][1]);
			sum+=2*len;
			max = Math.max(max, len);
		}
		if(sum-max < res){
			res = sum-max;
			rx = px; ry = py;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		sc.nextInt(); sc.nextInt();
		n = sc.nextInt();
		x = new int[n]; y = new int[n];
		p = new int[n][2];
		for(int i=0;i<n;i++){
			x[i] = p[i][0] = sc.nextInt(); y[i] = p[i][1] = sc.nextInt();
		}
		Arrays.sort(x);
		Arrays.sort(y);
		res = 1L<<60;
		f(x[(n-1)/2], y[(n-1)/2]);
		f(x[(n-1)/2], y[n/2]);
		f(x[n/2], y[(n-1)/2]);
		f(x[n/2], y[n/2]);
		System.out.println(res);
		System.out.println(rx+" "+ry);
	}
	
	public static void main(String[] args) {
		new AOJ0563().run();
	}
}