問題文
Exposition | Aizu Online Judge
感想
かなり時間かけた。解けると嬉しいですねえ。問題文は日本語なので略。これが距離の総和とかだったらどうやって解くんだろう・・・。誰もブログに解法書いてくれないし情報オリンピックも解法公開しないし陰謀じゃないかと思いつつ解法書いてみる。
ヒント
JAPLJさんとこのマンハッタン距離の最遠点対についての説明
(2点のマンハッタン距離) = |x1-x2| + |y1-y2|を場合分けしてうまく整理すると、
- (x1+y1) + (-x1-y2)
- (-x1+y1) + (x2-y2)
- (x1-y1) + (-x2+y2)
- (-x1-y1) + (x2+y2)
という式が出来上がって、本物のマンハッタン距離はこの中のいずれかが取る最大値(当然)。
この式が何を意味するかというと、一番上は、(x1+y1)が最大になるような点 と、(-x1-y2)が最大になるような点だけを探せばよくて、その下は(-x1+y1)が最大になる点と(x2-y2)が最大になるようなだけ点を探せば良い。(x+y)が最大になるような点とかはうまく管理してやる。
解法
↓反転
基本方針はpriority_queueを用いた貪欲。最大を最小化するので、最遠点対をできるだけ分けていく。
説明の簡単化のために、使ってない点の集合をS , 既に分けられた点が入っている２つの集合をA,Bとする。
- 4つのpriority_queueを用意して、その中にそれぞれの点について、さっきの４通りの値をぶちこむ。要するに(x+y),(-x+y),(x-y),(-x-y)用のpriority_queue(使ってない点の集合S用)を作る。
- その中から最大になるような組み合わせを選ぶんだけど、ここでSの中で距離が最大２点を選んで追加するとかやるのは嘘解法。なぜ問題かというと、既に分けられている点(A,Bに入っている点)のことを考えていないから。
- そこでそれらことを考えてあげるために、A,B用のpriority_queueを２つさらに用意しておく。(2つの集合に分ける問題なので)
- そうすると、『Sの中から2つ選び距離が最大になるような点』と『SとAで最大になるような点』と『SとBで最大になるような点』の３通りを考えれば良いことが分かる。後ろの２つは、ＳとＡで最大になるならその点対のＳの方をＢに入れてやり、逆ならＡに入れてやればよい。前者はどっちに入れたら距離が最小化されるか頑張ってシミュレーションして良い方につっこめば良い。
- 最後に、A,Bそれぞれ2の集合の独立した点対の距離で最大のものを出力すれば良い。
ソース
死ぬほど汚い。無駄に関数ポインタとか使ってる・・・(本当に無駄)。
#include <iostream> #include <vector> #include <queue> #include <cassert> #include <algorithm> using namespace std; #define INF (-(1<<29)) int A_(int x,int y){ return x+y; } int B_(int x,int y){ return x-y; } int C_(int x,int y){ return -x+y; } int D_(int x,int y){ return -x-y; } priority_queue< pair<int,int> > Q[3][4]; int (*f[4])(int x,int y) = {A_,B_,C_,D_}; pair<int,int> item[100000]; int used[100000]; int get(priority_queue< pair<int,int> > &A , priority_queue< pair<int,int> > &B){ if(A.size() == 0 || B.size() == 0) return 0; //if(A.top().second == B.top().second) return INF; return A.top().first + B.top().first; } int get2(priority_queue< pair<int,int> > &A , int B){ if(A.size() == 0) return 0; //if(A.top().second == B.top().second) return INF; return A.top().first + B; } int chk(int A,int B){ if(Q[1][0].size()==0){ return 0; }else{ int ans = 0; ans = max( ans , get2(Q[1][0],f[3](item[A].first,item[A].second) ) ); ans = max( ans , get2(Q[1][1],f[2](item[A].first,item[A].second) ) ); ans = max( ans , get2(Q[2][0],f[3](item[B].first,item[B].second) ) ); ans = max( ans , get2(Q[2][1],f[2](item[B].first,item[B].second) ) ); return ans; } } int chkk(int A,priority_queue< pair<int,int> > R[4]){ int ans = 0; ans = max( ans , get2(R[0],f[3](item[A].first,item[A].second) ) ); ans = max( ans , get2(R[1],f[2](item[A].first,item[A].second) ) ); return ans; } int put(int A,int B){ if(A != -1) for(int j = 0 ; j < 4 ; j++) Q[1][j].push(make_pair(f[j](item[A].first,item[A].second),A)); if(B != -1) for(int j = 0 ; j < 4 ; j++) Q[2][j].push(make_pair(f[j](item[B].first,item[B].second),B)); if(A != -1) used[A] = true; if(B != -1) used[B] = true; } int main(){ int n; cin >> n; for(int i = 0 ; i < n ; i++){ int x,y; cin >> x >> y; item[i] = make_pair(x,y); for(int j = 0 ; j < 4 ; j++){ Q[0][j].push(make_pair(f[j](x,y),i)); } } //int lastDistance; while(Q[0][0].size()){ int sub = -1 , h = -1 , aa , bb; for(int i = 0 ; i < 3 ; i++){ for(int j = 0 ; j < 4 ; j++){ int r = get( Q[0][j] , Q[i][3-j] ); if( r > sub){ sub = r; h = i; aa = Q[0][j].top().second; bb = Q[i][3-j].top().second; } } } if(h==0){ if( max( chkk(aa,Q[1]) , chkk(bb,Q[2]) ) > max( chkk(aa,Q[2]) , chkk(bb,Q[1]) ) ){ put(bb,aa); }else{ put(aa,bb); } }else if(h==1){ put(-1,aa); }else{ put(aa,-1); } for(int i = 0 ; i < 4 ; i++){ while(Q[0][i].size() && used[Q[0][i].top().second]) Q[0][i].pop(); } } int ans = 0; for(int i = 1 ; i < 3 ; i++){ for(int j = 0 ; j < 4 ; j++){ int r = get( Q[i][j] , Q[i][3-j] ); ans = max( ans , r ); } } cout << ans << endl; }
