AtCoder ARC #024 : D - バス停

本番は部分点のみで残念。
http://arc024.contest.atcoder.jp/tasks/arc024_4

問題

N個の点の座標が与えられる。
各点からは上下左右には移動できるが、途中で曲がることはできない。
ただし、新たな点を追加すると、その点では曲がることができる。

幾つか点を加え、互いの点同士をマンハッタン距離で最小で移動可能にせよ。
ただし点の数が10000個を超えることはできない。

解法

部分点は容易。
N<=100なので、X座標またはY座標のいずれかがN個の点と一致するN^2個の座標すべてに点を置けばよい。

N<=1000の場合、(N*logN)個の点で条件を満たすようにすれば10000個を超えない。
このためには、まずN個の点をX座標順にソートし、二分探索の要領で追加の点を置いていく。
例えば[L,R]の範囲の点を条件を満たすようにすることを考える。([0,N]が求める答えとなる)
まずは軸となる中点p=(L+R)/2を取る。そしてp番目の点と同じX座標X[p]上で、L～Rの各点のY座標と同じ位置に点を追加する。するとL～(p-1)番の点と(p+1)～R番の点はX座標X[p]のどこかの点を通ることで互いに移動可能となる。
後は再帰的に[L,p-1]と[p+1,R]に同じ処理を行えばよい。

二分探索するたびに各X座標に追加する点の数は半減していくので、全体の点の数はN*logNとなる。

int N;
int isis[1001][1001];
pair<int,int> P[1001];
set<pair<int,int> > S;

void dodo(int L,int R) {
	int p=(L+R)/2,i,x;
	if(L+1>=R) return;
	set<int> s;
	for(i=L;i<R;i++) s.insert(P[i].second);
	x = P[p].first;
	ITR(it,s) if(isis[x][*it]==0) isis[x][*it]=1, S.insert(make_pair(x,*it));
	dodo(L,p);
	dodo(p+1,R);
}

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	FOR(i,N) {
		cin>>P[i].first>>P[i].second;
		isis[P[i].first][P[i].second] = 1;
	}
	sort(P,P+N);
	dodo(0,N);
	
	_P("%d\n", S.size());
	ITR(it,S) _P("%d %d\n",it->first,it->second);
}

まとめ

わかってしまえばあっさりな問題。
本番、数の制限からうまく二分探索してN*logN個配置するんだろうなとは思ったけど、こんな単純に行くとは思わなかった。