※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ2111~2120」の編集履歴(バックアップ)一覧に戻る

AOJ2111~2120 - (2012/07/26 (木) 18:03:23) のソース

*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[次に両端のどちらの点から新しい線分を伸ばすか][これから新しく線分を伸ばす場所はどの線か][今までつなげた線分のリスト]=ここまでの折れ線の最小の長さ。
で動的計画法を適用していくだけの簡単な問題です。
この問題私はあまりいい解法ではなかったようでコード実行速度が出ませんでした。
私の場合スタート時全ての線分を折れ線の開始候補としていますがもしかしたらどこか一本の線分からスタートしていくだけでいいのかもしれません。

この問題を解いた時点でカンニングして解いたプロコンの過去問題は480問中31問。

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




 #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++){
					//線分p1から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++;
	}
 }