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

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

aoj2231~2240 - (2013/02/08 (金) 18:54:17) の1つ前との変更点

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

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

-*2333 My friends are small
-http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2333
-ナップザック問題のうち最大限入れられる組み合わせの数だけ計算する問題。
+*2233 Carrot Tour
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2233
+兎が都市を回って人参をもらってくる問題。
 
 解法
-組み合わせの集合を排他的に分けます。
-おもちゃの重さを小さい順に並べ、後は入れないことに決めた一番最後に入れる一番小さなおもちゃを決めてそれを入れない場合をナップザック問題の手法で計算します。
-入れないことに決めたおもちゃを最後に入れようとしてはいらない組み合わせだけ集計すれば答えが出ます。
-入れないことに決めたおもちゃより軽いおもちゃは全部入れるとすると組み合わせの集合が綺麗に別れるので工夫点はそこだけです。
+兎が前にいた都市今いる都市を点に見立ててグラフとして解きます。
+人参の個数を一つずつインクリメントしながら動的計画法で計算していけば答えが出ます。
+もっと速度が出るかと思ったら意外と速度が出ませんでした。
+
+
 
 
 
  #include<stdio.h>
  #include<vector>
- #include<string.h>
+ #include<queue>
+ #include<map>
+ #include<math.h>
  #include<iostream>
- #include<algorithm>
+ 
+ struct rMove{
+ 	int oldCity,nowCity;
+ 	long double len;
+ };
+ 
  int main(){
- 	long long int ans=0,mod=1000000007;
- 	int n,w,g,sum=0;
- 	std::vector<int> ws;
- 	scanf("%d %d",&n,&w);
+ 	long double xs[21],ys[21];
+ 	int n;
+ 	long double r,theta;
+ 	scanf("%d",&n);
+	if(n==1){
+ 		printf("0\n");
+ 		return 0;
+ 	}
+ 	std::cin>>r>>theta;
+ 	theta=cos(theta/180.0*M_PI);
  	for(int i=0;i<n;i++){
- 		scanf("%d",&g);
- 		ws.push_back(g);
+ 		std::cin>>xs[i]>>ys[i];
  	}
- 	
- 	std::sort(ws.begin(),ws.end());
- 	int m=ws[0];
- 	for(int i=0;i<ws.size();i++){
- 		long long int memo[10002]={0};
- 		if(sum>w)break;
- 		memo[sum]=1;
- 		for(int j=i+1;j<ws.size();j++){
- 			int g=ws[j];
- 			for(int k=w-g;k>=0;k--){
- 				memo[k+g]=(memo[k+g]+memo[k])%mod;
+ 	std::vector<int> moveOKs[21][21];//moveOKs[前いた都市][今いる都市]="次にいける都市のリスト"
+ 	long double dx1,dx2,dy1,dy2;
+ 	for(int i=0;i<n;i++){
+ 		//前の都市
+ 		for(int j=0;j<n;j++){
+ 			//今いる都市
+ 			if(i==j)continue;
+ 			for(int k=0;k<n;k++){
+ 				//次の都市
+ 				if(i==k||j==k)continue;
+ 				dx1=xs[j]-xs[i];
+ 				dy1=ys[j]-ys[i];
+ 				dx2=xs[k]-xs[j];
+ 				dy2=ys[k]-ys[j];
+ 				double cos1=(dx1*dx2+dy1*dy2)/(hypot(dx1,dy1)*hypot(dx2,dy2));
+ 				if(cos1>=theta&&hypot(dx2,dy2)<=r){
+ 					moveOKs[i][j].push_back(k);
+ 				}
  			}
  		}
- 		for(int k=w;k>=0&&k>w-ws[i];k--){
- 			ans=(ans+memo[k])%mod;
+ 	}
+ 	std::queue<rMove> qu;
+  	rMove rm;
+ 	rm.oldCity=0;
+ 	for(int i=1;i<n;i++){
+ 		rm.len=hypot(xs[i]-xs[0],ys[i]-ys[0]);
+ 		rm.nowCity=i;
+ 		if(rm.len<=r){
+ 			qu.push(rm);
  		}
- 		sum+=ws[i];
  	}
- 	if(sum<=w||m>w){
- 		printf("1\n");
- 	}else{
- 		std::cout<<ans<<"\n";
+ 	int ans=0;
+ 	std::map<int,double> getMemo[21];//[前にいた都市][今いる都市]=最短移動距離
+ 	while(qu.empty()==false){
+ 		double len;
+ 		ans++;
+ 		while(qu.empty()==false){
+  			rm=qu.front();
+ 			qu.pop();
+ 			if(rm.len>r)continue;
+ 			for(int i=0;i<moveOKs[rm.oldCity][rm.nowCity].size();i++){
+ 				int no=moveOKs[rm.oldCity][rm.nowCity][i];
+ 				double len=rm.len+hypot(xs[rm.nowCity]-xs[no],ys[rm.nowCity]-ys[no]);
+ 				if(len>r)continue;
+ 				if(getMemo[rm.nowCity].find(no)==getMemo[rm.nowCity].end()||getMemo[rm.nowCity][no]>len){
+ 					getMemo[rm.nowCity][no]=len;
+ 				}
+  			}
+ 		}
+ 		for(int i=0;i<n;i++){
+ 			for(int j=0;j<n;j++){
+ 				if(getMemo[i].find(j)!=getMemo[i].end()){
+ 					rm.oldCity=i;
+ 					rm.nowCity=j;
+ 					rm.len=getMemo[i][j];
+ 					qu.push(rm);
+  				}
+ 			}
+ 		}
+ 		for(int i=0;i<n;i++)getMemo[i].clear();
  	}
+ 	
+ 	printf("%d\n",ans);
  }