JOI2011本戦　第四問「歩くサンタクロース」

JOI

今回から「負け惜しみの解説講座」みたいになるんじゃないかとヒヤヒヤしてたんですが、大丈夫でした(汗
問1 (20点) 内訳 ○○○○○○○○○○
問2 (20点) 内訳 ○○○○○○○○○○
問3 (14点) 内訳 ○○○○××○○×○
問4 (0点) 内訳 ××××××××××××××××××××
問5 (4点) 内訳 ○○××××××××


本戦では、
「うわ、マンハッタン距離や」
とか思って、去年の４番のトラウマのせいで考える気が失せてしまった・・・

  • X軸方向とY軸方向に分けて考える。

これを聞いてひらめく人は多いはず。
では、具体的にやっていきますか。

f:id:snuke:20110216191416p:image:left

5 4
3
1 1
3 4
5 3

入力例１です。
まずは各家までの距離を最小化することを考えてみましょう。
とりあえず各家の座標をX,Y方向に分けてソートします。

X : 1,3,5
Y : 1,3,4

データ数が少なくて むなしいですが、気にしない。
まずは X軸方向から。
f:id:snuke:20110216193524p:image
仮に２の地点に降り立ったとすると、各家までの距離の和は５です。
降り立つ地点を移動させてみましょう。
まず、左に a だけ動かしたとしましょう。
右向きの矢印が１本、左向きの矢印が２本なので、距離の和は
5 - a + 2a = 5 + a
となり、増えてしまいます。
右に a 動かすと、同様にして距離の和は
5 - a
となり、減ります！
ということは右に動かす方が良さそうですね。
f:id:snuke:20110216195114p:image
しかし、調子に乗ってどんどん右に動かすとこうなります。
３の地点を過ぎたところから距離の和は増え始めるんですね。
というわけで、
真ん中に降り立てばいい！
ということが分かります。
では次、Y軸方向〜
f:id:snuke:20110216195720p:image
はい、真ん中に降り立ってみました。
交差点にしか降り立てなかった気がしますが、今は気にしない。
とりあえず、距離の和は 4.5です。
これでいいんでしょうか？
答えは否！３の地点に降り立つと、距離の和は４になるんです！
図の矢印の数を数えてみると分かるんですが、上図は

  • 右向き矢印：１個
  • 左向き矢印：２個

なので、距離の和を減らせる余地があるんですね。
というわけで、
右向き矢印と左向き矢印の数が等しい地点に降り立てばいい！
んです。
言い換えると、
N個の家のうちの、N/2番目の家の座標に降り立てばいい！
と、おおまかにこうなります。

往復しなきゃいけないよね？

往復するときの距離は、片道の距離×２となるのはOKですね？
最後の家は片道だけでいいので、全体の合計は

  • 各家までの距離の和×２ − 最後の家までの距離

です。
もう少しだけ発想を転換すると、

  • 最後の家以外の家は２件ずつ存在する。
  • その上で、各家までの距離の和を求める。

となります。
すると、最後の家が変わると真ん中の家も変わるんじゃないか？という疑問が湧いてきます。
え？湧いてこない？　湧いてくることにしておいてください！
調べてみましょう。
X座標の値が小さい家から順に X1,X2,X3….と呼ぶことにします。


まずは、家が５個（奇数個）の場合
X1 X2 X2 X3 X3 X4 X4 X5 X5
X1 X1 X2 X3 X3 X4 X4 X5 X5
X1 X1 X2 X2 X3 X4 X4 X5 X5
X1 X1 X2 X2 X3 X3 X4 X5 X5
X1 X1 X2 X2 X3 X3 X4 X4 X5
真ん中の家は常にX3ですね。
つまり、降り立つ地点のX座標は X3の座標となります。


つぎに、家が４個（偶数個）の場合
X1 X2 X2 X3 X3 X4 X4
X1 X1 X2 X3 X3 X4 X4
X1 X1 X2 X2 X3 X4 X4
X1 X1 X2 X2 X3 X3 X4
真ん中の家はX2 or X3ですね。
つまり、降り立つ地点のX座標は X2 or X3 の座標となります。


まとめると、

  • 家が奇数個なら真ん中の１つ
  • 家が偶数個なら真ん中の２つ

が降り立つ地点の候補になります。


ソートに一番時間がかかるので、O(N log N)　ですかね。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;
typedef long long ll;

int main(){
	int w, h, n, ax, ay, ansx, ansy, maxd, d;
	ll ansd = 1ll << 62, sumd;
	vector<int> x, rx, y, ry, cx, cy;
	
	scanf("%d%d%d", &w, &h, &n);
	
	rep(i,n){
		scanf("%d%d", &ax, &ay);
		x.pb(ax); rx.pb(ax);
		y.pb(ay); ry.pb(ay);
	}
	
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	
	if (n%2){
		cx.pb(x[n/2]);
		cy.pb(y[n/2]);
	} else {
		cx.pb(x[n/2-1]); cx.pb(x[n/2]);
		cy.pb(y[n/2-1]); cy.pb(y[n/2]);
	}
	
	rep(i,cx.size()) rep(j,cy.size()){
		sumd = 0; maxd = 0;
		rep(k,n){
			d = abs(rx[k] - cx[i]) + abs(ry[k] - cy[j]);
			sumd += d*2;
			maxd = max(maxd, d);
		}
		if (ansd > sumd - maxd){
			ansx = cx[i];
			ansy = cy[j];
			ansd = sumd - maxd;
		}
	}
	
	printf("%lld\n%d %d\n", ansd, ansx, ansy);
	
	return 0;
}

〜変数説明〜
w, h, n, ax, ay : 入力用
ansx, ansy, ansd : 答え
maxd, d, sumd : マンハッタン距離を代入
x, y : 各家のx,y座標を記録しておく。ソート用。
rx, ry : 各家のx,y座標を記録しておく。ソートしない。
cx, cy : 答えの候補。


だいぶ解説が雑くなって来ましたww
分からなければ聞いて下さいね。