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

AOJ551～560 - (2011/11/09 (水) 08:49:13) の１つ前との変更点

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

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

----
*0551　Icicles
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0551
軒下に連なったつららがいつ全て折れるかを計算する問題です。
つららは隣のつららより長いつららのみ成長し、一定の長さになると折れます。

解法
この問題は あるつららが伸び始めるタイムが隣の先に延び始めたつららが折れるまで伸びないという点に注目点があります。
つまりあるつららが折れる時間は　隣のつららが折れた時間+L-初めの長さ。
という親子関係が全てのつららで成り立ちます。
これが判明すれば後はつららの折れるタイムを優先順位付きキューに入れれば実装は簡単です。
この発想法は実装の簡単さを優先しましたが、メモリを多めに使ってしまいます。
工夫すればメモリを節約できるようなので他の方のコードを参考にすることをお勧めします。



 #include<stdio.h>
 #include<queue>
 struct turara{
	int len,point,time;
	bool spent,grown;
	bool operator<(const turara t)const{
		return t.time<time;
	}
 };
 const int mymax=100001;
 turara map[mymax];
 bool addOK(int p,int n,turara map[mymax]){
	if(p<0 || n<=p) return false;//ｐ番目のつららが伸びることが出来るかのチェック
	if(map[p].spent==true || map[p].grown==true)return false;//伸びてる途中でないか折れ済ではないかチェック
	if(p>0){
		if(map[p-1].spent==false && map[p-1].len>=map[p].len){
			return false;//隣より短いならノー
		}
	}
	if(p<n-1){
		if(map[p+1].spent==false && map[p+1].len>=map[p].len){
			return false;
		}
	}
	return true;//隣より長いことが判明伸ばすことを決定
 }
 void setData(int n,int L){
	std::priority_queue<turara> turaras;
	turara t,nt;
	
	t.spent=false;
	t.grown=false;
	t.time=0;
	for(int i=0;i<n;i++){
		scanf("%d",&t.len);
		t.point=i;
		map[i]=t;
	}
	for(int i=0;i<n;i++){
		if(addOK(i,n,map)){
			map[i].grown=true;
			t=map[i]; 
			t.time=L-t.len;//次に折れるタイミング
			turaras.push(t);
		}
	}
	int p;
	while(!turaras.empty()){
		t=turaras.top();//ｔのつららが折れた
		turaras.pop();
		p=t.point;
		map[p].spent=true;//ｔを親に左右のつららが伸びることが出来るかチェック
		if(addOK(p-1,n,map)){
			map[p-1].grown=true;
			nt=map[p-1];
			nt.time=L-nt.len+t.time;
			turaras.push(nt);
		}
		if(addOK(p+1,n,map)){
			map[p+1].grown=true;
			nt=map[p+1];
			nt.time=L-nt.len+t.time;
			turaras.push(nt);
		}
	}
	printf("%d\n",t.time);
 }
 int main(){
	int n,L;
	while(scanf("%d %d",&n,&L)!=EOF){
		setData(n,L);
	}
 }




----
*0554 Total Time
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0554
移動時間の合計を算出せよという問題。

解法
計算するだけです。

 #include<stdio.h>
 int main(){
	int a,b,c,d,t;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	t=a+b+c+d;
	printf("%d\n%d\n",t/60,t%60);
 }


----
*0555　Ring
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0555
リングに刻まれた文字列のなかから特定の文字列を探すという問題。

解法
std::stringの基本機能を使いこなせるかだけの問題で計算量も小さいので気楽に解きます。

 #include<iostream>
 #include<string>
 int main(){
	std::string text,ring;
	int n,count=0;
	std::cin>>text>>n;
	for(int i=0;i<n;i++){
		std::cin>>ring;
		ring+=ring;
		if(std::string::npos!=ring.find(text,0))count++;
	}
	std::cout<<count<<"\n";
 }


----
*0556　Tile
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0556
規則的なタイル模様のうち欠けた部分の座標から補修に必要なタイルの色を求める問題。
解法
盤面の対称性を利用して１～2回折りたたんで計算します。
折りたたむと、盤面が非常に簡単になります。



 #include<stdio.h>
 int main(){
	int n,m,herf,x,y;
	scanf("%d %d",&n,&m);
	herf=(n+1)/2;	
	for(int i=0;i<m;i++){
		scanf("%d %d",&x,&y);
		if(x>herf)x=n-x+1;
		if(y>herf)y=n-y+1;//盤面を1/4か1/2に折りたたむ
		if(x>=y){
			printf("%d\n",(y-1)%3+1);
		}else{
			printf("%d\n",(x-1)%3+1);
		}
	}
 }



----
*0557　A First Grader
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557
算数を題材にしたメモ化計算の問題。

解法
典型的なメモ化計算の問題ですので簡単にサクッと実装します。


 #include<stdio.h>
 #include<string.h>
 int main(){
	int nums[101],n,t;
	unsigned long long int memo[21];
	unsigned long long int next[21];
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&nums[i]);
	memset(memo,0,sizeof(memo));
	memo[nums[0]]=1;
	for(int i=1;i<n-1;i++){
		memset(next,0,sizeof(next));
		for(int j=0;j<21;j++){
			t=j+nums[i];
			if(t<21){
				next[t]+=memo[j];
			}
			t=j-nums[i];
			if(-1<t){
				next[t]+=memo[j];
			}
		}
		memcpy(memo,next,sizeof(next));
	}
	printf("%llu\n",memo[nums[n-1]]); 
 }


----
*0558
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558
升目になっているマップの上でネズミがチーズを求めて移動する。
チーズは硬さが決まっており、やわらかいチーズを先に食べて体力をつけないと硬いチーズは食べられない。
全てのチーズを食べることのできる最短ルートの距離を求めよという問題です。

解法
この問題は気持高速に動作するコードときれいなコードどちらを掲載するか迷いました。
ほとんど速度差がないので綺麗なほうを掲載することにしました。
問題の本質はスタートからチーズ、チーズからチーズへのルートの探索だけです。
幅優先探索でチーズからチーズへの移動距離を求めます。

綺麗に直したほうを掲載する前、公開されているジャッジデータでコードを試したのですが、BCCでは実行時エラー(おそらくqueueのオーバーかコマンドプロンプトの入力限界)がおきGCCではエラーが起きなかったのが下記コードです。

そのうちBCCでも動くように変更しようと考えています。



 #include<stdio.h>
 #include<queue>
 #include<string.h>
 struct point{
	int x,y,len;
	bool operator<(const point p)const{
		return p.len<len;
	}
 };
 //グローバル変数はすべてここに
 int turn[1001][1001];
 char map[1001][1001];
 int dxs[4]={1,0,-1,0};
 int dys[4]={0,1,0,-1};
 //グローバル変数終わり
 int search(point p1,point p2,int h,int w){
	int gx=p2.x;
	int gy=p2.y;
	std::priority_queue<point> points;
	points.push(p1);
	int nx,ny,nt;
	turn[p1.y][p1.x]=1;//スタート地点だけダミーデータ	
	while(!points.empty()){
		p1=points.top();//幅優先探索、経路は水量の上がる水溜りのように外郭だけとなるのでqueueに入るデータ量は少なめ
		points.pop();
		for(int i=0;i<4;i++){
			nx=p1.x+dxs[i];
			ny=p1.y+dys[i];
			nt=p1.len+1;//縦横チェック
			if(nx<0 || w<=nx || ny<0 || h<=ny) continue;
			if(map[ny][nx]=='X' || (turn[ny][nx]!=0 && nt>=turn[ny][nx])) continue;
			if(nx==gx && ny==gy)return nt;
			turn[ny][nx]=nt;
			p2.x=nx;
			p2.y=ny;
			p2.len=nt;
			points.push(p2);
		}
	}
	return 0;
 }
 int main(){
	int h,w,n;
	int sx,sy;
	char t;
	point points[10];
	scanf("%d %d %d",&h,&w,&n);
	for(int y=0;y<h;y++){
		scanf("%s",map[y]);
		for(int x=0;x<w;x++){
			t=map[y][x];
			if(t=='S'){
				points[0].x=x;//スタート座標
				points[0].y=y;
				points[0].len=0;
			}else if('1'<=t && t<='9'){
				points[t-'0'].x=x;//チーズ座標
				points[t-'0'].y=y;
				points[t-'0'].len=0;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		memset(turn,0,sizeof(turn));
		ans+=search(points[i-1],points[i],h,w);//スタートからチーズへチーズからチーズへの経路を検索
	}
	printf("%d\n",ans);
 }

----
*0551　Icicles
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0551
軒下に連なったつららがいつ全て折れるかを計算する問題です。
つららは隣のつららより長いつららのみ成長し、一定の長さになると折れます。

解法
この問題は あるつららが伸び始めるタイムが隣の先に延び始めたつららが折れるまで伸びないという点に注目点があります。
つまりあるつららが折れる時間は　隣のつららが折れた時間+L-初めの長さ。
という親子関係が全てのつららで成り立ちます。
これが判明すれば後はつららの折れるタイムを優先順位付きキューに入れれば実装は簡単です。
この発想法は実装の簡単さを優先しましたが、メモリを多めに使ってしまいます。
工夫すればメモリを節約できるようなので他の方のコードを参考にすることをお勧めします。



 #include<stdio.h>
 #include<queue>
 struct turara{
	int len,point,time;
	bool spent,grown;
	bool operator<(const turara t)const{
		return t.time<time;
	}
 };
 const int mymax=100001;
 turara map[mymax];
 bool addOK(int p,int n,turara map[mymax]){
	if(p<0 || n<=p) return false;//ｐ番目のつららが伸びることが出来るかのチェック
	if(map[p].spent==true || map[p].grown==true)return false;//伸びてる途中でないか折れ済ではないかチェック
	if(p>0){
		if(map[p-1].spent==false && map[p-1].len>=map[p].len){
			return false;//隣より短いならノー
		}
	}
	if(p<n-1){
		if(map[p+1].spent==false && map[p+1].len>=map[p].len){
			return false;
		}
	}
	return true;//隣より長いことが判明伸ばすことを決定
 }
 void setData(int n,int L){
	std::priority_queue<turara> turaras;
	turara t,nt;
	
	t.spent=false;
	t.grown=false;
	t.time=0;
	for(int i=0;i<n;i++){
		scanf("%d",&t.len);
		t.point=i;
		map[i]=t;
	}
	for(int i=0;i<n;i++){
		if(addOK(i,n,map)){
			map[i].grown=true;
			t=map[i]; 
			t.time=L-t.len;//次に折れるタイミング
			turaras.push(t);
		}
	}
	int p;
	while(!turaras.empty()){
		t=turaras.top();//ｔのつららが折れた
		turaras.pop();
		p=t.point;
		map[p].spent=true;//ｔを親に左右のつららが伸びることが出来るかチェック
		if(addOK(p-1,n,map)){
			map[p-1].grown=true;
			nt=map[p-1];
			nt.time=L-nt.len+t.time;
			turaras.push(nt);
		}
		if(addOK(p+1,n,map)){
			map[p+1].grown=true;
			nt=map[p+1];
			nt.time=L-nt.len+t.time;
			turaras.push(nt);
		}
	}
	printf("%d\n",t.time);
 }
 int main(){
	int n,L;
	while(scanf("%d %d",&n,&L)!=EOF){
		setData(n,L);
	}
 }




----
*0554 Total Time
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0554
移動時間の合計を算出せよという問題。

解法
計算するだけです。

 #include<stdio.h>
 int main(){
	int a,b,c,d,t;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	t=a+b+c+d;
	printf("%d\n%d\n",t/60,t%60);
 }


----
*0555　Ring
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0555
リングに刻まれた文字列のなかから特定の文字列を探すという問題。

解法
std::stringの基本機能を使いこなせるかだけの問題で計算量も小さいので気楽に解きます。

 #include<iostream>
 #include<string>
 int main(){
	std::string text,ring;
	int n,count=0;
	std::cin>>text>>n;
	for(int i=0;i<n;i++){
		std::cin>>ring;
		ring+=ring;
		if(std::string::npos!=ring.find(text,0))count++;
	}
	std::cout<<count<<"\n";
 }


----
*0556　Tile
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0556
規則的なタイル模様のうち欠けた部分の座標から補修に必要なタイルの色を求める問題。
解法
盤面の対称性を利用して１～2回折りたたんで計算します。
折りたたむと、盤面が非常に簡単になります。



 #include<stdio.h>
 int main(){
	int n,m,herf,x,y;
	scanf("%d %d",&n,&m);
	herf=(n+1)/2;	
	for(int i=0;i<m;i++){
		scanf("%d %d",&x,&y);
		if(x>herf)x=n-x+1;
		if(y>herf)y=n-y+1;//盤面を1/4か1/2に折りたたむ
		if(x>=y){
			printf("%d\n",(y-1)%3+1);
		}else{
			printf("%d\n",(x-1)%3+1);
		}
	}
 }



----
*0557　A First Grader
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557
算数を題材にしたメモ化計算の問題。

解法
典型的なメモ化計算の問題ですので簡単にサクッと実装します。


 #include<stdio.h>
 #include<string.h>
 int main(){
	int nums[101],n,t;
	unsigned long long int memo[21];
	unsigned long long int next[21];
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&nums[i]);
	memset(memo,0,sizeof(memo));
	memo[nums[0]]=1;
	for(int i=1;i<n-1;i++){
		memset(next,0,sizeof(next));
		for(int j=0;j<21;j++){
			t=j+nums[i];
			if(t<21){
				next[t]+=memo[j];
			}
			t=j-nums[i];
			if(-1<t){
				next[t]+=memo[j];
			}
		}
		memcpy(memo,next,sizeof(next));
	}
	printf("%llu\n",memo[nums[n-1]]); 
 }


----
*0558
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558
升目になっているマップの上でネズミがチーズを求めて移動する。
チーズは硬さが決まっており、やわらかいチーズを先に食べて体力をつけないと硬いチーズは食べられない。
全てのチーズを食べることのできる最短ルートの距離を求めよという問題です。

解法
この問題は気持高速に動作するコードときれいなコードどちらを掲載するか迷いました。
ほとんど速度差がないので綺麗なほうを掲載することにしました。
問題の本質はスタートからチーズ、チーズからチーズへのルートの探索だけです。
幅優先探索でチーズからチーズへの移動距離を求めます。



 #include<stdio.h>
 #include<queue>
 #include<string.h>
 struct point{
	int x,y,len;
	bool operator<(const point p)const{
		return p.len<len;
	}
 };
 //グローバル変数はすべてここに
 int turn[1001][1002];
 char map[1001][1002];
 int dxs[4]={1,0,-1,0};
 int dys[4]={0,1,0,-1};
 //グローバル変数終わり
 int search(point p1,point p2,int h,int w){
	int gx=p2.x;
	int gy=p2.y;
	std::priority_queue<point> points;
	points.push(p1);
	int nx,ny,nt;
	turn[p1.y][p1.x]=1;//スタート地点だけダミーデータ	
	while(!points.empty()){
		p1=points.top();//幅優先探索、経路は水量の上がる水溜りのように外郭だけとなるのでqueueに入るデータ量は少なめ
		points.pop();
		for(int i=0;i<4;i++){
			nx=p1.x+dxs[i];
			ny=p1.y+dys[i];
			nt=p1.len+1;//縦横チェック
			if(nx<0 || w<=nx || ny<0 || h<=ny) continue;
			if(map[ny][nx]=='X' || (turn[ny][nx]!=0 && nt>=turn[ny][nx])) continue;
			if(nx==gx && ny==gy)return nt;
			turn[ny][nx]=nt;
			p2.x=nx;
			p2.y=ny;
			p2.len=nt;
			points.push(p2);
		}
	}
	return 0;
 }
 int main(){
	int h,w,n;
	int sx,sy;
	char t;
	point points[10];
	scanf("%d %d %d",&h,&w,&n);
	for(int y=0;y<h;y++){
		scanf("%s",map[y]);
		for(int x=0;x<w;x++){
			t=map[y][x];
			if(t=='S'){
				points[0].x=x;//スタート座標
				points[0].y=y;
				points[0].len=0;
			}else if('1'<=t && t<='9'){
				points[t-'0'].x=x;//チーズ座標
				points[t-'0'].y=y;
				points[t-'0'].len=0;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		memset(turn,0,sizeof(turn));
		ans+=search(points[i-1],points[i],h,w);//スタートからチーズへチーズからチーズへの経路を検索
	}
	printf("%d\n",ans);
 }