幾何コンテスト2013 : B - 玉座の間

本番はいいところまで行って部分点止まり。
終了後に他人のコードを見て復習。
http://geocon2013.contest.atcoder.jp/tasks/geocon2013_b

問題

２次元座標上にN個の点が与えられる。
これらの点をY軸に線対称になるように移動する場合、各点の移動距離の総和を最小化し、その値を返せ。

解法

点群が線対称になるには、各点が以下の様になるように移動すればよい。

• 点がY軸上に来る。このときの移動距離はX座標の絶対値。
• 他の点と線対象の関係になるように動く。このときの２点の移動距離の和は、片方の点をY軸対称な位置に動かした点と、もう一つの点の距離。

つまり、基本的には各点が前者になるように動くが、もし２点を選んで線対称に来るように動かしたとき、前者よりも移動距離の和が減るならそちらを選ぶのが良い。

また、X座標の正負が一致する点同士は後者が前者より小さくなることはない。
よって、後者の組み合わせはX座標の正負が異なるものにしかならない。

ここで推測がつくのは、これはマッチング問題であり最小コストフローで解けるということ。
ただ、本番そこまでは気が付いたもののうまくグラフが作れずWAを連発した。
しょうがないので、組わせを総当たりするコードで100点まで取得。以下はそのケース。

int N;
int X[101],Y[101];
double D[101][101];
double res=1e10;

double dist(int c1,int c2) {
	int nx=(X[c1]+X[c2]);
	int ny=(Y[c1]-Y[c2]);
	
	return min(abs(X[c1])+abs(X[c2])+0.0,sqrt(nx*nx+ny*ny));
}

double dfs(int cur,int mask, double res) {
	double t=res;
	int i;
	if(cur>=N) return res;
	if(mask & (1<<cur)) return dfs(cur+1,mask,res);
	
	t=dfs(cur+1,mask|(1<<cur),res+abs(X[cur]));
	for(i=cur+1;i<N;i++) {
		if(mask & (1<<i)) continue;
		if(X[cur]*X[i]>=0) continue;
		
		t=min(t,dfs(cur+1,mask|(1<<i),res+D[cur][i]));
	}
	return t;
}

void solve() {
	int f,r,i,j,k,l,x,y,np,nn;
	int used[101];
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(x,N) FOR(y,N) D[x][y]=dist(x,y);
	ZERO(used);
	
	if(N>20) return;
	_P("%.12lf\n",dfs(0,0,0));
	
	return;
}

次に終了後に解いた完答版。
まず、全部の点をY軸に移動する場合の移動距離を求めておく。
次に、X座標が正の点から負の点に辺を張り、そのコストを後者のケースから前者のケースの移動距離を引いたものとしてグラフを作る。
こうすると各辺のコストが負になるグラフができるので、その最小コストフローを求め、最初に移動した移動距離の和から引けばよい。

class MinCostFlow {
public:
	struct edge { ll to, capacity; double cost; ll reve;};
	static const int MV = 5000;
	vector<edge> E[MV];
	double dist[MV];
	ll prev_v[MV], prev_e[MV], NV;
	
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) E[i].clear();}
	void add_edge(int x,int y, ll cap, double cost) {
		E[x].push_back((edge){y,cap,cost,E[y].size()});
		E[y].push_back((edge){x,0, -cost,E[x].size()-1}); /* rev edge */
	}
	
	double mincost(int from, int to, ll flow) {
		double res=0;
		int i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, 1e10);
			dist[from]=0;
			bool up=true;
			while(up) {
				up=false;
				FOR(v,NV) {
					if(dist[v]==1e10) continue;
					FOR(i,E[v].size()) {
						edge &e=E[v][i];
						if(e.capacity>0 && dist[e.to]>dist[v]+e.cost) {
							dist[e.to]=dist[v]+e.cost;
							prev_v[e.to]=v;
							prev_e[e.to]=i;
							up=true;
						}
					}
				}
			}
			
			if(dist[to]==1e10) return -1;
			ll lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};

int N;
int X[101],Y[101];
double D[101][101];

double dist(int c1,int c2) {
	int nx=(X[c1]+X[c2]);
	int ny=(Y[c1]-Y[c2]);
	
	return min(abs(X[c1])+abs(X[c2])+0.0,sqrt(nx*nx+ny*ny));
}

void solve() {
	int f,r,i,j,k,l,x,y,np,nn;
	int used[101];
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(x,N) FOR(y,N) D[x][y]=dist(x,y);
	double res=0;
	FOR(x,N) res+=abs(X[x]);
	ZERO(used);
	
	MinCostFlow mcf;
	mcf.init(5000);
	np=nn=0;
	
	FOR(i,N) if(X[i]>0) np++;
	FOR(i,N) if(X[i]<0) nn++;
	
	if(nn>np) FOR(i,N) X[i]=-X[i];
	
	FOR(i,N) if(X[i]>0) {mcf.add_edge(0,i+1,1,0);mcf.add_edge(i+1,1000,1,0);}
	FOR(i,N) if(X[i]<0) mcf.add_edge(N+i+1,1000,1,0);
	FOR(x,N) FOR(y,N) if(X[x]>0 && X[y]<0) mcf.add_edge(x+1,N+y+1,1,D[x][y]-abs(X[x])-abs(X[y]));
	
	res+=mcf.mincost(0,1000,max(nn,np));
	_P("%.12lf\n",res);
	
	return;
}

まとめ

手元の最小コストフローのライブラリはコストが整数前提だったので、書き換えに手間取った。
途中ミスで無限ループとか作りこんじゃったし。

あと、最小コストフローって負のコストでも使えるのね…。
そこに気づかず本番中に解けなかった。総当たりで100pt取れたのは良かったけどね。