「AOJ2000～2010」の編集履歴（バックアップ）一覧はこちら

「AOJ2000～2010」(2013/01/12 (土) 16:30:19) の最新版変更点

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

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

*2000　Misterious Gems
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2000
マス目に散らばった宝石の位置とそれを回収するロボットの命令が与えられるので全部の宝石を集められるか判断せよという問題。
簡単すぎてショートコーディングくらいしかやることがないが私はショートコードがかなり苦手。


 #include<stdio.h>
 #include<string.h>
 void setData(int n){
	bool map[22][22];
	int x,y,ans=0,m,d,r;
	char s[2];
	memset(map,false,sizeof(map));
	for(int i=0;i<n;i++){
		scanf("%d %d",&x ,&y);
		map[y][x]=true;
	}
	scanf("%d",&m);
	char v[4]={'E','N','W','S'};
	int dxs[]={1,0,-1,0};
	int dys[]={0,1,0,-1};
	x=y=10;
	while(m--){
		scanf("%s %d",s,&d);
		for(r=0;r<4;r++)if(s[0]==v[r])break;
		//ここもちょっと綺麗にならないかな。
		ans+=map[y][x];
		map[y][x]=false;
		while(d--){
			ans+=map[y+=dys[r]][x+=dxs[r]];
			map[y][x]=false;
		}
	}
	printf("%s\n",ans==n?"Yes":"No");
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		setData(n);
	}
 }




*2001　Amida, the City of Miracle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2001

あみだくじをシミュレートする問題。
あみだを題材にした問題の中では一番簡単な部類。
何も考えず書いて上の下にランクイン。

 #include<stdio.h>
 #include<algorithm>
 struct bar{
	int h,p,q;
	bool operator<(const bar& b)const{
		return h>b.h;
	}
 };
 void setData(int m,int a){
	bar b,bars[1002];
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&b.h, &b.p, &b.q);
		bars[i]=b;
	}
	std::sort(bars,bars+m);
	for(int i=0;i<m;i++){
		b=bars[i];
		a=a==b.p?b.q:a==b.q?b.p:a;
	}
	printf("%d\n",a);
 }
 int main(){
	int n,m,a;
	while(1){
		scanf("%d %d %d",&n,&m,&a);
		if(a==0)break;
		setData(m,a);
	}
 }




*2002　X-Ray Screening System
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2002
この問題はどうしても解き方がわからなくて他人のコードを参考にしてしまった問題。
非常にシンプルな解法だったので自力で解けなかったのがかなり悔しかった思い出がある。
どんな順番で重なってるかの組み合わせを全て調べて一つでも上手くいくのがあるかどうかを決めて調べていくだけでした。
独自改造
どんな順番で重なってるかをコンピュータに推論させれば探索がいらなくなるかもしれない。
その場合速度は稼げるがコードが膨らむという欠点を持つし意外と上下関係の判定が難しい。





 #include<stdio.h>
 #include<string.h>
 #include <algorithm>
 struct Goods{
	int lx,ty,rx,dy;//左上、右下
	bool spents;//調査済み
	char type;//材質
 };
 char map[52][52];//マップ
 int layered[52][52];//そのセルに材質がいくつ重なっているか
 int maxType;//見つかった材質の種類
 Goods goods[10];//グッズの左上から右下までの座標保持
 bool checkBad;
 void saiki(int deep){
	if(deep==maxType){
		checkBad=false;
	}else{
		for(int i=0;i<maxType;i++){
			Goods g=goods[i];
			if(g.spents==false){
				//未使用だったので長方形の範囲を調べる
				bool ok=true;
				for(int y=g.ty;y<=g.dy;y++){
					for(int x=g.lx;x<=g.rx;x++){
						if(layered[y][x]==0&&g.type!=map[y][x]){
							ok=false;//長方形に足りない部分が見つかった
						}
						layered[y][x]++;
					}
				}
				goods[i].spents=true;
				if(ok==true)saiki(deep+1);//長方形だったので次へ行く
				if(checkBad==false)return;
				goods[i].spents=false;
				for(int y=g.ty;y<=g.dy;y++){
					for(int x=g.lx;x<=g.rx;x++){
						layered[y][x]--;
					}
				}
				
			}
			
		}
	}
 }
 void setData(){
	int h,w;
	int hit[30];//A～Zの文字がヒットしたか
	checkBad=true;
	scanf("%d %d",&h,&w);
	maxType=0;//ヒットした材質の数
	memset(layered,0,sizeof(layered));//重なりの初期化
	memset(hit,-1,sizeof(hit));
	Goods g,*tg;
	g.lx=g.ty=100;
	g.rx=g.dy=-1;
	g.spents=false;
	for(int i=0;i<10;i++){
		goods[i]=g;//ダミーデータを入れておく
	}	
	for(int r=0;r<h;r++){
		scanf("%s",map[r]);
		for(int x=0;x<w;x++){
			char c=map[r][x];
			if(c<'A'||'Z'<c)continue;
			c-='A';
			if(hit[c]==-1){
				hit[c]=maxType;
				goods[hit[c]].type=c+'A';
				maxType++;
			}
			tg=&(goods[hit[c]]);
			(*tg).lx=std::min((*tg).lx,x);
			(*tg).rx=std::max((*tg).rx,x);
			(*tg).ty=std::min((*tg).ty,r);
			(*tg).dy=std::max((*tg).dy,r);
		}
	}
	for(int i=0;i<maxType;i++){
		g=goods[i];
		//printf("%c lx=%d ty=%d rx=%d dy=%d \n",g.type,g.lx,g.ty,g.rx,g.dy);
	}
	saiki(0);
	printf("%s\n",checkBad==false?"SAFE":"SUSPICIOUS");
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n--)setData();
	
 }






*2003　Railroad Conflict
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2003
線路のトンネルを設置していく問題。

解法
幾何の問題なので公式通り線分の交差判定で交差をチェックし交差するなら媒介変数表示の値で交点を並べます。
後は状態遷移マシンに食わせておしまいです。
問題自体は簡単ですが幾何の判定は基本的にめんどくさいのでコードが長くなっています。



 #include<stdio.h>
 #include<queue>
 #include<iostream>
 struct cross{
 	long double t;
 	int type,cType;
 	bool operator<(const cross& c)const{
 		return t>c.t;
 	}
 };
   
 double calcS(double xa,double ya,double xb,double yb,double x1,double y1){
 	return (x1-xa)*(yb-ya)-(xb-xa)*(y1-ya);
 }
 
 int calc(){
 	long double xa,ya,xb,yb,xs1,xs2,ys1,ys2,s1,s2,s3,s4,Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
 	std::priority_queue<cross> qu;
 	std::cin>>xa>>ya>>xb>>yb;
 	cross c,c1;
 	int size;
  	scanf("%d",&size);
 	for(int i=0;i<size;i++){
 		std::cin>>xs1>>ys1>>xs2>>ys2>>c.cType>>c.type;
 		s1=calcS(xa,ya,xb,yb,xs1,ys1);
 		s2=calcS(xa,ya,xb,yb,xs2,ys2);
 		s3=calcS(xs1,ys1,xs2,ys2,xa,ya);
 		s4=calcS(xs1,ys1,xs2,ys2,xb,yb);
 		if(s1*s2<0&&s3*s4<0){
 			Ax=xa;
 			Ay=ya;
 			Bx=xb;
 			By=yb;
 			Cx=xs1;
 			Cy=ys1;
 			Dx=xs2;
 			Dy=ys2;
 			c.t=((Dy-Cy)*(Cx-Ax)-(Dx-Cx)*(Cy-Ay))/((Bx - Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx));
 			qu.push(c);
 		}
 	}
 	if(qu.empty()==true)return 0;
 	c=qu.top();
 	qu.pop();
 	int gType=c.type;
 	if(c.cType==0)gType=!gType;
 	int ans=0;
 	while(qu.empty()==false){
 		c1=qu.top();
 		qu.pop();
 		if(c1.cType==0){
 			if(c1.type==gType){
 				ans++;
 				gType=!gType;
 			}
 		}else{
 			if(c1.type!=gType){
 				ans++;
 				gType=!gType;
 			}
 		}
 	}
 	return ans;
 }
 
 int main(){
 	int n;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++){
 		printf("%d\n",calc());
 	}
 }









*2005　Water Pipe Construction
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2005
火星の基地間を結ぶ水道管を最小コストで敷設する問題。

水が一方通行であることに注意しながらワーシャルフロイド法で全2地点間を結ぶ最短コストを求めます。
後は基地、水道管の分岐点、目的基地までを結ぶ３つの最短経路の計が最小化される道を探すだけです。


 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 void wf(int con[101][101],int n){
	//ワーシャルフロイド法で全基地の最小距離を求める
	int t;
	for(int y=1;y<=n;y++){
		for(int x=1;x<=n;x++){
			if(con[x][y]==-1)continue;
			for(int i=1;i<=n;i++){
				if(con[y][i]==-1)continue;
				t=con[x][y]+con[y][i];
				if(con[x][i]==-1||con[x][i]>t){
					con[x][i]=t;
				}
			}
		}
	}
 }
 bool setData(){
	int n,m,s,g1,g2,con[101][101],b1,b2,c;
	scanf("%d %d %d %d %d",&n,&m,&s,&g1,&g2);
	if(n==0&&m==0&&s==0&&g1==0&&g2==0)return false;
	memset(con,-1,sizeof(con));
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&b1,&b2,&c);
		con[b1][b2]=c;
	}
	for(int i=1;i<=n;i++)con[i][i]=0;
	wf(con,n);
	int ans=2000000000,t;
	for(int i=1;i<=n;i++){
		if(con[i][g1]!=-1&&con[i][g2]!=-1&&con[s][i]!=-1){
			t=con[i][g1]+con[i][g2]+con[s][i];
			ans=std::min(ans,t);
		}
	}
	printf("%d\n",ans);
	return true;
 }
 int main(){
	while(setData());
 }

*2000　Misterious Gems
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2000
マス目に散らばった宝石の位置とそれを回収するロボットの命令が与えられるので全部の宝石を集められるか判断せよという問題。
簡単すぎてショートコーディングくらいしかやることがないが私はショートコードがかなり苦手。


 #include<stdio.h>
 #include<string.h>
 void setData(int n){
	bool map[22][22];
	int x,y,ans=0,m,d,r;
	char s[2];
	memset(map,false,sizeof(map));
	for(int i=0;i<n;i++){
		scanf("%d %d",&x ,&y);
		map[y][x]=true;
	}
	scanf("%d",&m);
	char v[4]={'E','N','W','S'};
	int dxs[]={1,0,-1,0};
	int dys[]={0,1,0,-1};
	x=y=10;
	while(m--){
		scanf("%s %d",s,&d);
		for(r=0;r<4;r++)if(s[0]==v[r])break;
		//ここもちょっと綺麗にならないかな。
		ans+=map[y][x];
		map[y][x]=false;
		while(d--){
			ans+=map[y+=dys[r]][x+=dxs[r]];
			map[y][x]=false;
		}
	}
	printf("%s\n",ans==n?"Yes":"No");
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		setData(n);
	}
 }




*2001　Amida, the City of Miracle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2001

あみだくじをシミュレートする問題。
あみだを題材にした問題の中では一番簡単な部類。
何も考えず書いて上の下にランクイン。

 #include<stdio.h>
 #include<algorithm>
 struct bar{
	int h,p,q;
	bool operator<(const bar& b)const{
		return h>b.h;
	}
 };
 void setData(int m,int a){
	bar b,bars[1002];
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&b.h, &b.p, &b.q);
		bars[i]=b;
	}
	std::sort(bars,bars+m);
	for(int i=0;i<m;i++){
		b=bars[i];
		a=a==b.p?b.q:a==b.q?b.p:a;
	}
	printf("%d\n",a);
 }
 int main(){
	int n,m,a;
	while(1){
		scanf("%d %d %d",&n,&m,&a);
		if(a==0)break;
		setData(m,a);
	}
 }




*2002　X-Ray Screening System
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2002
この問題はどうしても解き方がわからなくて他人のコードを参考にしてしまった問題。
非常にシンプルな解法だったので自力で解けなかったのがかなり悔しかった思い出がある。
どんな順番で重なってるかの組み合わせを全て調べて一つでも上手くいくのがあるかどうかを決めて調べていくだけでした。
独自改造
どんな順番で重なってるかをコンピュータに推論させれば探索がいらなくなるかもしれない。
その場合速度は稼げるがコードが膨らむという欠点を持つし意外と上下関係の判定が難しい。





 #include<stdio.h>
 #include<string.h>
 #include <algorithm>
 struct Goods{
	int lx,ty,rx,dy;//左上、右下
	bool spents;//調査済み
	char type;//材質
 };
 char map[52][52];//マップ
 int layered[52][52];//そのセルに材質がいくつ重なっているか
 int maxType;//見つかった材質の種類
 Goods goods[10];//グッズの左上から右下までの座標保持
 bool checkBad;
 void saiki(int deep){
	if(deep==maxType){
		checkBad=false;
	}else{
		for(int i=0;i<maxType;i++){
			Goods g=goods[i];
			if(g.spents==false){
				//未使用だったので長方形の範囲を調べる
				bool ok=true;
				for(int y=g.ty;y<=g.dy;y++){
					for(int x=g.lx;x<=g.rx;x++){
						if(layered[y][x]==0&&g.type!=map[y][x]){
							ok=false;//長方形に足りない部分が見つかった
						}
						layered[y][x]++;
					}
				}
				goods[i].spents=true;
				if(ok==true)saiki(deep+1);//長方形だったので次へ行く
				if(checkBad==false)return;
				goods[i].spents=false;
				for(int y=g.ty;y<=g.dy;y++){
					for(int x=g.lx;x<=g.rx;x++){
						layered[y][x]--;
					}
				}
				
			}
			
		}
	}
 }
 void setData(){
	int h,w;
	int hit[30];//A～Zの文字がヒットしたか
	checkBad=true;
	scanf("%d %d",&h,&w);
	maxType=0;//ヒットした材質の数
	memset(layered,0,sizeof(layered));//重なりの初期化
	memset(hit,-1,sizeof(hit));
	Goods g,*tg;
	g.lx=g.ty=100;
	g.rx=g.dy=-1;
	g.spents=false;
	for(int i=0;i<10;i++){
		goods[i]=g;//ダミーデータを入れておく
	}	
	for(int r=0;r<h;r++){
		scanf("%s",map[r]);
		for(int x=0;x<w;x++){
			char c=map[r][x];
			if(c<'A'||'Z'<c)continue;
			c-='A';
			if(hit[c]==-1){
				hit[c]=maxType;
				goods[hit[c]].type=c+'A';
				maxType++;
			}
			tg=&(goods[hit[c]]);
			(*tg).lx=std::min((*tg).lx,x);
			(*tg).rx=std::max((*tg).rx,x);
			(*tg).ty=std::min((*tg).ty,r);
			(*tg).dy=std::max((*tg).dy,r);
		}
	}
	for(int i=0;i<maxType;i++){
		g=goods[i];
		//printf("%c lx=%d ty=%d rx=%d dy=%d \n",g.type,g.lx,g.ty,g.rx,g.dy);
	}
	saiki(0);
	printf("%s\n",checkBad==false?"SAFE":"SUSPICIOUS");
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n--)setData();
	
 }






*2003　Railroad Conflict
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2003
線路のトンネルを設置していく問題。

解法
幾何の問題なので公式通り線分の交差判定で交差をチェックし交差するなら媒介変数表示の値で交点を並べます。
後は状態遷移マシンに食わせておしまいです。
問題自体は簡単ですが幾何の判定は基本的にめんどくさいのでコードが長くなっています。



 #include<stdio.h>
 #include<queue>
 #include<iostream>
 struct cross{
 	long double t;
 	int type,cType;
 	bool operator<(const cross& c)const{
 		return t>c.t;
 	}
 };
   
 double calcS(double xa,double ya,double xb,double yb,double x1,double y1){
 	return (x1-xa)*(yb-ya)-(xb-xa)*(y1-ya);
 }
 
 int calc(){
 	long double xa,ya,xb,yb,xs1,xs2,ys1,ys2,s1,s2,s3,s4,Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
 	std::priority_queue<cross> qu;
 	std::cin>>xa>>ya>>xb>>yb;
 	cross c,c1;
 	int size;
  	scanf("%d",&size);
 	for(int i=0;i<size;i++){
 		std::cin>>xs1>>ys1>>xs2>>ys2>>c.cType>>c.type;
 		s1=calcS(xa,ya,xb,yb,xs1,ys1);
 		s2=calcS(xa,ya,xb,yb,xs2,ys2);
 		s3=calcS(xs1,ys1,xs2,ys2,xa,ya);
 		s4=calcS(xs1,ys1,xs2,ys2,xb,yb);
 		if(s1*s2<0&&s3*s4<0){
 			Ax=xa;
 			Ay=ya;
 			Bx=xb;
 			By=yb;
 			Cx=xs1;
 			Cy=ys1;
 			Dx=xs2;
 			Dy=ys2;
 			c.t=((Dy-Cy)*(Cx-Ax)-(Dx-Cx)*(Cy-Ay))/((Bx - Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx));
 			qu.push(c);
 		}
 	}
 	if(qu.empty()==true)return 0;
 	c=qu.top();
 	qu.pop();
 	int gType=c.type;
 	if(c.cType==0)gType=!gType;
 	int ans=0;
 	while(qu.empty()==false){
 		c1=qu.top();
 		qu.pop();
 		if(c1.cType==0){
 			if(c1.type==gType){
 				ans++;
 				gType=!gType;
 			}
 		}else{
 			if(c1.type!=gType){
 				ans++;
 				gType=!gType;
 			}
 		}
 	}
 	return ans;
 }
 
 int main(){
 	int n;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++){
 		printf("%d\n",calc());
 	}
 }









*2005　Water Pipe Construction
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2005
火星の基地間を結ぶ水道管を最小コストで敷設する問題。

水が一方通行であることに注意しながらワーシャルフロイド法で全2地点間を結ぶ最短コストを求めます。
後は基地、水道管の分岐点、目的基地までを結ぶ３つの最短経路の計が最小化される道を探すだけです。


 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 void wf(int con[101][101],int n){
	//ワーシャルフロイド法で全基地の最小距離を求める
	int t;
	for(int y=1;y<=n;y++){
		for(int x=1;x<=n;x++){
			if(con[x][y]==-1)continue;
			for(int i=1;i<=n;i++){
				if(con[y][i]==-1)continue;
				t=con[x][y]+con[y][i];
				if(con[x][i]==-1||con[x][i]>t){
					con[x][i]=t;
				}
			}
		}
	}
 }
 bool setData(){
	int n,m,s,g1,g2,con[101][101],b1,b2,c;
	scanf("%d %d %d %d %d",&n,&m,&s,&g1,&g2);
	if(n==0&&m==0&&s==0&&g1==0&&g2==0)return false;
	memset(con,-1,sizeof(con));
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&b1,&b2,&c);
		con[b1][b2]=c;
	}
	for(int i=1;i<=n;i++)con[i][i]=0;
	wf(con,n);
	int ans=2000000000,t;
	for(int i=1;i<=n;i++){
		if(con[i][g1]!=-1&&con[i][g2]!=-1&&con[s][i]!=-1){
			t=con[i][g1]+con[i][g2]+con[s][i];
			ans=std::min(ans,t);
		}
	}
	printf("%d\n",ans);
	return true;
 }
 int main(){
	while(setData());
 }










*2006　Keitai Message
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2006
入力データから携帯メッセージを復元する問題。

解法
マトリックスを用意して状態遷移マシーンを回すだけです。


 #include<stdio.h>
 void change(){
 	char text[1030];
 	scanf("%s",text);
 	char no='0',c;
 	int count=0;
 	char word[10][7]={"",".,!? ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
 	for(int i=0;text[i]!='\0';i++){
 		c=text[i];
 		if(no!='0'&&c=='0'){
 			printf("%c",word[no-'0'][count]);
 			no=c;
 			count=0;
 		}
 		if(no=='0'&&c=='0'){
 			count=0;
 		}
 		if(no!='0'&&c!='0'){
 			count++;
 			if(word[no-'0'][count]=='\0')count=0;
 		}
 		if(no=='0'&&c!='0'){
 			no=c;
 			count=0;
 		}
 	}
 	printf("\n");
 }
 
 int main(){
 	int n;
 	scanf("%d",&n);
 	while(n--){
 		change();
 	}
 }