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

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

AOJ541~550 - (2011/11/08 (火) 09:28:11) の1つ前との変更点

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

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

 ----
 *0541 Walk
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0541
-一定のルールで移動経路を一定のルールで変化させながら何度も道を散歩するとき、n回目の散歩がどの地点に到達するかを答える問題。
+格子の街並みを東か南に移動しながらマップの外まで散歩し一度通った交差点を次に通る時は東なら次は南、南なら次は東とするとき、n回目の散歩がどの地点に到達するかを答える問題。
 
 
 解法
 この問題はある地点を何回通るかということが重要となります。
 スタート地点で考えてみましょう。
 スタートが東で通る回数が1回のとき、2回のとき、、、n回のときと考えると。
 nが奇数回目のときは必ず東に向かい、nが偶数回目のときは必ず南に向かいます。
 この条件が全ての交差点で成り立ちます。
 つまり、どの交差点も何回訪れたかで南か東かが決まります。
 これを利用してn-1回目までの散歩を道路にまとめて流すと下記のようなコードとなります。
 n-1回目までの結果、東南がどう変わったかを利用して最後のwhileが実行されます。
 
 
 
 
  #include<stdio.h>
  #include<string.h>
  int map[1002][1002];
  int memo[1002][1002];
  int h,w,n;
  void setData(){
 	int x,y,t;
 	for(y=0;y<h;y++){
 		for(x=0;x<w;x++){
 			scanf("%d",&map[y][x]);
 		}
 	}
 	memset(memo,0,sizeof(memo));
 	memo[0][0]=n-1;
 	for(int y=0;y<h;y++){
 		for(int x=0;x<w;x++){
 			t=memo[y][x];
 			if(map[y][x]==0){
 				if(t%2==0){
 					memo[y+1][x]+=t/2;
 					memo[y][x+1]+=t/2;
 				}else{
 					map[y][x]=1;
 					memo[y+1][x]+=t/2+1;
 					memo[y][x+1]+=t/2;
 				}
 			}else{
 				if(t%2==0){
 					memo[y+1][x]+=t/2;
 					memo[y][x+1]+=t/2;
 				}else{
 					map[y][x]=0;
 					memo[y+1][x]+=t/2;
 					memo[y][x+1]+=t/2+1;
 				}
 			}
 		}
 	}
 	y=x=0;
 	while(y<h && x<w){
 		if(map[y][x]==0)y++;
 		else 		x++;
 	}
 	printf("%d %d\n",y+1,x+1);
  }
  int main(){
 	while(1){
 		scanf("%d %d %d",&h,&w,&n);
 		if(h==0 && w==0 && n==0) break;
 		setData();
 	}
  }
 
 
 
 ----
 *0542 Authentication Level
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0542
-部屋をつなぐドアに保安レベルが設定されておりレベル以上の認証レベルを持ってないとその部屋を訪れることが出来ない。
+格子状に連なった部屋をつなぐドアに保安レベルが設定されておりレベル以上の認証レベルを持ってないとその部屋を訪れることが出来ない。
 ある一定数以上の部屋を訪れることのできる認証レベルを求める問題。
 
 
 解法
 優先順位付きキューでレベルの低い部屋から優先して訪れある部屋に一番低いレベルで訪れたらその部屋はそのレベルでないと入れない部屋としてレベルを更新します。
 
 Lv3の部屋に行く途中でどのような経路を通っても途中にLv10の部屋を挟まないといけないなら、Lv3の部屋はLv10でないと入れない部屋に更新するわけです。
 そして全ての部屋を訪れた後更新されたレベルでそのレベルで訪れれる部屋数をカウントします。
 最後に必要なレベルを算出するために訪れれる部屋数をキーにレベルを値にしてMapに入れなおして最後のループで答えを求めます。
 
 素直な実装をしてみたところランキングではメモリ多消費の割には平凡なコード実行速度になりました。
 もう少し良いコードがあるようです。
 
 
 
  #include<stdio.h>
  #include<queue>
  #include<map>
  #include<string.h>
  struct room{
 	int x,y,level;
 	bool operator<(const room r)const{
 		return level>r.level;
 	}
 	void set(int ix,int iy,int ilevel){
 		x=	ix;
 		y=	iy;
 		level=	ilevel;
 	}
  };
  const int roomSize=501;
  int dxs[4]={0,1,0,-1};
  int dys[4]={1,0,-1,0};
  void search(int sx,int sy,int w,int h,int level[roomSize][roomSize],std::map<int,int>& ans){
 	std::priority_queue<room> qu;
 	room r,nextR;
 	int nx,ny,nLevel;
 	r.set(sx,sy,level[sy][sx]);
 	qu.push(r);
 	ans.clear();
 	ans[0]=0;
 	ans[1]=1;
 	bool moveOKs[roomSize][roomSize];
 	memset(moveOKs,true,sizeof(moveOKs));
 	moveOKs[sy][sx]=false;
 	while(!qu.empty()){
 		r=qu.top();
 		qu.pop();
 		for(int i=0;i<4;i++){
 			nx=r.x+dxs[i];
 			ny=r.y+dys[i];
 			nLevel=r.level;
 			if(nx<0 || nx>=w || ny<0 || ny>=h) continue;
 			if(moveOKs[ny][nx]==false) continue;
 			moveOKs[ny][nx]=false;			
 			if(level[ny][nx]>nLevel)nLevel=level[ny][nx];
 			level[ny][nx]=nLevel;
 			nextR.set(nx,ny,nLevel);
 			if(ans.find(nLevel)==ans.end()){
 				ans[nLevel]=1;
 			}else{
 				ans[nLevel]++;
 			}
 			qu.push(nextR);
 		}
 	}
  }
  void print(int level[roomSize][roomSize],int h,int w){
 	printf("\n\n");
 	for(int y=0;y<h;y++){
 		for(int x=0;x<w;x++){
 			printf("%d ",level[y][x]);
 		}
 		printf("\n");
 	}
 	printf("\n\n");
  }
  int level[2][roomSize][roomSize];
  void setData(int r){	
 	int w,h,sx,sy;
 	std::map<int,int> levelCounts[2];
 	for(int i=0;i<2;i++){
 		scanf("%d %d %d %d",&w,&h,&sx,&sy);
 		sx--;
 		sy--;
 		for(int y=0;y<h;y++){
 			for(int x=0;x<w;x++){
 				scanf("%d",&level[i][y][x]);
 			}
 		}
 		//print(level[i],h,w);
 		search(sx,sy,w,h,level[i],levelCounts[i]);
 		//print(level[i],h,w);
 	}	
 	std::map<int,int> roomCounts[2];
 	std::map<int,int>::iterator it,it2;
 	int back;
 	for(int i=0;i<2;i++){
 		it=levelCounts[i].begin();
 		back=0;
 		while(it!=levelCounts[i].end()){
 			back+=(*it).second;
 			roomCounts[i][back]=(*it).first;
 			it++;
 		}
 	}
 	it=roomCounts[0].begin();
 	int temp,sumLevel,sumRoom,ans=1000000000;
 	while(it!=roomCounts[0].end()){
 		temp=r-(*it).first;
 		it2=roomCounts[1].lower_bound(temp);
 		sumRoom=(*it).first+(*it2).first;
 		if(sumRoom<r){
 			it++;
 			continue;
 		}
 		sumLevel=(*it).second+(*it2).second;
 		ans=ans>sumLevel?sumLevel:ans;
 		it++;
 	}
 	printf("%d\n",ans);
  }
  int main(){
 	int r;
 	while(1){
 		scanf("%d",&r);
 		if(r==0) break;
 		setData(r);
 	}
  }
 
 
 
 ----
 *0543 Receipt
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0543
 レシートのデータで一つだけ金額がかすれているので残りの金額からかすれた部分の値段を求める問題。
 
 
 解法
 中学生にでも出題しそうな簡単な問題なので計算するだけです。 
 
  #include<stdio.h>
  int main(){
 	int sum,all,i,t;
 	while(1){
 		scanf("%d",&all);
 		if(all==0) break;
 		i=9,sum=0;
 		while(i--){
 			scanf("%d",&t);
 			sum+=t;
 		}
 		printf("%d\n",all-sum);
 	}
  }
 
 
 
 ----
 *0544 Sugoroku
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0544
 すごろくの升目データとさいころの情報が与えられるので何手目でゴールできるかを答える問題。
 
 解法
 サイを振った後、升目の進む戻るで
 ゴールを超えた升目を参照しないように注意さえすれば簡単な問題です。
 コードをきれいにまとめられませんでした。
 
  #include<stdio.h>
  void setData(int n,int m){
 	int map[1002];
 	for(int i=1;i<=n;i++){
 		scanf("%d",&map[i]);
 	}
 	int xai,nowP=1,ans;
 	bool goal=false;
 	for(int i=1;i<=m;i++){
 		scanf("%d",&xai);
 		if(goal==true) continue;
 		nowP+=xai;
 		if(n<=nowP){
 			ans=i;
 			goal=true;
 			continue;
 		}
 		nowP+=map[nowP];
 		if(n<=nowP){
 			ans=i;
 			goal=true;
 		}
 	}
 	printf("%d\n",ans);
 	
  }
  int main(){
 	int n,m;
 	while(1){
 		scanf("%d %d",&n,&m);
 		if(n==0 && m==0) break;
 		setData(n,m);
 	}
  }
 
 
 
 
 ----
 *0545 Party
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0545
 誰と誰が友達かの情報から、友達の友達が何人いるか答える問題です。
 
 解法
 友達の友達が実は単なる友達で探索が続く場合にさえ注意すれば再起探索で間に合う問題です。
 素直に再起で実装しました。
 
 
 
  #include<stdio.h>
  #include<string.h>
  //簡単な問題なのでグローバル変数で手抜き
  const int max=502;
  bool con[max][max],moveOKs[max];
  int ans,n,m;
  void search(int deep,int no){
 	//友達の友達が実は友達だった場合探索が続くので注意
 	for(int i=2;i<=n;i++){
 		if(con[no][i]){
 			if(moveOKs[i]==true)ans++;
 			moveOKs[i]=false;
 			if(deep==0)search(deep+1,i);
 		}
 	}
  }
  void setData(){
 	memset(con,    false, sizeof(con));
 	memset(moveOKs,true , sizeof(moveOKs));
 	moveOKs[1]=false;
 	ans=0;
 	int a,b;
 	for(int i=0;i<m;i++){
 		scanf("%d %d",&a,&b);
 		con[a][b]=con[b][a]=true;
 	}	
 	search(0,1);
 	printf("%d\n",ans);
  }
  int main(){
 	while(1){
 		scanf("%d %d",&n,&m);
 		if(n==0 && m==0) break;
 		setData();
 	}
  }
 
 
 
 
 ----
 *0546 Lining up the cards
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0546
-10枚までの数字の書かれたカードの中から数枚選んでカードを並べるとき何通りの数が出来上がるか答えよという問題です。
+数字の書かれたカードの中から数枚選んでカードを並べるとき何通りの数が出来上がるか答えよという問題です。
  
 解法
 再起探索で全ての組み合わせを全生成し出来た数字を文字列としてstd::set<std::string> allに入れて重複を削除します。
 後はall.sizeで答えが出ます。
 グローバル変数を使わずに解いてみました。
 実務ならグローバル変数はクラス内に隠されますし変数の受け渡し部分が煩わしくなるのであまり意味のないコードになりました。
 素直にグローバル変数を使ったほうがよいという例です。
 
 
  #include <iostream> 
  #include<string>
  #include<set>
  #include<vector>
  #include<string.h>
  void saiki(	int deep,  std::string s,std::vector<std::string>& nums,
 		bool moveOKs[11],  std::set<std::string>& all,  int k,  int n){
 	if(k<=deep){
 		//std::cout<<s<<"\n";
 		all.insert(s);
 	}else{
 		for(int i=0;i<n;i++){
 			if(moveOKs[i]==true){
 				moveOKs[i]=false;
 				saiki(deep+1,s+nums[i],nums,moveOKs,all,k,n);
 				moveOKs[i]=true;
 			}
 		}
 	}
  }
  void setData(int n,int k){
 	std::set<std::string> all;
 	std::vector<std::string> nums;
 	std::string num;
 	bool moveOKs[11];
 	memset(moveOKs,true,11);
 	for(int i=0;i<n;i++){
 		std::cin>>num;
 		nums.push_back(num);
 	}
 	saiki(0,"",nums,moveOKs,all,k,n);
 	std::cout<<all.size()<<"\n";
  }
  int main(){
 	int n,k;
 	while(1){
 		std::cin>>n>>k;
 		if(n==0 && k==0) break;
 		setData(n,k);
 	}
  }