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

AOJ91～100 - (2013/04/02 (火) 11:33:58) の１つ前との変更点

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

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

*0091 Blur
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0091
ジャッジデータが存在しないので飛ばし


*0092　Square Searching
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092
.と*で出来た升目のデータが与えられます。
盤面の中らから、.の部分だけを使って出来る最大の長方形を見つけよという問題です。

解法
まず前の行から次の行へと何段.が連続してるか計算します。
後は、そのデータをもとに横方向に移動しながら正方形が作れるかをチェックするだけです。
今まで見つかった最大の正方形より小さい正方形はチェックしないようにしています。
悪くないコードだと思いますがこのコードは実行速度的にあまりいいコードではありません。
他の方のコードを参考にした方がよいでしょう。
他の方によればこの問題は漸化式的に処理でき計算量は線形的になるそうです。


 #include<stdio.h>
 void setMap(int n){
	char map[1001];
	int memo[1001]={0},y,up,ans=0,t,right,x;
	for(int i=0;i<n;i++){
		scanf("%s",map);
		for(x=0;x<n;x++){
			if(map[x]=='.'){
				memo[x]=memo[x]+1;
			}else{
				memo[x]=0;
			}
		}		
		for(int p=0;p<n;p++){
			t=memo[p];
			for(int k=t;k>ans;k--){
				right=k+p;
				if(right>n) continue;
				x=p;
				while(x<right){
					if(k>memo[x]) break;
					x++;
				}
				if(x==right){
					ans=ans>k?ans:k;
					break;
				}
			}
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		setMap(n);
	}
 }





*追記　他の人のコードを見て書きなおした分。
 #include<stdio.h>
 #include<string.h>
 #include <algorithm>
 char Line[1002];
 int memo[2][1002];
 void calc(int n){
	memset(memo,0,sizeof(memo));
	int ans=0;
	for(int i=0;i<n;i++){
		scanf("%s",Line);
		int now=i&1;
		int next=(i+1)&1;
		for(int x=0;x<n;x++){
			if(Line[x]=='.'){
				memo[next][x+1]=std::min(std::min(memo[now][x+1],memo[next][x]),memo[now][x])+1;
				ans=std::max(ans,memo[next][x+1]);
			}else{
				memo[next][x+1]=0;
			}
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		calc(n);
	}
 }




*0093 Leap Year
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0093
与えられた2つの年の間に何個閏年があるかを閏年をすべて出力する問題。
解法
西暦3000年までしか問われないので最初に閏年を全てメモ化しておくだけです。


 #include<stdio.h>
 int main(){
	int years[3001]={0},a,b,c,f=0;
	for(int i=0;i<3000;i++){
		if(i%4==0){
			if(i%100==0 && i%400==0){
				years[i]=1;
			}else if(i%100!=0){
				years[i]=1;
			}
		}
	}	
	while(1){
		scanf("%d %d",&a,&b);
		if(a==0 && b==0) break;
		f==0?f=1:printf("\n");
		c=0;
		a+=(a%4==0?0:4-a%4);
		for(int i=a;i<=b;i+=4){
			if(years[i]==1){
				printf("%d\n",i);
				c++;
			}
		}
		printf("%s",c==0?"NA\n":"");
	}
 }




----
*0094 Calculation of Area
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0094
単位換算するだけの問題。


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




----
*0095 Surf Smelt Fishing Contest
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0095
釣り大会で一番多く釣った人を答える問題。


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



----
*AOJ 0096 Sum of 4 Integers II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0096
0<=n<=4000なｎが与えられるので
a+b+c+d=n
0<=a,b,c,d<=1000
としてｎを何通りの表し方で表すことが出来るか？
問題を読んで３分ほど考えて計算量10000回でクリア。
簡単すぎてショートコードくらいしかやることがない。


 #include<stdio.h>
 #include<iostream>
 #include<string.h>
 long long int memo[4001]={0};
 void calc(int up){
 	long long int sum=0;
 	long long int next[4001]={0};
  	for(int i=0;i<=up;i++){
 		sum+=memo[i];
 		if(i>1000){
 			sum-=memo[i-1001];
  		}
 		next[i]=sum;
 	}
 	memcpy(memo,next,sizeof(next));
 }
 
 int main(){
 	for(int i=0;i<=1000;i++)memo[i]=1;//aを決定
 	calc(2000);
  	calc(3000);
 	calc(4000);
 	int n;
  	while(scanf("%d",&n)!=EOF){
 		std::cout<<memo[n]<<"\n";
 	}
 	
 }





----
*0097　Sum of Integers II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0097
0～100から異なる数をｎ個選んで和ｓを作る。
ｓを作れる和の組み合わせ数を答えよ。
問われるのは答えが10＾10以内となる組み合わせのみである。

解法
一応合格はもらったけど？
他の人がみな00.00secで解いてるのに私だけ00.04 secかかってる。
恥ずかしい。
ええとどこをいじれば纏めて計算できるのだろうか？
ちょっと思いつかない。
10＾10以内ということを利用して逐次計算して答えるのかも？


 #include<stdio.h>
 #include<string.h>
 #include<iostream>
 long long int dp[10][101][1001],ans[10][1001];
 
 void calc(){
 	memset(dp,0,sizeof(dp));
 	memset(ans,0,sizeof(ans));
 	dp[0][0][0]=1;
 	dp[1][0][0]=1;
  	for(int i=1;i<=9;i++){
 		for(int j=0;j<=100;j++){
 			for(int k=j+1;k<=100;k++){
 				for(int L=0;L+k<=1000;L++){
 					dp[i][k][L+k]+=dp[i-1][j][L];//問われない範囲で桁あふれが起きても気にしない
  				}
 			}
 		}
 	}
 	for(int i=1;i<=9;i++){
 		for(int j=0;j<=100;j++){
  			for(int k=0;k<=1000;k++){
 				ans[i][k]+=dp[i][j][k];
 			}
 		}
 	}
 }
 
 
 int main(){
 	calc();
 	int n,s;
 	while(1){
  		scanf("%d %d",&n,&s);
 		if(n==0&&s==0)break;
 		std::cout<<ans[n][s]<<"\n";
 	}
 }





----
*100 Sale Result
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0100
販売員の売上げ記録があります。
売り上げの総計が1000000を超えた従業員のリストを作ってくださいという問題。
解法
intでは桁あふれが生じるのでlong long intを使うだけ後は計算するだけです。



 #include<stdio.h>
 void calc(int n){
    long long int sums[4001];
    for(int i=0;i<4001;i++)sums[i]=0;
    int no,m,c,hit=0;
    for(int i=0;i<n;i++){
        scanf("%d %d %d",&no,&m,&c);
        if(sums[no]<0) continue;
        sums[no]+=((long long int)m)*c;
        if(sums[no]>=1000000){
            sums[no]=-1;
            printf("%d\n",no);
            hit++;
        }
    }
    if(hit==0)printf("NA\n");
 }
 int main(){
    int n=1;
    while(1){
        scanf("%d",&n);
        if(n==0) break;
        calc(n);
    }
 }

*0091 Blur
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0091
ジャッジデータが存在しないので飛ばし


*0092　Square Searching
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092
.と*で出来た升目のデータが与えられます。
盤面の中らから、.の部分だけを使って出来る最大の長方形を見つけよという問題です。

解法
まず前の行から次の行へと何段.が連続してるか計算します。
後は、そのデータをもとに横方向に移動しながら正方形が作れるかをチェックするだけです。
今まで見つかった最大の正方形より小さい正方形はチェックしないようにしています。
悪くないコードだと思いますがこのコードは実行速度的にあまりいいコードではありません。
他の方のコードを参考にした方がよいでしょう。
他の方によればこの問題は漸化式的に処理でき計算量は線形的になるそうです。


 #include<stdio.h>
 void setMap(int n){
	char map[1001];
	int memo[1001]={0},y,up,ans=0,t,right,x;
	for(int i=0;i<n;i++){
		scanf("%s",map);
		for(x=0;x<n;x++){
			if(map[x]=='.'){
				memo[x]=memo[x]+1;
			}else{
				memo[x]=0;
			}
		}		
		for(int p=0;p<n;p++){
			t=memo[p];
			for(int k=t;k>ans;k--){
				right=k+p;
				if(right>n) continue;
				x=p;
				while(x<right){
					if(k>memo[x]) break;
					x++;
				}
				if(x==right){
					ans=ans>k?ans:k;
					break;
				}
			}
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		setMap(n);
	}
 }





*追記　他の人のコードを見て書きなおした分。
 #include<stdio.h>
 #include<string.h>
 #include <algorithm>
 char Line[1002];
 int memo[2][1002];
 void calc(int n){
	memset(memo,0,sizeof(memo));
	int ans=0;
	for(int i=0;i<n;i++){
		scanf("%s",Line);
		int now=i&1;
		int next=(i+1)&1;
		for(int x=0;x<n;x++){
			if(Line[x]=='.'){
				memo[next][x+1]=std::min(std::min(memo[now][x+1],memo[next][x]),memo[now][x])+1;
				ans=std::max(ans,memo[next][x+1]);
			}else{
				memo[next][x+1]=0;
			}
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		calc(n);
	}
 }




*0093 Leap Year
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0093
与えられた2つの年の間に何個閏年があるかを閏年をすべて出力する問題。
解法
西暦3000年までしか問われないので最初に閏年を全てメモ化しておくだけです。


 #include<stdio.h>
 int main(){
	int years[3001]={0},a,b,c,f=0;
	for(int i=0;i<3000;i++){
		if(i%4==0){
			if(i%100==0 && i%400==0){
				years[i]=1;
			}else if(i%100!=0){
				years[i]=1;
			}
		}
	}	
	while(1){
		scanf("%d %d",&a,&b);
		if(a==0 && b==0) break;
		f==0?f=1:printf("\n");
		c=0;
		a+=(a%4==0?0:4-a%4);
		for(int i=a;i<=b;i+=4){
			if(years[i]==1){
				printf("%d\n",i);
				c++;
			}
		}
		printf("%s",c==0?"NA\n":"");
	}
 }




----
*0094 Calculation of Area
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0094
単位換算するだけの問題。


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




----
*0095 Surf Smelt Fishing Contest
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0095
釣り大会で一番多く釣った人を答える問題。


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



----
*AOJ 0096 Sum of 4 Integers II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0096
0<=n<=4000なｎが与えられるので
a+b+c+d=n
0<=a,b,c,d<=1000
としてｎを何通りの表し方で表すことが出来るか？
問題を読んで３分ほど考えて計算量10000回でクリア。
簡単すぎてショートコードくらいしかやることがない。


 #include<stdio.h>
 #include<iostream>
 #include<string.h>
 long long int memo[4001]={0};
 void calc(int up){
 	long long int sum=0;
 	long long int next[4001]={0};
  	for(int i=0;i<=up;i++){
 		sum+=memo[i];
 		if(i>1000){
 			sum-=memo[i-1001];
  		}
 		next[i]=sum;
 	}
 	memcpy(memo,next,sizeof(next));
 }
 
 int main(){
 	for(int i=0;i<=1000;i++)memo[i]=1;//aを決定
 	calc(2000);
  	calc(3000);
 	calc(4000);
 	int n;
  	while(scanf("%d",&n)!=EOF){
 		std::cout<<memo[n]<<"\n";
 	}
 	
 }





----
*0097　Sum of Integers II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0097
0～100から異なる数をｎ個選んで和ｓを作る。
ｓを作れる和の組み合わせ数を答えよ。
問われるのは答えが10＾10以内となる組み合わせのみである。

解法
何も考えずにdpすると２５００万回の計算回数になるので工夫します。
ｄｐのループを足す数、足された個数、合計値の順で計算すると少ない計算量で答えが出ます。


 #include<stdio.h>
 #include<string.h>
 #include<iostream>
 long long int dp[10][1001],max;
 
 void calc(){
 	max=10000*10000;
 	max*=100;
 	memset(dp,0,sizeof(dp));
 	dp[0][0]=1;
  	for(int i=0;i<=100;i++){
 		for(int j=9;j>=1;j--){
 			for(int k=0;k+i<=1000;k++){
 				dp[j][k+i]+=dp[j-1][k];//問われない範囲が桁あふれしても気にしない
 			}
 		}
 	}
 }
 
 
 int main(){
 	calc();
 	int n,s;
  	while(1){
 		scanf("%d %d",&n,&s);
 		if(n==0&&s==0)break;
 		std::cout<<dp[n][s]<<"\n";
 	}
 }




----
*100 Sale Result
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0100
販売員の売上げ記録があります。
売り上げの総計が1000000を超えた従業員のリストを作ってくださいという問題。
解法
intでは桁あふれが生じるのでlong long intを使うだけ後は計算するだけです。



 #include<stdio.h>
 void calc(int n){
    long long int sums[4001];
    for(int i=0;i<4001;i++)sums[i]=0;
    int no,m,c,hit=0;
    for(int i=0;i<n;i++){
        scanf("%d %d %d",&no,&m,&c);
        if(sums[no]<0) continue;
        sums[no]+=((long long int)m)*c;
        if(sums[no]>=1000000){
            sums[no]=-1;
            printf("%d\n",no);
            hit++;
        }
    }
    if(hit==0)printf("NA\n");
 }
 int main(){
    int n=1;
    while(1){
        scanf("%d",&n);
        if(n==0) break;
        calc(n);
    }
 }