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

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

AOJ541~550 - (2011/11/07 (月) 17:09:11) の編集履歴(バックアップ)



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


解法
優先順位付きキューでレベルの低い部屋から優先して訪れある部屋に一番低いレベルで訪れたらその部屋はそのレベルでないと入れない部屋としてレベルを更新します。

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);
}
}