「AOJ再挑戦91～95」の編集履歴（バックアップ）一覧はこちら

「AOJ再挑戦91～95」(2014/02/06 (木) 04:17:50) の最新版変更点

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

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

*問91　Blur
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0091
布の色の濃さのデータからどのように染料がたらされたのか逆算する問題。

解法
地道に一マスずつ動的計画法を適用しました。
コードはマトリックス化して配列にしておくべきだったかも。
めんどくさいので解説とか書かない。
色の濃さの合計値からたらした染料のサイズの個数を逆算すればもうちょっと早くなるかも。
速度は遅いしメモリは食ってるしこのコードは合格はしたけれど現状失敗作。



 #include<stdio.h>
 #include<vector>
 #include<set>
 
 struct S{
 	int n,x,y;
 	int map[10][10];
 	std::vector<int> ansXs,ansYs,ansSize;
 	bool operator<(const S& s)const{
 		if(n!=s.n)return n<s.n;
		if(y!=s.y)return y<s.y;
 		if(x!=s.x)return x<s.x;
 		for(int i=-2;i<=2;i++){
 			int dy=y+i;
 			if(0<=dy&&dy<=9){
 				for(int x=0;x<=9;x++){
 					if(map[dy][x]!=s.map[dy][x])return map[dy][x]<s.map[dy][x];
 				}
 			}
 		}
 		return false;
 	}
 	void commit(int size){
 		ansXs.push_back(x);
		ansYs.push_back(y);
 		ansSize.push_back(size);
 	}
 	void commitPop(){
 		ansXs.pop_back();
 		ansYs.pop_back();
 		ansSize.pop_back();
 	}
 
 	bool isNextOK(){
 		if(y<2)return true;
 		if(2<=y&&y<=7){
 			return map[y-2][x]==0;
 		}
		if(y==8){
 			if(map[y-2][x]>0)return false;
 			if(x==9){
 				return n==0&&(map[y-1][x] | map[y][x] | map[y+1][x] | map[y-1][x-1] | map[y][x-1] | map[y+1][x-1])==0;
 			}else if(x>0){
 				return (map[y-1][x-1] | map[y][x-1] | map[y+1][x-1])==0;
 			}else{
 				return true;
 			}
 		}
 		return false;
	}
  	
 	bool isS_OK(){
 		if(n<=0)return false;
 		if(0<x&&x<9&&0<y&&y<9){
 			return map[y-1][x]>0 && map[y+1][x]>0 && map[y][x+1]>0 && map[y][x-1]>0 && map[y][x]>0;
 		}else{
			return false;
 		}
 	}
 	bool isM_OK(){
 		if(0<x&&x<9&&0<y&&y<9){
  			bool t =map[y-1][x-1]>0 && map[y-1][x+1]>0 && map[y+1][x+1]>0 && map[y+1][x-1]>0;
			return t&&isS_OK();
  		}else{
 			return false;
		}
 	}
 	bool isL_OK(){
 		if(1<x&&x<8&&1<y&&y<8){
  			bool t =map[y-2][x]>0&&map[y+2][x]>0&&map[y][x+2]>0&&map[y][x-2]>0;
			return t&&isM_OK();
 		}else{
  			return false;
		}
 	}
 	void changeS(int add){
 		map[y-1][x]+=add;
 		map[y+1][x]+=add;
 		map[y][x-1]+=add;
 		map[y][x+1]+=add;
 		map[y][x]+=  add;
 		n+=add;
 	}
 	
 	void changeM(int add){
 		map[y-1][x-1]+=add;
  		map[y-1][x+1]+=add;
 		map[y+1][x-1]+=add;
 		map[y+1][x+1]+=add;
 		changeS(add);
 	}
 	
 	void changeL(int add){
 		map[y+2][x]+=add;
 		map[y-2][x]+=add;
  		map[y][x+2]+=add;
		map[y][x-2]+=add;
  		changeM(add);
 	}
 
 };
 
 void searchS(std::set<S>& next,S& s1){
 	if(s1.isS_OK()){
 		s1.changeS(-1);
 		s1.commit(1);
 		searchS(next,s1);
  		if(s1.isNextOK()==true){
 			next.insert(s1);
 		}
 		s1.commitPop();
 		s1.changeS(1);
 	}
 }
 void searchM(std::set<S>& next,S& s1){
 	searchS(next,s1);
 	if(s1.isM_OK()){
 		s1.changeM(-1);
 		s1.commit(2);
  		searchM(next,s1);
 		if(s1.isNextOK()==true){
  			next.insert(s1);
 		}
 		s1.commitPop();
 		s1.changeM(1);
	}
 }
 	
 	
 void searchL(std::set<S>& next,S &s1){
 	searchM(next,s1);
 	if(s1.isL_OK()){
 		s1.changeL(-1);
 		s1.commit(3);
 		searchL(next,s1);
 		if(s1.isNextOK()==true){
 			next.insert(s1);
 		}
 		s1.commitPop();
 		s1.changeL(1);
 	}
 }
 
 void calc(S seed){
 	std::set<S>::iterator it;
 	S s1;
 	std::set<S> memo,next;
 	memo.insert(seed);
 	for(int y=1;y<=8;y++){
 		for(int x=1;x<=9;x++){
  			for(it=memo.begin();it!=memo.end();it++){
 				s1=(*it);
 				s1.x=x;
 				s1.y=y;
 				searchL(next,s1);
 				if(s1.isNextOK())next.insert(s1);
 			}
 			memo.clear();
 			memo.insert(next.begin(),next.end());
 			next.clear();
 		}
 	}
  	it=memo.begin();
 	s1=(*it);
 	for(int i=0;i<s1.ansXs.size();i++){
 		printf("%d %d %d\n",s1.ansXs[i],s1.ansYs[i],s1.ansSize[i]);
 	}
 }
 
  
 
 
 int main(){
  	S seed;
 	scanf("%d",&seed.n);
 	for(int i=0;i<10;i++){
 		for(int j=0;j<10;j++){
 			scanf("%d",&seed.map[i][j]);
  		}
 	}
 	calc(seed);
 }




*問92　Square Searching
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092
格子上のデータの中に描ける最大の大きさの正方形のサイズをこたえる問題。
解法
左上から右下へのメモ化で左、上、斜め左上で描けている正方形のうちそのサイズに+1した数がそのマスを右下としたとき描ける最大の正方形。



 #include<stdio.h>
 #include<algorithm>
 
 void calc(int n){
 	char oneLine[1001];
 	int memo[1001]={0},ans=0,old;
 	for(int y=0;y<n;y++){
  		scanf("%s",oneLine);
 		old=memo[0];
 		memo[0]=(oneLine[0]=='.');
 		ans=std::max(ans,memo[0]);
 
 		for(int j=1;j<n;j++){
			if(oneLine[j]=='*'){
 				old=memo[j];
 				memo[j]=0;
  			}else{
 				int m=old;
 				m=std::min(m,memo[j]);
 				m=std::min(m,memo[j-1]);
 				old=memo[j];
 				memo[j]=m+1;
 				ans=std::max(ans,m+1);
  			}
 		}
 	}
 	printf("%d\n",ans);
 }
 
 int main(){
 	int n;
 	while(scanf("%d",&n)!=EOF){
  		if(n==0)break;
 		calc(n);
 	}
 
 }




*問93　Leap Year
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0093
指定された範囲内にあるうるう年をこたえる問題。
解法
範囲が狭いので全検討で間に合います。

 
 #include<stdio.h>
 bool hit(int y){
 	return y%4==0 && (y%400==0 || y%100>0);
 }
 
 int main(){
 	int a,b,turn=0;
  	while(scanf("%d %d",&a,&b)!=EOF){
 		if(a==0&&b==0)break;
 		if(turn>0)printf("\n");
 		int count=0;
 		for(int i=a;i<=b;i++){
 			if(hit(i)){
 				printf("%d\n",i);
 				count++;
 			}
  		}
 		if(count==0)printf("NA\n");
 		turn++;
 	}
 }




*問94 Calculation of Area
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0094
平方メートルを坪に換算するだけの問題。


 #include<stdio.h>
 int main(){
 	double a,b;
 	scanf("%lf %lf",&a,&b);
 	printf("%.6lf\n",a*b/3.305785);
 }

*問91　Blur
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0091
布の色の濃さのデータからどのように染料がたらされたのか逆算する問題。

解法
地道に一マスずつ動的計画法を適用しました。
コードはマトリックス化して配列にしておくべきだったかも。
めんどくさいので解説とか書かない。
色の濃さの合計値からたらした染料のサイズの個数を逆算すればもうちょっと早くなるかも。
速度は遅いしメモリは食ってるしこのコードは合格はしたけれど現状失敗作。



 #include<stdio.h>
 #include<vector>
 #include<set>
 
 struct S{
 	int n,x,y;
 	int map[10][10];
 	std::vector<int> ansXs,ansYs,ansSize;
 	bool operator<(const S& s)const{
 		if(n!=s.n)return n<s.n;
		if(y!=s.y)return y<s.y;
 		if(x!=s.x)return x<s.x;
 		for(int i=-2;i<=2;i++){
 			int dy=y+i;
 			if(0<=dy&&dy<=9){
 				for(int x=0;x<=9;x++){
 					if(map[dy][x]!=s.map[dy][x])return map[dy][x]<s.map[dy][x];
 				}
 			}
 		}
 		return false;
 	}
 	void commit(int size){
 		ansXs.push_back(x);
		ansYs.push_back(y);
 		ansSize.push_back(size);
 	}
 	void commitPop(){
 		ansXs.pop_back();
 		ansYs.pop_back();
 		ansSize.pop_back();
 	}
 
 	bool isNextOK(){
 		if(y<2)return true;
 		if(2<=y&&y<=7){
 			return map[y-2][x]==0;
 		}
		if(y==8){
 			if(map[y-2][x]>0)return false;
 			if(x==9){
 				return n==0&&(map[y-1][x] | map[y][x] | map[y+1][x] | map[y-1][x-1] | map[y][x-1] | map[y+1][x-1])==0;
 			}else if(x>0){
 				return (map[y-1][x-1] | map[y][x-1] | map[y+1][x-1])==0;
 			}else{
 				return true;
 			}
 		}
 		return false;
	}
  	
 	bool isS_OK(){
 		if(n<=0)return false;
 		if(0<x&&x<9&&0<y&&y<9){
 			return map[y-1][x]>0 && map[y+1][x]>0 && map[y][x+1]>0 && map[y][x-1]>0 && map[y][x]>0;
 		}else{
			return false;
 		}
 	}
 	bool isM_OK(){
 		if(0<x&&x<9&&0<y&&y<9){
  			bool t =map[y-1][x-1]>0 && map[y-1][x+1]>0 && map[y+1][x+1]>0 && map[y+1][x-1]>0;
			return t&&isS_OK();
  		}else{
 			return false;
		}
 	}
 	bool isL_OK(){
 		if(1<x&&x<8&&1<y&&y<8){
  			bool t =map[y-2][x]>0&&map[y+2][x]>0&&map[y][x+2]>0&&map[y][x-2]>0;
			return t&&isM_OK();
 		}else{
  			return false;
		}
 	}
 	void changeS(int add){
 		map[y-1][x]+=add;
 		map[y+1][x]+=add;
 		map[y][x-1]+=add;
 		map[y][x+1]+=add;
 		map[y][x]+=  add;
 		n+=add;
 	}
 	
 	void changeM(int add){
 		map[y-1][x-1]+=add;
  		map[y-1][x+1]+=add;
 		map[y+1][x-1]+=add;
 		map[y+1][x+1]+=add;
 		changeS(add);
 	}
 	
 	void changeL(int add){
 		map[y+2][x]+=add;
 		map[y-2][x]+=add;
  		map[y][x+2]+=add;
		map[y][x-2]+=add;
  		changeM(add);
 	}
 
 };
 
 void searchS(std::set<S>& next,S& s1){
 	if(s1.isS_OK()){
 		s1.changeS(-1);
 		s1.commit(1);
 		searchS(next,s1);
  		if(s1.isNextOK()==true){
 			next.insert(s1);
 		}
 		s1.commitPop();
 		s1.changeS(1);
 	}
 }
 void searchM(std::set<S>& next,S& s1){
 	searchS(next,s1);
 	if(s1.isM_OK()){
 		s1.changeM(-1);
 		s1.commit(2);
  		searchM(next,s1);
 		if(s1.isNextOK()==true){
  			next.insert(s1);
 		}
 		s1.commitPop();
 		s1.changeM(1);
	}
 }
 	
 	
 void searchL(std::set<S>& next,S &s1){
 	searchM(next,s1);
 	if(s1.isL_OK()){
 		s1.changeL(-1);
 		s1.commit(3);
 		searchL(next,s1);
 		if(s1.isNextOK()==true){
 			next.insert(s1);
 		}
 		s1.commitPop();
 		s1.changeL(1);
 	}
 }
 
 void calc(S seed){
 	std::set<S>::iterator it;
 	S s1;
 	std::set<S> memo,next;
 	memo.insert(seed);
 	for(int y=1;y<=8;y++){
 		for(int x=1;x<=9;x++){
  			for(it=memo.begin();it!=memo.end();it++){
 				s1=(*it);
 				s1.x=x;
 				s1.y=y;
 				searchL(next,s1);
 				if(s1.isNextOK())next.insert(s1);
 			}
 			memo.clear();
 			memo.insert(next.begin(),next.end());
 			next.clear();
 		}
 	}
  	it=memo.begin();
 	s1=(*it);
 	for(int i=0;i<s1.ansXs.size();i++){
 		printf("%d %d %d\n",s1.ansXs[i],s1.ansYs[i],s1.ansSize[i]);
 	}
 }
 
  
 
 
 int main(){
  	S seed;
 	scanf("%d",&seed.n);
 	for(int i=0;i<10;i++){
 		for(int j=0;j<10;j++){
 			scanf("%d",&seed.map[i][j]);
  		}
 	}
 	calc(seed);
 }




*問92　Square Searching
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092
格子上のデータの中に描ける最大の大きさの正方形のサイズをこたえる問題。
解法
左上から右下へのメモ化で左、上、斜め左上で描けている正方形のうちそのサイズに+1した数がそのマスを右下としたとき描ける最大の正方形。



 #include<stdio.h>
 #include<algorithm>
 
 void calc(int n){
 	char oneLine[1001];
 	int memo[1001]={0},ans=0,old;
 	for(int y=0;y<n;y++){
  		scanf("%s",oneLine);
 		old=memo[0];
 		memo[0]=(oneLine[0]=='.');
 		ans=std::max(ans,memo[0]);
 
 		for(int j=1;j<n;j++){
			if(oneLine[j]=='*'){
 				old=memo[j];
 				memo[j]=0;
  			}else{
 				int m=old;
 				m=std::min(m,memo[j]);
 				m=std::min(m,memo[j-1]);
 				old=memo[j];
 				memo[j]=m+1;
 				ans=std::max(ans,m+1);
  			}
 		}
 	}
 	printf("%d\n",ans);
 }
 
 int main(){
 	int n;
 	while(scanf("%d",&n)!=EOF){
  		if(n==0)break;
 		calc(n);
 	}
 
 }




*問93　Leap Year
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0093
指定された範囲内にあるうるう年をこたえる問題。
解法
範囲が狭いので全検討で間に合います。

 
 #include<stdio.h>
 bool hit(int y){
 	return y%4==0 && (y%400==0 || y%100>0);
 }
 
 int main(){
 	int a,b,turn=0;
  	while(scanf("%d %d",&a,&b)!=EOF){
 		if(a==0&&b==0)break;
 		if(turn>0)printf("\n");
 		int count=0;
 		for(int i=a;i<=b;i++){
 			if(hit(i)){
 				printf("%d\n",i);
 				count++;
 			}
  		}
 		if(count==0)printf("NA\n");
 		turn++;
 	}
 }






*問94 Calculation of Area
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0094
平方メートルを坪に換算するだけの問題。


 #include<stdio.h>
 int main(){
 	double a,b;
 	scanf("%lf %lf",&a,&b);
 	printf("%.6lf\n",a*b/3.305785);
 }





*問95　Surf Smelt Fishing Contest
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0095
ワカサギ釣り大会の優勝者をこたえる問題
解法
そのまま



 #include<stdio.h> 
 int main(){
 	int n,minA,maxV,a,v;
 	scanf("%d %d %d",&n,&minA,&maxV);
 	n--;
 	while(n--){
  		scanf("%d %d",&a,&v);
 		if(v>maxV||(v==maxV && a<minA)){
 			maxV=v;
  			minA=a;
 		}
 	}
 	printf("%d %d\n",minA,maxV);
 }