「AOJ1131～1140」の編集履歴（バックアップ）一覧はこちら

「AOJ1131～1140」(2013/03/04 (月) 20:07:22) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*1138 Traveling by Stagecoach
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1138
この問題は動的計画法で解きます。
まずチケット８枚、都市数30の場合を考えます。
ある都市にいるときどのチケットを使ってるかを考えます。
そうすると状態数はチケットの使用組み合わせ２５６通り*今いる都市30通り＝7680個の点を持つグラフとなりこのグラフ上を移動する問題に翻訳できます。
このグラフに対して動的計画法を適用すれば解けます。
calc関数で動的計画法を実施します。
スタート地点のタイムは0です。
calc関数の外側のfor文一週目ではチケットを一枚も使ってない点だけを取り上げ動的計画法を適用します。
２週目ではチケットを一枚使った状態の点だけを取り上げ動的計画法を適用します。
３週目では２枚でこれを繰り返します。
最終的にループが終われば計算完了です。
ゴール都市でのタイムを最後のループで調べます。
この手法は泥臭い工夫ですが驚くほど効果があり、実行速度５位という良好な速度を叩き出しましたが僅差で一位を抜くことはできませんでした。
別の手法ですが、高速化の知恵を振りかけたダイクストラで攻略すれば１位を余裕で抜きされる可能性は高いです。




 #include<stdio.h>
 #include<vector>
 #include<bitset>
 double myMax=1000000000;//最大値
 double memoMoveTime[31][31][9];//mMT[都市１][都市２][チケットi]で移動したときにかかる時間
 double nowTime[31][257];//[都市i][チケットの状態s]で到達できた最短タイム
 double tickets[9];//チケットデータ
 int n,m,p,a,b;//チケット数、都市数、道路数、出発地、目的地
 std::vector<int> permMemo[9];//[k枚]チケットを使った場合の組み合わせ
 void calc(){
	int permMax=1<<n;//チケットで作れる組み合わせの総数
	int nextPerm,cHash;
	double nextTime;
	for(int k=0;k<n;k++){
		//今のところk枚チケットを使った
		for(int c1=0;c1<m;c1++){
			//都市ｃ1～スタート
			for(int c2=0;c2<m;c2++){
				//都市ｃ２への移動
				if(memoMoveTime[c1][c2][0]==myMax)continue;//道が通じてなかった
				for(int cNo=0;cNo<n;cNo++){
					//cNo番目のカードを使う
					cHash=1<<(cNo);//cNo番目のカードを使えるか
					for(int u=0;u<permMemo[k].size();u++){
						//チケットの組perm
						int perm=permMemo[k][u];
						if((perm&cHash)!=0)continue;//このカードは使用済みなので次へ
						if(nowTime[c1][perm]==myMax)continue;//この都市へ到達してないので次へ
						nextPerm=perm|cHash;
						nextTime=nowTime[c1][perm]+memoMoveTime[c1][c2][cNo];
						if(nowTime[c2][nextPerm]>nextTime){
							nowTime[c2][nextPerm]=nextTime;
						}
					}
				}
			}
		}
	}
	double ans=myMax;
	for(int p=0;p<permMax;p++){
		ans=ans>nowTime[b][p]?nowTime[b][p]:ans;
	}
	if(ans>=myMax){
		printf("Impossible\n");
	}else{
		printf("%lf\n",ans);
	}
 }
 void setData(){
	//データの初期化を行う
	//チケットデータの読み込み
	for(int i=0;i<n;i++){
		scanf("%lf",&tickets[i]);
	}
	//移動にかかる時間の初期化
	int c1,c2,cNo;
	double time;
	for(c1=0;c1<m;c1++){
		for(c2=0;c2<m;c2++){
			for(cNo=0;cNo<n;cNo++){
				memoMoveTime[c1][c2][cNo]=myMax;
			}
		}
	}
	//移動にかかる時間の設定
	for(int i=0;i<p;i++){
		scanf("%d %d %lf",&c1,&c2,&time);
		c1--;
		c2--;
		for(cNo=0;cNo<n;cNo++){
			memoMoveTime[c1][c2][cNo]=memoMoveTime[c2][c1][cNo]=time/tickets[cNo];
		}
	}
	for(c1=0;c1<m;c1++){
		for(cNo=0;cNo<256;cNo++){
			nowTime[c1][cNo]=myMax;
		}
	}
	nowTime[a][0]=0;
	for(int i=0;i<=n;i++)permMemo[i].clear();
	std::bitset<9> b;
	for(int p=0;p<(1<<n);p++){
		b=p;
		permMemo[b.count()].push_back(p);
	}
 }
 int main(){
	while(1){
		scanf("%d %d %d %d %d",&n,&m,&p,&a,&b);//基礎データ読み込み
		if(n+m+p+a+b==0)break;
		a--;//扱いやすいよう0ベースにする
		b--;
		
		setData();
		calc();
	}
 }

*1132　Circle and Points
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1132
平面上の点の座標が与えられるので一つの半径１の円で囲むことが出来る点の最大数を答える問題。

解法
回転行列の概念を使って交点を求めます。
後は交点を中心に円を描いたとき何個の点を囲めるかを確かめるだけです。
どうしようＡＯＪの問題を５７３問解いたけど、残りの問題どれをみても解法を思いつかないのばっかりだ、、、


 #include<stdio.h>
 #include<math.h>
 #include<vector>
 
 void calc(double x1,double y1,double x2,double y2,std::vector<double>& pxs,std::vector<double>& pys){
 	double len,len2,x3=x2-x1,y3=y2-y1,cos1,sin1,cos2,sin2,ansX,ansY;
 	len=hypot(x3,y3);
 	len2=len/2.0;
 	cos1=x3/len;
 	sin1=y3/len;
 	sin2=sqrt(1.0-len2*len2);
 	cos2=len2;
 	pxs.push_back(cos2*cos1-sin1*sin2+x1);
 	pys.push_back(sin2*cos1+sin1*cos2+y1);
 	pxs.push_back(cos2*cos1+sin1*sin2+x1);
 	pys.push_back(-sin2*cos1+sin1*cos2+y1);
 	//printf("(%lf %lf %lf %lf)",cos2*cos1-sin1*sin2+x1,sin2*cos1+sin1*cos2+y1,
 	//		cos2*cos1+sin1*sin2+x1,-sin2*cos1+sin1*cos2+y1);
 }
 
 void search(int n){
 	double xs[301],ys[301];
 	std::vector<double> pxs,pys;
 	for(int i=0;i<n;i++){
 		scanf("%lf %lf",&xs[i],&ys[i]);
 	}
 	for(int i=0;i<n;i++){
 		for(int j=i+1;j<n;j++){
 			if(hypot(xs[i]-xs[j],ys[i]-ys[j])<=2.0){
 				calc(xs[i],ys[i],xs[j],ys[j],pxs,pys);
 			}
 		}
 	}
 	int ans=1;
 	for(unsigned int i=0;i<pxs.size();i++){
 		int count=0;
 		for(int j=0;j<n;j++){
 			if(hypot(xs[j]-pxs[i],ys[j]-pys[i])<=1.000001)count++;
 		}
 		if(ans<count)ans=count;
 	}
 	printf("%d\n",ans);
 }
 
 int main(){
 	int n;
 	while(1){
 		scanf("%d",&n);
 		if(n==0)break;
 		search(n);
 	}
 }


*1138 Traveling by Stagecoach
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1138
この問題は動的計画法で解きます。
まずチケット８枚、都市数30の場合を考えます。
ある都市にいるときどのチケットを使ってるかを考えます。
そうすると状態数はチケットの使用組み合わせ２５６通り*今いる都市30通り＝7680個の点を持つグラフとなりこのグラフ上を移動する問題に翻訳できます。
このグラフに対して動的計画法を適用すれば解けます。
calc関数で動的計画法を実施します。
スタート地点のタイムは0です。
calc関数の外側のfor文一週目ではチケットを一枚も使ってない点だけを取り上げ動的計画法を適用します。
２週目ではチケットを一枚使った状態の点だけを取り上げ動的計画法を適用します。
３週目では２枚でこれを繰り返します。
最終的にループが終われば計算完了です。
ゴール都市でのタイムを最後のループで調べます。
この手法は泥臭い工夫ですが驚くほど効果があり、実行速度５位という良好な速度を叩き出しましたが僅差で一位を抜くことはできませんでした。
別の手法ですが、高速化の知恵を振りかけたダイクストラで攻略すれば１位を余裕で抜きされる可能性は高いです。




 #include<stdio.h>
 #include<vector>
 #include<bitset>
 double myMax=1000000000;//最大値
 double memoMoveTime[31][31][9];//mMT[都市１][都市２][チケットi]で移動したときにかかる時間
 double nowTime[31][257];//[都市i][チケットの状態s]で到達できた最短タイム
 double tickets[9];//チケットデータ
 int n,m,p,a,b;//チケット数、都市数、道路数、出発地、目的地
 std::vector<int> permMemo[9];//[k枚]チケットを使った場合の組み合わせ
 void calc(){
	int permMax=1<<n;//チケットで作れる組み合わせの総数
	int nextPerm,cHash;
	double nextTime;
	for(int k=0;k<n;k++){
		//今のところk枚チケットを使った
		for(int c1=0;c1<m;c1++){
			//都市ｃ1～スタート
			for(int c2=0;c2<m;c2++){
				//都市ｃ２への移動
				if(memoMoveTime[c1][c2][0]==myMax)continue;//道が通じてなかった
				for(int cNo=0;cNo<n;cNo++){
					//cNo番目のカードを使う
					cHash=1<<(cNo);//cNo番目のカードを使えるか
					for(int u=0;u<permMemo[k].size();u++){
						//チケットの組perm
						int perm=permMemo[k][u];
						if((perm&cHash)!=0)continue;//このカードは使用済みなので次へ
						if(nowTime[c1][perm]==myMax)continue;//この都市へ到達してないので次へ
						nextPerm=perm|cHash;
						nextTime=nowTime[c1][perm]+memoMoveTime[c1][c2][cNo];
						if(nowTime[c2][nextPerm]>nextTime){
							nowTime[c2][nextPerm]=nextTime;
						}
					}
				}
			}
		}
	}
	double ans=myMax;
	for(int p=0;p<permMax;p++){
		ans=ans>nowTime[b][p]?nowTime[b][p]:ans;
	}
	if(ans>=myMax){
		printf("Impossible\n");
	}else{
		printf("%lf\n",ans);
	}
 }
 void setData(){
	//データの初期化を行う
	//チケットデータの読み込み
	for(int i=0;i<n;i++){
		scanf("%lf",&tickets[i]);
	}
	//移動にかかる時間の初期化
	int c1,c2,cNo;
	double time;
	for(c1=0;c1<m;c1++){
		for(c2=0;c2<m;c2++){
			for(cNo=0;cNo<n;cNo++){
				memoMoveTime[c1][c2][cNo]=myMax;
			}
		}
	}
	//移動にかかる時間の設定
	for(int i=0;i<p;i++){
		scanf("%d %d %lf",&c1,&c2,&time);
		c1--;
		c2--;
		for(cNo=0;cNo<n;cNo++){
			memoMoveTime[c1][c2][cNo]=memoMoveTime[c2][c1][cNo]=time/tickets[cNo];
		}
	}
	for(c1=0;c1<m;c1++){
		for(cNo=0;cNo<256;cNo++){
			nowTime[c1][cNo]=myMax;
		}
	}
	nowTime[a][0]=0;
	for(int i=0;i<=n;i++)permMemo[i].clear();
	std::bitset<9> b;
	for(int p=0;p<(1<<n);p++){
		b=p;
		permMemo[b.count()].push_back(p);
	}
 }
 int main(){
	while(1){
		scanf("%d %d %d %d %d",&n,&m,&p,&a,&b);//基礎データ読み込み
		if(n+m+p+a+b==0)break;
		a--;//扱いやすいよう0ベースにする
		b--;
		
		setData();
		calc();
	}
 }