「AOJ2111～2120」の編集履歴（バックアップ）一覧に戻る

AOJ2111～2120 - (2012/07/26 (木) 19:41:30) の編集履歴(バックアップ)

---

2117　Connect Line Segments

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2117
平面上に散らばってる線分を繋げて一本の長い折れ線を作るとき、最小の長さの折れ線を作った時の長さを答えよという問題。
プログラミングコンテストの過去問を1000問解いたって学歴、職歴、実績の三無い人間の私では世間から何の評価もされません。
プロコンの問題を解くことは私にとって単なる趣味でしかないのです。
使い捨て労働で仕事を探しながらこの趣味を完遂するのだけが楽しみです。
何かアプリでも作って売れたら世間からの評価も変わるかもしれないのでその可能性にかけるくらいです。

解法
さてこの問題自分なりに考えた解法は2種類で以下の通りです。
コード実行速度が悪いコードとコード実行速度2位のコードです。
単純に深さ優先探索を行うと線分が10本を超えたあたりで10！*2^10となり計算量が限界を超えます。
13や14などは枝刈で挑むのは論外です。
分岐が不可能なのでプリム法も使えません。
よって動的計画法を使わなくてはいけません。
動的計画法は、memo[次に両端のどちらの点から新しい線分を伸ばすか][これから新しく線分を伸ばす場所はどの線か][今までつなげた線分のリスト]=ここまでの折れ線の最小の長さ。
で動的計画法を適用していくだけの簡単な問題です。
この問題私はあまりいい解法ではなかったようでコード実行速度が出ませんでした。
私の場合スタート時全ての線分を折れ線の開始候補としていますがもしかしたらどこか一本の線分からスタートしていくだけでいいのかもしれません。

コード実行速度2位の方は1つの線分を結んだ、2つの線分を結んだ、、、ｎ個の線分を結んだまでが綺麗な順序で無駄なく実行されるようにソートしてから動的計画法を適用して解いています。
毎回思うが一位の壁は厚い、ランキング上位に入れても一位を抜けることはめったにない、一位手ごわすぎ。

2位のコード実は動的計画法のｎ/２本目まで線分を結んだところで残り半分は実は計算する必要はありません。
結んでない線分の補集合を取ってその折れ線との結びつきを試せば真中で計算が終わります。
しかしこれでコード実行速度1位を取れますがコードが少し膨らみますし2倍しか早くならないのでたかが練習問題でそこまでして一位を取る必要もないかなと考えます。

この問題を解いた時点でカンニングして解いたプロコンの過去問題は480問中31問この比率をこれからどんどん下げていくのが楽しみです。

#include<stdio.h>
#include<queue>
#include<math.h>
#include<string.h>
struct State{
int nowNo,perm,r;//今いる地点と結んだ線分のリストのビット表現と次の向き
double len;//今まで引いた長さ
bool operator<(const State& s)const{
	return len>s.len;
}
};
double memo[2][14][2<<14];//[次の線分の出発点][最後に結んだ線分][結んだ線のビット表現]
bool   first[2][14][2<<14];//最初
void setData(int n,int i){
double xs[2][15],ys[2][15];
memset(first,true,sizeof(first));
for(int i=0;i<n;i++){
	scanf("%lf %lf %lf %lf",&xs[0][i],&ys[0][i],&xs[1][i],&ys[1][i]);
}
//printf("scanOK");

double lensMemo[2][2][15][15],len1;//線分で結ぶ時の距離のメモ
for(int l1=0;l1<n;l1++){
	for(int l2=0;l2<n;l2++){
		if(l1==l2)continue;//同じ線分は結ばない
		for(int r1=0;r1<2;r1++){
			for(int r2=0;r2<2;r2++){
				len1=sqrt(pow(xs[r1][l1]-xs[r2][l2],2)+pow(ys[r1][l1]-ys[r2][l2],2));
				lensMemo[r1][r2][l1][l2]=len1;
			}
		}
	}
}
//スタート地点となる線分のリストを作る
std::priority_queue<State> pQ;
State s,nextS;
int ansPerm=0;
s.len=0;//長さ0
for(int i=0;i<n;i++){
	s.r=0;//どちらの両端から出発するか
	s.perm=(1<<i);//スタートの線分を使用禁止にする
	s.nowNo=i;//今いる線分
	pQ.push(s);
	s.r=1;//逆の端から出発する
	pQ.push(s);
	ansPerm|=(1<<i);//答えの組み合わせを立てておく
}
double ansLen=0;
for(int i=0;i<n;i++){
	ansLen+=sqrt(pow(xs[0][i]-xs[1][i],2)+pow(ys[0][i]-ys[1][i],2));
}	
while(!pQ.empty()){
	s=pQ.top();
	pQ.pop();
	if(s.perm==ansPerm)break;//答え到達
	len1=memo[s.r][s.nowNo][s.perm];
	if(first[s.r][s.nowNo][s.perm]==false&&len1<s.len)continue;//これより短い折れ線があった
	memo[s.r][s.nowNo][s.perm]=s.len;
	first[s.r][s.nowNo][s.perm]=false;
	for(int i=0;i<n;i++){
		if((s.perm&(1<<i))!=0)continue;//この線分は接続済み
		nextS.perm=(s.perm|(1<<i));
		nextS.nowNo=i;
		nextS.len=s.len+lensMemo[s.r][0][s.nowNo][i];//端点0と線分でつなげる
		nextS.r=1;//次は端点1からスタート
		len1=memo[nextS.r][nextS.nowNo][nextS.perm];
		if(first[nextS.r][nextS.nowNo][nextS.perm]==true||len1>nextS.len){//より短いルートか初めて
			memo[nextS.r][nextS.nowNo][nextS.perm]=nextS.len;
			first[nextS.r][nextS.nowNo][nextS.perm]=false;
			pQ.push(nextS);
		}
		nextS.len=s.len+lensMemo[s.r][1][s.nowNo][i];//端点1と線分でつなげる
		nextS.r=0;//次は端点0から出発
		len1=memo[nextS.r][nextS.nowNo][nextS.perm];
		if(first[nextS.r][nextS.nowNo][nextS.perm]==true||(len1>nextS.len)){//より短いルートか初めてだった
			memo[nextS.r][nextS.nowNo][nextS.perm]=nextS.len;
			first[nextS.r][nextS.nowNo][nextS.perm]=false;
			pQ.push(nextS);
		}
	}
}
printf("Case %d: %.5lf\n",i,s.len+ansLen);
}
int main(){
int n,i=1;
while(1){
	scanf("%d",&n);
	if(n==0)break;
	setData(n,i);
	i++;
}
}

タイムが遅かったので高速化してみました。

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<bitset>
double memo[2][14][2<<14];//[次の線分の出発点][最後に結んだ線分][結んだ線のビット表現]
bool   first[2][14][2<<14];//最初
void setData(int n,int i){
double xs[2][15],ys[2][15];
memset(first,true,sizeof(first));
for(int i=0;i<n;i++){
	scanf("%lf %lf %lf %lf",&xs[0][i],&ys[0][i],&xs[1][i],&ys[1][i]);
}
//printf("scanOK");
double lensMemo[2][2][15][15],len1;//線分で結ぶ時の距離のメモ
for(int l1=0;l1<n;l1++){
	for(int l2=0;l2<n;l2++){
		if(l1==l2)continue;//同じ線分は結ばない
		for(int r1=0;r1<2;r1++){
			for(int r2=0;r2<2;r2++){
				len1=sqrt(pow(xs[r1][l1]-xs[r2][l2],2)+pow(ys[r1][l1]-ys[r2][l2],2));
				lensMemo[r1][r2][l1][l2]=len1;
			}
		}
	}
}
//引かれてる線分の長さを集計しておく
double ansLen=0;
int ansPerm=0;//全部の線分を繋げた後の組み合わせ
for(int i=0;i<n;i++){
	ansLen+=sqrt(pow(xs[0][i]-xs[1][i],2)+pow(ys[0][i]-ys[1][i],2));
	ansPerm|=(1<<i);
	memo[0][i][1<<i]=memo[1][i][1<<i]=0;//スタート地点の線分を設定
}
int perm1,nextPerm;
std::vector<int> perm[16];//結んだ線分の組み合わせ
std::bitset<16> b;
for(int i=1;i<(1<<n);i++){
	b=i;
	perm[b.count()].push_back(i);
}
double nextLen,ans2=1000000000;;
for(int i=1;i<n;i++){
	for(int j=0;j<perm[i].size();j++){
		perm1=perm[i][j];//
		for(int p1=0;p1<n;p1++){
			if((perm1&(1<<p1))==0)continue;//この組み合わせは駄目
			for(int p2=0;p2<n;p2++){
				//線分ｐ１からｐ２へと繋げる
				if((perm1&(1<<p2))!=0)continue;//これはもう繋げている
				if(p1==p2)continue;//あり得ないが念のため
				nextPerm=(perm1|(1<<p2));
				for(int r1=0;r1<2;r1++){
					for(int r2=0;r2<2;r2++){
						nextLen=lensMemo[(r1+1)&1][r2][p1][p2]+memo[r1][p1][perm1];
						//printf("%lf>",nextLen);
						if(first[r2][p2][nextPerm]==true){
							first[r2][p2][nextPerm]=false;
							memo[r2][p2][nextPerm]=nextLen;
						}else if(memo[r2][p2][nextPerm]>nextLen){
							memo[r2][p2][nextPerm]=nextLen;
						}
						if(nextPerm==ansPerm&&ans2>nextLen)ans2=nextLen;
					}
				}					
			}
		}
	}
}	
printf("Case %d: %.5lf\n",i,ansLen+ans2);
}
int main(){
int n,i=1;
while(1){
	scanf("%d",&n);
	if(n==0)break;
	setData(n,i);
	i++;
}
}