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

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

AOJ541~550 - (2011/11/09 (水) 13:41:57) のソース

----
*0541 Walk
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0541
格子の街並みを東か南に移動しながらマップの外まで散歩し次回の散歩では一度通った交差点を次に通る時は前回東なら次は南、前回南なら次は東とするとき、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
数字の書かれたカードの中から数枚選んでカードを並べるとき何通りの数が出来上がるか答えよという問題です。
 
解法
再起探索で全ての組み合わせを全生成し出来た数字を文字列として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);
	}
 }



----
*0547 Commute routes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0547
升目状の道路で目的地までの通り方が何通りあるか答える問題。

解法
升目が最大10000マスと小さいので気楽に実装します。
縦移動の後は横移動、横移動の後は縦移動という性質を使って縦横に分解してメモ化で計算します。
最後に縦と横の計を集計して終わりです。


 #include<stdio.h>
 #include <algorithm>
 #include<string.h>
 void setData(int w,int h){
	int moveTate[102][102];//縦移動後
	int moveYoko[102][102];//横移動後
	memset(moveTate,0,sizeof(moveTate));
	memset(moveYoko,0,sizeof(moveYoko));
	if(w<h)std::swap(w,h);//コードを短くするため横方向を長くする
	moveYoko[0][0]=moveTate[0][0]=moveYoko[0][1]=moveTate[1][0]=1;
	const int mod=100000;
	for(int i=0;i<h;i++){
		for(int x=i;x<w;x++){
			for(int x2=x+2;x2<w;x2++){
				moveYoko[i][x2]+=moveTate[i][x];
			}
		}
		for(int y=i;y<h;y++){
			for(int y2=y+2;y2<h;y2++){
				moveTate[y2][i]+=moveYoko[y][i];
			}
		}		
		for(int x=i+1;x<w;x++){
			//縦移動
			for(int y=i+2;y<h;y++){
				moveTate[y][x]+=moveYoko[i][x];
				moveTate[y][x]%=mod;
			}
		}
		for(int y=i+1;y<h;y++){
			//横移動
			for(int x=i+2;x<w;x++){
				moveYoko[y][x]+=moveTate[y][i];
				moveYoko[y][x]%=mod;
			}
		}
	}
	int ans=0;
	ans+=moveYoko[h-1][w-1]+moveYoko[h-2][w-1]+moveTate[h-1][w-1]+moveTate[h-1][w-2];
	printf("%d\n",ans%mod);
 }
 int main(){
	int w,h;
	while(1){
		scanf("%d %d",&w,&h);
		if(w==0&& h==0) break;
		setData(w,h);
	}
 }


----
*0548 Reindeer with no sense of direction
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0548
サンタクロースがプレゼントを配っていくルートがいくつあるか答える問題。

解法
逆戻りでプレゼントを配り終わった状態からスタートへ戻ることを考えます。
最初の一手目教会から東西南北一番近い家にプレゼントを回収しなければなりません。
そうしないとその近い家の煙に阻まれて教会にたどり着くことが出来ないからです。
その次の家でも同じ条件となります。
これで計算量は上下左右の家4方向しかないので最悪4^23通り、実際の組み合わせ数はもっと減ります。

しかしこれだけではまだ計算量が少し大きいのでメモ化で計算をまとめます。
過去にプレゼントを回収した家が同じで今いる家が同じになる経路をroots変数で一つにまとめてメモ化して計算します。
これによって計算量を抑えます。
またn件目までまわった場合とその次だけをrootsにメモすることでメモリ消費量を大幅に抑えます。






 #include<stdio.h>
 #include<string.h>
 #include<map>
 struct Move{
	int x,y,houses;
	bool operator<(const Move m)const{
		if(houses!=m.houses) return houses<m.houses;
		if(y!=m.y) return y<m.y;
		return x<m.x;
	}
 };
 //グローバル変数一覧
 int map[11][11];//マップ
 int m,n;
 int houseCount;
 const int dxs[4]={1,0,-1,0};
 const int dys[4]={0,1,0,-1};
 int houseBits[11][11];
 std::map<Move,int> memo;
 int ans;
 //グローバル変数終わり
 int search(Move move,int h,int w){
	std::map<Move,int> roots[2];
	std::map<Move,int>::iterator it;
	int type,now,next,nx,ny,perm;
	Move nextMove;
	roots[0][move]=1;	
	for(int i=0;i<=houseCount;i++){
		type=i==houseCount?2:1;
		now =i%2;//メモ化探索
		next=(i+1)%2;
		roots[next].clear();
		it=roots[now].begin();
		while(it!=roots[now].end()){
			move=(*it).first;
			perm=(*it).second;
			for(int i=0;i<4;i++){
				for(int j=1;j<11;j++){
					nx=move.x+dxs[i]*j;//上下左右の探索
					ny=move.y+dys[i]*j;
					if(nx<0 || w<=nx || ny<0 || h<=ny) break;
					if(type==map[ny][nx] && (move.houses&houseBits[ny][nx])==0){
						nextMove.x=nx;//上下左右がプレゼント未回収の家か教会だったので経路を加算
						nextMove.y=ny;
						nextMove.houses=move.houses|houseBits[ny][nx];
						if(roots[next].find(nextMove)==roots[next].end()){
							roots[next][nextMove]=perm;
						}else{
							roots[next][nextMove]+=perm;//同じルートをまとめる
						}
						break;
					}
				}
			}
			it++;
		}
	}
	return roots[next][nextMove];
 }
 void setData(){
	houseCount=0;
	int sx,sy;
	memset(houseBits,0,sizeof(houseBits));
	memo.clear();	
	for(int y=0;y<n;y++){
		for(int x=0;x<m;x++){
			scanf("%d",&map[y][x]);
			if(map[y][x]==1){
				houseBits[y][x]=1<<houseCount;//intの中で1bitだけで家を表現
				houseCount++;
			}else if(map[y][x]==2){
				sx=x;//教会をスタート位置に
				sy=y;
			}
		}
	}
	Move move;
	move.houses=0;//訪れた家を1bit単位で管理
	move.x=sx;
	move.y=sy;
	ans=0;
	printf("%d\n",search(move,n,m));
 }
 int main(){
	while(1){
		scanf("%d %d",&m,&n);
		if(m==0 && n==0) break;
		setData();
	}
 }





----
*0549 A Traveler
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0549

一本道の街道にある宿場町とその間の距離が与えられる。
宿場から宿場への移動ルートの情報が与えられるので総移動距離を求めよという問題。

解法
宿場Aと宿場Bの距離は宿場1からAまでの距離をA1、宿場1から宿場Bまでの距離をB1とすると
abs(A1B1)となります。
後はこれを順次足すだけです。


 #include<stdio.h>
 #include<stdlib.h>
 #include<vector>
 void setData(int n,int m){
	std::vector<int> points;
	points.push_back(0);
	int len,move,sum=0,now=0;
	for(int i=1;i<n;i++){
		scanf("%d",&len);
		points.push_back(points.back()+len);
	}	
	for(int i=0;i<m;i++){
		scanf("%d",&move);
		sum+=abs(points[now]-points[now+move]);
		sum%=100000;
		now+=move;
	}
	printf("%d\n",sum);
 }
 int main(){
	int n,m;
	while(scanf("%d %d",&n,&m)!=EOF){
		setData(n,m);
	}
 }