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

AOJ561～570 - (2012/03/08 (木) 15:48:07) の１つ前との変更点

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

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

*565　Lunch
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0565
簡単な問題なので工夫する気すら起きませんでした。
もし工夫するならショートコーディングくらいかな。

 #include<stdio.h>
 int main(){
	int min1=10000,min2=10000,v;
	for(int i=0;i<3;i++){
		scanf("%d",&v);
		min1=min1>v?v:min1;
	}
	for(int i=0;i<2;i++){
		scanf("%d",&v);
		min2=min2>v?v:min2;
	}
	printf("%d\n",min1+min2-50);
 }

*566　Soccer

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0566
最初ソートすればいいかと思ったがソート関数の定義がめんどくさくなったので手抜き実装。
意外とコードが短くなった。


 #include<stdio.h>
 #include <string.h>
 int main(){
	int n,scores[102],a,b,c,d,ranks[400],max=-1;
	scanf("%d",&n);
	memset(scores,0,sizeof(scores));
	memset(ranks,0,sizeof(ranks));	
	for(int i=0;i<(n*(n-1))/2;i++){
		scanf("%d %d %d %d",&a,&b,&c,&d);
		a--;
		b--;
		if(c>d){
			scores[a]+=3;
		}else if(c<d){
			scores[b]+=3;
		}else{
			scores[a]+=1;
			scores[b]+=1;
		}
	}
	for(int i=0;i<n;i++){
		ranks[scores[i]]++;
		max=max>scores[i]?max:scores[i];
	}
	for(int i=max;i>0;i--){
		ranks[i-1]+=ranks[i];
	}
	for(int i=0;i<n;i++){
		printf("%d\n",ranks[scores[i]+1]+1);
	}
 }


*0567 Best Pizza
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0567
一回目油断しまくりで、＄頭カロリー計算を整数扱いで挑戦して転ぶ。
double型を使う実装に変えてアセプト。
こんな簡単な問題で油断しすぎた。


 #include<stdio.h>
 #include <algorithm>
 #include <functional>
 int main(){
	int n;
	double a,b,c,costLine,ansV,ansC,cs[101];
	scanf("%d %lf %lf %lf",&n,&a,&b,&c);
	costLine=c/a;
	ansV=a;
	ansC=c;	
	for(int i=0;i<n;i++){
		scanf("%lf",&cs[i]);
	}
	sort(cs, cs + n, std::greater<int>());
	for(int i=0;i<n;i++){
		ansV+=b;
		ansC+=cs[i];
		if(ansC/ansV>costLine){
			costLine=ansC/ansV;
		}else{
			break;
		}
	}
	printf("%d\n",(int)(costLine));
 }


*0569　Illumination
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569
幼稚園児と同じレベルで素直に解く。
外側から到達できる部分に２という色を塗っていき、全部の色が塗れたら後は１に隣接している２の数を数え上げていく。
コードサイズを見ると私は最下位クラスなのでもっと賢い方法があるらしい。



 #include<stdio.h>
 #include<string.h>
 int dxsKi[]={ 1, 1, 0,-1, 0, 1};
 int dysKi[]={ 0,-1,-1, 0, 1, 1};
 int dxsGu[]={ 1, 0,-1,-1,-1, 0};
 int dysGu[]={ 0,-1,-1, 0, 1, 1};
 int map[104][104];
 int w,h;
 bool inArea(int x,int y){
	if(x<0||x>w+1||y<0||y>h+1)return 0;
	return 1;
 }
 void saiki(int x,int y){
	if(inArea(x,y)==0||(map[y][x]&2)==2||(map[y][x]&1)==1) return;
	map[y][x]=2;
	int nx,ny;
	for(int i=0;i<6;i++){
		if(y%2==0){
			nx=x+dxsGu[i];
			ny=y+dysGu[i];
		}else{
			nx=x+dxsKi[i];
			ny=y+dysKi[i];
		}
		saiki(nx,ny);
	}
 }
 int main(){
	//1bit目を建物に、2bit目を外から到達可能な地点のフラグ
	//まず最初に外側から到達できるヘクスの情報を取る
	memset(map,0,sizeof(map));//外側を番兵にする
	scanf("%d %d",&w,&h);
	for(int y=1;y<=h;y++){
		for(int x=1;x<=w;x++){
			scanf("%d",&map[y][x]);
		}
	}
	//まずは外側から到達できる地点のフラグを建てる。
	for(int x=1;x<=h+1;x++){
		saiki(x,0);
		saiki(x,h+1);
	}
	for(int y=1;y<=w+1;y++){
		saiki(0,y);
		saiki(w+1,y);
	}
	int ans=0;
	int check[104][104];
	memset(check,0,sizeof(check));	
	int nx,ny;
	for(int y=1;y<=h;y++){
		for(int x=1;x<=w;x++){
			for(int i=0;i<6;i++){
				if(y%2==0){
					nx=x+dxsGu[i];
					ny=y+dysGu[i];
				}else{
					nx=x+dxsKi[i];
					ny=y+dysKi[i];
				}
				if(map[y][x]==1 && map[ny][nx]==2){
					ans++;
					check[y][x]++;
				}
			}
		}
	}
	//for(int y=1;y<=h;y++){
	//	printf("\n%s",y%2==0?" ":"　");
	//	for(int x=1;x<=w;x++){
	//		printf("%d ",check[y][x]);
	//	}
	//}
	printf("%d\n",ans);
 }

*565　Lunch
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0565
簡単な問題なので工夫する気すら起きませんでした。
もし工夫するならショートコーディングくらいかな。

 #include<stdio.h>
 int main(){
	int min1=10000,min2=10000,v;
	for(int i=0;i<3;i++){
		scanf("%d",&v);
		min1=min1>v?v:min1;
	}
	for(int i=0;i<2;i++){
		scanf("%d",&v);
		min2=min2>v?v:min2;
	}
	printf("%d\n",min1+min2-50);
 }

*566　Soccer

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0566
最初ソートすればいいかと思ったがソート関数の定義がめんどくさくなったので手抜き実装。
意外とコードが短くなった。


 #include<stdio.h>
 #include <string.h>
 int main(){
	int n,scores[102],a,b,c,d,ranks[400],max=-1;
	scanf("%d",&n);
	memset(scores,0,sizeof(scores));
	memset(ranks,0,sizeof(ranks));	
	for(int i=0;i<(n*(n-1))/2;i++){
		scanf("%d %d %d %d",&a,&b,&c,&d);
		a--;
		b--;
		if(c>d){
			scores[a]+=3;
		}else if(c<d){
			scores[b]+=3;
		}else{
			scores[a]+=1;
			scores[b]+=1;
		}
	}
	for(int i=0;i<n;i++){
		ranks[scores[i]]++;
		max=max>scores[i]?max:scores[i];
	}
	for(int i=max;i>0;i--){
		ranks[i-1]+=ranks[i];
	}
	for(int i=0;i<n;i++){
		printf("%d\n",ranks[scores[i]+1]+1);
	}
 }


*0567 Best Pizza
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0567
一回目油断しまくりで、＄頭カロリー計算を整数扱いで挑戦して転ぶ。
double型を使う実装に変えてアセプト。
こんな簡単な問題で油断しすぎた。


 #include<stdio.h>
 #include <algorithm>
 #include <functional>
 int main(){
	int n;
	double a,b,c,costLine,ansV,ansC,cs[101];
	scanf("%d %lf %lf %lf",&n,&a,&b,&c);
	costLine=c/a;
	ansV=a;
	ansC=c;	
	for(int i=0;i<n;i++){
		scanf("%lf",&cs[i]);
	}
	sort(cs, cs + n, std::greater<int>());
	for(int i=0;i<n;i++){
		ansV+=b;
		ansC+=cs[i];
		if(ansC/ansV>costLine){
			costLine=ansC/ansV;
		}else{
			break;
		}
	}
	printf("%d\n",(int)(costLine));
 }

*0568　Pasta
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568
普通にメモ化計算で一応正答。
賢い方法を思いつかなかったのでハードコーディングしまくり、このコードを参考にしてはいけない。
例えば４日連続で続いてはいけないとか、料理の種類が増えたらどうするのかとか色々問題のあるコード。
初日２日間の特殊処理だの、その後のメモ化のハードコーディングだの完璧に反面教師。



 #include<stdio.h>
 #include<string.h>
 int mode=10000;
 int n;
 int datas[101];
 int firstMemo[3];
 void firstSet(int deep,int memo[3][3]){
	if(deep==2){
		memo[firstMemo[0]][firstMemo[1]]=1;//こんなハードコーディング駄目だよなと思いつつ楽な方に流れてしまった、、
		return;
	}else{
		if(datas[deep]==-1){
			for(int i=0;i<3;i++){
				firstMemo[deep]=i;
				firstSet(deep+1,memo);
			}
		}else{
			firstMemo[deep]=datas[deep];
			firstSet(deep+1,memo);
		}
	}
 }
 int main(){
	int k,a,b;
	int memo[3][3];
	int next[3][3];
	
	scanf("%d %d",&n,&k);
	memset(datas,-1,sizeof(datas));
	memset(memo,0,sizeof(memo));
	
	for(int i=0;i<k;i++){
		scanf("%d %d",&a,&b);
		a--;//扱いやすい0日目を初日にとる
		b--;//同じく扱いやすい0から始める
		datas[a]=b;
	}
	//最初の二日間を綺麗に扱う方法を思いつかないので特別に計算する。
	firstSet(0,memo);
	//ここも綺麗な解法を思いつかないのでループする、ｎ日とかになったらどうすると言われたら困る
	//-30点くらいのコードですね
	for(int d=2;d<n;d++){
		memset(next,0,sizeof(next));
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				int k=datas[d];
				if(k!=-1){
					if(!(i==j && k==j)){
						next[j][k]=(next[j][k]+memo[i][j])%mode;
					}
				}else{
					for(int k=0;k<3;k++){
						if(!(i==j && k==j)){
							next[j][k]=(next[j][k]+memo[i][j])%mode;
						}
					}
				}
			}
		}
		memcpy(memo,next,sizeof(next));
	}
	int ans=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			ans=(ans+next[i][j])%mode;
		}
	}
	printf("%d\n",ans);
 }



*0569　Illumination
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569
幼稚園児と同じレベルで素直に解く。
外側から到達できる部分に２という色を塗っていき、全部の色が塗れたら後は１に隣接している２の数を数え上げていく。
コードサイズを見ると私は最下位クラスなのでもっと賢い方法があるらしい。



 #include<stdio.h>
 #include<string.h>
 int dxsKi[]={ 1, 1, 0,-1, 0, 1};
 int dysKi[]={ 0,-1,-1, 0, 1, 1};
 int dxsGu[]={ 1, 0,-1,-1,-1, 0};
 int dysGu[]={ 0,-1,-1, 0, 1, 1};
 int map[104][104];
 int w,h;
 bool inArea(int x,int y){
	if(x<0||x>w+1||y<0||y>h+1)return 0;
	return 1;
 }
 void saiki(int x,int y){
	if(inArea(x,y)==0||(map[y][x]&2)==2||(map[y][x]&1)==1) return;
	map[y][x]=2;
	int nx,ny;
	for(int i=0;i<6;i++){
		if(y%2==0){
			nx=x+dxsGu[i];
			ny=y+dysGu[i];
		}else{
			nx=x+dxsKi[i];
			ny=y+dysKi[i];
		}
		saiki(nx,ny);
	}
 }
 int main(){
	//1bit目を建物に、2bit目を外から到達可能な地点のフラグ
	//まず最初に外側から到達できるヘクスの情報を取る
	memset(map,0,sizeof(map));//外側を番兵にする
	scanf("%d %d",&w,&h);
	for(int y=1;y<=h;y++){
		for(int x=1;x<=w;x++){
			scanf("%d",&map[y][x]);
		}
	}
	//まずは外側から到達できる地点のフラグを建てる。
	for(int x=1;x<=h+1;x++){
		saiki(x,0);
		saiki(x,h+1);
	}
	for(int y=1;y<=w+1;y++){
		saiki(0,y);
		saiki(w+1,y);
	}
	int ans=0;
	int check[104][104];
	memset(check,0,sizeof(check));	
	int nx,ny;
	for(int y=1;y<=h;y++){
		for(int x=1;x<=w;x++){
			for(int i=0;i<6;i++){
				if(y%2==0){
					nx=x+dxsGu[i];
					ny=y+dysGu[i];
				}else{
					nx=x+dxsKi[i];
					ny=y+dysKi[i];
				}
				if(map[y][x]==1 && map[ny][nx]==2){
					ans++;
					check[y][x]++;
				}
			}
		}
	}
	//for(int y=1;y<=h;y++){
	//	printf("\n%s",y%2==0?" ":"　");
	//	for(int x=1;x<=w;x++){
	//		printf("%d ",check[y][x]);
	//	}
	//}
	printf("%d\n",ans);
 }