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

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

AOJ1041~1050 - (2012/07/16 (月) 11:52:14) の1つ前との変更点

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

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

 ----
 *1045 Split Up!
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1045
 戦闘力が与えられるので戦闘力の合計が均等になるように2チームにわける問題。
 普通に解くだけなら全探索にちょっと枝刈で簡単に解いたけど、高速化してみた。
 saikiAとsaikiBと半分半分で計算すれば2^20の計算量が2*2^10の計算量に落ちる。
 
 
 
 
  #include<stdio.h>
  #include<set>
  int sum,herf,n,datas[21],t,ans,nHerf;
  std::set<int> herfSum;
  std::set<int>::iterator it;
  void saikiB(int deep,int now){
 	if(deep<n){
 		saikiB(deep+1,now+datas[deep]);
 		saikiB(deep+1,now);
 	}else{
 		if(now<=herf){
 			it=herfSum.upper_bound(herf-now);
 			if((*it)!=0)it--;
 			now+=(*it);
 			t=sum-now*2;
 		}else{
 			t=now*2-sum;
 		}
 		ans=ans>t?t:ans;
 	}
  }
  void saikiA(int deep,int now){
 	if(deep<nHerf){
 		saikiA(deep+1,now+datas[deep]);
 		saikiA(deep+1,now);
 	}else{
 		herfSum.insert(now);
 	}
  }
  int main(){
 	while(scanf("%d",&n)){
 		if(n==0)break;
 		sum=0;
 		ans=2000000000;
 		herfSum.clear();
 		for(int i=0;i<n;i++){
 			scanf("%d",&datas[i]);
 			sum+=datas[i];
 		}
 		herf=sum/2;
 		nHerf=n/2;
 		saikiA(0,0);
 		saikiB(nHerf,0);
 		printf("%d\n",ans);
 	}
  }
 
 
 
 
 
 
 
 
 ----
 *1046 Ghost Buster!
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1046
 升目で区切られたマップ上を一定のルールで移動する幽霊を最短時間で捕まえる問題。
 あるマスで捕まえるとき、そのマスまで最短時間で移動しそのマスに幽霊が来るのを待てばいい。
 この簡単なことに気づくのにやたらと時間のかかった問題。
 考え方さえ分かれば後は場合分けが少しめんどくさいだけの実装ゲーム。
 
 
  #include<stdio.h>
  #include<string.h>
  //               0 1 2 3  4 5 6 7  8
  const int dxs[]={0,0,0,0,-1,0,1,0, 0};
  const int dys[]={0,0,1,0, 0,0,0,0,-1};
  const int max=100000000;
  char map[21][21];
  bool gMoveMemo[21][21];
  int moveMemo[21][21];
  int h,w;
  bool areaOut(int x,int y){
 	if(x<0||x>=w||y<0||y>=h) return true;
 	return false;
  }
  void saiki(int x,int y,int deep){
 	if(areaOut(x,y)||map[y][x]=='#'||moveMemo[y][x]<=deep) return;
 	moveMemo[y][x]=deep;
 	saiki(x+1,y,deep+1);
 	saiki(x-1,y,deep+1);
 	saiki(x,y+1,deep+1);
 	saiki(x,y-1,deep+1);
  }
  void print(){
 	for(int y=0;y<h;y++){
 		for(int x=0;x<w;x++){
 			printf("%2d",moveMemo[y][x]==max?-1:moveMemo[y][x]);
 		}
 		printf("\n");
 	}
  }
  bool setData(){
 	scanf("%d %d",&h,&w);
 	if(h+w==0)return false;	
 	int sx,sy,gx,gy;
 	memset(gMoveMemo,true,sizeof(gMoveMemo));
 	for(int y=0;y<h;y++){
 		scanf("%s",&map[y]);
 		for(int x=0;x<w;x++){
 			moveMemo[y][x]=max;
 			if(map[y][x]=='A'){
 				sx=x;
 				sy=y;
 			}else if(map[y][x]=='B'){
 				gx=x;
 				gy=y;
 			}
 		}
 	}
 	saiki(sx,sy,0);
 	//print();
 	char com[12];
 	scanf("%s",com);
 	int size=strlen(com),count=1,nx,ny,ans=max,ansX,ansY,turn=0;
 	while(count!=0&&ans>turn){
 		count=0;
 		for(int p=0;p<size;p++){
 			nx=dxs[com[p]-'0']+gx;
 			ny=dys[com[p]-'0']+gy;
 			turn++;
 			if(areaOut(nx,ny)==false){
 				gx=nx;
 				gy=ny;
 			}
 			if(moveMemo[gy][gx]<=turn){
 				gMoveMemo[gy][gx]=false;
 				count++;
 				if(ans>turn){
 					ans=turn;
 					ansX=gx;
 					ansY=gy;
 				}
 			}else if(gMoveMemo[gy][gx]==true){
 				count++;
 				gMoveMemo[gy][gx]=false;
 			}else if(moveMemo[gy][gx]!=max){
 				count++;
 			}
 		}
 	}
 	if(ans==max)printf("impossible\n");
 	else printf("%d %d %d\n",ans,ansY,ansX);
 	return true;
  }
  int main(){
 	while(setData()){
 	}
  }
 
 
 
 
 *1047 Crop Circle
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1047
 数学の公式通りに円の交点を求め、円i上の交点を反時計回りにmemo[i]に入れていきます。
 memo[i]の要素AiとAi+1が外部を構成するなら円弧AiAi+1の中点Biも外周に属します。
 Biが外周に属するなら円弧AiAi+1の長さを足していけばこの問題は解けます。
 小数点以下12桁指定でないと丸め誤差で不正回を食らうようなのでその点だけ要注意です。
 
 
  #include<stdio.h>
  #include<math.h>
  #include<set>
  struct circle{
 	double x,y,r,x2,y2,r2;
 	int no;
 	bool bad;//同心円でサイズが小さいことが判明したのは使わない
 	void set(int ino){
 		no=ino;
 		x2=x*x;
 		y2=y*y;
 		r2=r*r;
 		bad=false;
 	}
  };
  void setPoint(circle& c1,circle& c2,std::set<double> memo[101]){
 	if(c1.bad||c2.bad)return;//使わない円が来た
 	if(c1.x==c2.x&&c1.y==c2.y){
 		//計算誤差が怖いので念のため下と処理を分けておく
 		if(c1.r<c2.r)c1.bad=true;
 		else c2.bad=true;
 		return;
 	}
 	double len=sqrt(pow(c1.x-c2.x,2)+pow(c1.y-c2.y,2));
 	if(len<=fabs(c1.r-c2.r)){
 		//円の内側に入っていた
 		if(c1.r>=c2.r)c2.bad=true;
 		else c1.bad=true;
 		return;
 	}
 	if(c1.r+c2.r>len&&len>fabs(c1.r-c2.r)){
 		//交点が二つあることが判明したので
 		double x,y1,y2,cosA,sinA,tempX,tempY,ansR;
 		x=(c1.r2-c2.r2+len*len)/(2.0*len);
 		y1=sqrt(c1.r2-x*x);
 		y2=-y1;
 		//回転する
 		cosA=(c2.x-c1.x)/len;
 		sinA=(c2.y-c1.y)/len;
 		tempX=(cosA*x-sinA*y1);
 		tempY=sinA*x+cosA*y1;
 		//printf("<x=%lf,y=%lf>",tempX+c1.x,tempY+c1.y);
 		tempX=tempX/c1.r;
 		if(tempX>=1.0){
 			ansR=0;
 		}else if(tempX<=-1.0){
 			ansR=M_PI;
 		}else{
 			ansR=tempY<0?2*M_PI-acos(tempX):acos(tempX);
 		}
 		memo[c1.no].insert(ansR);		
 		//二つ目の点を求める
 		tempX=(cosA*x-sinA*y2);
 		tempY=sinA*x+cosA*y2;
 		//printf("<x=%lf,y=%lf>\n",tempX+c1.x,tempY+c1.y);
 		tempX=tempX/c1.r;
 		//printf("(%lf)\n",tempX);
 		if(tempX>=1.0){
 			ansR=0;
 		}else if(tempX<=-1.0){
 			ansR=M_PI;
 		}else{
 			ansR=tempY<0?2*M_PI-acos(tempX):acos(tempX);
 		}
 		memo[c1.no].insert(ansR);
 	}
  }
  void setData(int n){
 	circle c,cs[101],c2;
 	for(int i=0;i<n;i++){
 		scanf("%lf %lf %lf",&c.x,&c.y,&c.r);
 		c.set(i);
 		cs[i]=c;
 	}
 	std::set<double> memo[101];//交点のメモ、各円に対して時計回りで記憶する
 	for(int i=0;i<n;i++){
 		memo[i].insert(0);//この円は交点を持つので
 		memo[i].insert(2*M_PI);//番兵
 		for(int j=0;j<n;j++){
 			if(i==j)continue;
 			setPoint(cs[i],cs[j],memo);
 		}
 	}	
 	double ans=0;
 	std::set<double>::iterator it,nIt;
 	for(int i=0;i<n;i++){
 		if(cs[i].bad==true)continue;//別の円の内側に入っていた
 		//円を反時計回りに切り分けてその範囲が他の円に入るかを調べる
 		it=memo[i].begin();
 		nIt=it;
 		nIt++;
 		c=cs[i];
 		double r1,r2,r3,x1,y1,len1;
 		for(;nIt!=memo[i].end();it++,nIt++){
 			r1=(*it);
 			r2=(*nIt);
 			r3=(r1+r2)/2.0;
 			x1=c.r*cos(r3)+c.x;//切り分けた真中の点を求める
 			y1=c.r*sin(r3)+c.y;
 			bool bad=false;
 			for(int j=0;j<n;j++){
 				if(i==j)continue;
 				if(cs[j].bad==true)continue;
 				c2=cs[j];
 				len1=(x1-c2.x)*(x1-c2.x)+(y1-c2.y)*(y1-c2.y);
 				if(len1<c2.r2){
 					bad=true;
 					break;
 				}
 			}
 			if(bad==false){
 				ans+=c.r*(r2-r1);
 			}
 		}
 		
 	}
 	printf("%.12lf\n",ans);
  }
  int main(){
 	int n;
 	while(1){
 		scanf("%d",&n);
 		if(n==0)break;
 		setData(n);
+	}
+ }
+
+
+
+
+
+
+*1049 Building Houses
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1049
+仲の悪い住人の家を上手に間をあけて配置した時の最小距離を求める問題。
+
+深さ優先による全探索と枝刈を組み合わせただけのシンプルコードで通るようです。
+一応コード実行速度3位を取ったコードだが一位との差は大きい。
+一位がどんな魔法を使ったのか気になるところ。
+メモ化による枝刈をもっと高度化したというところかな?
+
+
+ #include<stdio.h>
+ #include<string.h>
+ #include<algorithm>
+ int ans,lens[11],data[11][11];
+ bool spents[11];
+ int n;
+ void saiki(int deep,int l){
+	if(deep==n){
+		if(ans==-1)ans=l;
+		ans=std::min(ans,l);
+	}else{
+		int back[11];
+		bool out=false;
+		memcpy(back,lens,sizeof(lens));
+		for(int i=0;i<n;i++){
+			if(spents[i]==false){
+				spents[i]=true;
+				int len=lens[i];
+				for(int j=0;j<n;j++){
+					if(spents[j]==false)lens[j]=std::max(len+data[i][j],lens[j]);
+					if(ans>-1&&ans<=lens[j]&&spents[j]==false)out=true;
+				}
+				if(out==false)saiki(deep+1,len);
+				out=false;
+				memcpy(lens,back,sizeof(back));
+				spents[i]=false;
+			}
+		}
+	}
+ }
+ void setData(){	
+	ans=-1;
+	memset(data,0,sizeof(data));
+	for(int i=0;i<n;i++){
+		spents[i]=false;
+		lens[i]=0;
+		for(int j=0;j<n;j++){
+			scanf("%d",&data[i][j]);
+			data[i][j]=data[j][i]=std::max(data[i][j],data[j][i]);
+		}
+	}
+	saiki(0,0);
+	printf("%d\n",ans);
+ }
+ int main(){
+	while(1){
+		scanf("%d",&n);
+		if(n==0)break;
+		setData();
 	}
  }