kmjp's blog

競技プログラミング参加記です

AtCoder ARC #065 : E - へんなコンパス / Manhattan Compass

しょうもないミスでWAも含め大幅タイムロスした。
http://arc065.contest.atcoder.jp/tasks/arc065_c

問題

2次元座標上にN個の異なる格子点が与えられる。
初期状態では2点(A,B)を指している。(A,B)と(B,A)を指していることは同じとみなす。

2点(P,Q)を指している状態で、別の頂点Rに対し、P-Q間とQ-R間のマンハッタン距離が等しい場合、(Q,R)を指す状態に移行できる。
この処理を繰り返し、移行できる状態は何通りあるか。

解法

A,B間のマンハッタン距離をTとする。
するとこの問題は以下のように言い換えられる。

頂点Aからはじめ、マンハッタン距離がTの頂点間に辺をつなぐ。
全部でいくつの辺ができるか。

さらに言い換えると、以下の2つが行えればよい。

  • 各頂点Vに対し、マンハッタン距離がTの頂点数を数え上げる。
  • 頂点Aからはじめ、マンハッタン距離がTの頂点Vに対し再帰的に上記処理を行う。

最後に前者で求めた頂点数を2で割る。

ここからはマンハッタン距離に関する定番テクで解くことができる。
座標をVp=Vx+Vy,Vq=Vy-Vxと45度回転するような感じで変換しよう。
するとマンハッタン距離がTの頂点は、変換後の座標でVを中心とする正方形の辺上に来る。
あとはlower_boundなどを使い、正方形の辺上の頂点数を高速に数え上げるとともに、DFSで処理しよう。

int N,A,B;
ll X[101010],Y[101010],T;
map<ll,vector<pair<ll,int>>> U,D;
map<ll,set<pair<ll,int>>> US,DS;
ll ret;

void dfs(int cur) {
	ll UD=Y[cur]-X[cur];
	ll DD=Y[cur]+X[cur];
	
	US[UD].erase({X[cur],cur});
	DS[DD].erase({X[cur],cur});
	
	ret += lower_bound(ALL(U[UD+T]),make_pair(X[cur],0))  -lower_bound(ALL(U[UD+T]),make_pair(X[cur]-T,0));
	ret += lower_bound(ALL(D[DD+T]),make_pair(X[cur]+T+1,0))-lower_bound(ALL(D[DD+T]),make_pair(X[cur],0));
	ret += lower_bound(ALL(U[UD-T]),make_pair(X[cur]+T,0))-lower_bound(ALL(U[UD-T]),make_pair(X[cur],0));
	ret += lower_bound(ALL(D[DD-T]),make_pair(X[cur],0))  -lower_bound(ALL(D[DD-T]),make_pair(X[cur]-T+1,0));
	
	while(1) {
		auto it=US[UD+T].lower_bound({X[cur]-T,0});
		if(it==US[UD+T].end() || it->first>X[cur]) break;
		dfs(it->second);
	}
	while(1) {
		auto it=US[UD-T].lower_bound({X[cur],0});
		if(it==US[UD-T].end() || it->first>X[cur]+T) break;
		dfs(it->second);
	}
	while(1) {
		auto it=DS[DD+T].lower_bound({X[cur],0});
		if(it==DS[DD+T].end() || it->first>X[cur]+T) break;
		dfs(it->second);
	}
	while(1) {
		auto it=DS[DD-T].lower_bound({X[cur]-T,0});
		if(it==DS[DD-T].end() || it->first>X[cur]) break;
		dfs(it->second);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	A--,B--;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		U[Y[i]-X[i]].push_back({X[i],i});
		D[X[i]+Y[i]].push_back({X[i],i});
		US[Y[i]-X[i]].insert({X[i],i});
		DS[X[i]+Y[i]].insert({X[i],i});
	}
	
	T=abs(X[A]-X[B])+abs(Y[A]-Y[B]);
	
	FORR(r,U) sort(ALL(r.second));
	FORR(r,D) sort(ALL(r.second));
	
	dfs(A);
	cout<<ret/2<<endl;
}

まとめ

なぜか決め打ちで先頭の頂点からDFSするコードを書いて時間をロスした。