AOJ91～100 - c21coterie @ ウィキ

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";
	}
}

---

0098　Maximum Sum Sequence II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098
行列表の中から部分行列の和が最大になるよう取りだしたときの最大値を求める問題。

解法

足す列数を定めてから尺取り虫法で計算することで計算量をｎ^3に抑えます。

#include<stdio.h>
int calcMax(int rows[101],int n){
	int sum=rows[0];
	int re=sum;
 	for(int i=1;i<n;i++){
		if(sum<0)sum=rows[i];
		else sum+=rows[i];
		if(re<sum)re=sum;
	}
	return re;
}

int main(){
	int n,mat[101][101];
	scanf("%d",&n);
	for(int i=0;i<n;i++){
 		for(int j=0;j<n;j++){
			scanf("%d",&mat[i][j]);
		}
	}
	int ans=mat[0][0];
	for(int colSize=1;colSize<=n;colSize++){
		int rowSums[101]={0};
		for(int r=0;r<n;r++){
 			for(int c=0;c<colSize;c++){
				rowSums[r]+=mat[r][c];
			}
		}
		int t=calcMax(rowSums,n);
		if(t>ans)ans=t;
		for(int c=colSize;c<n;c++){
			for(int r=0;r<n;r++){
				rowSums[r]+=mat[r][c]-mat[r][c-colSize];
 			}
			t=calcMax(rowSums,n);
			if(t>ans)ans=t;
		}
	}
	printf("%d\n",ans);
}

---

0099 Surf Smelt Fishing Contest II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0099
１００万人の参加するワカサギ釣りで誰かが釣った数かリリースした数が時系列順に１０万個与えられる。
その時点で最もつってる人の参加者Ｎｏと釣ってる数を答えよ。

解法
クエリーの数が少ないことを利用して、釣った人のデータだけ素直に数えてみました。
残念ながら速度はあまり出てません。

#include<stdio.h>
#include<map>
#include<set>
#include<iostream>
std::map<int,std::set<int> > noList;//map<釣った数,この数を釣った人のリスト>
std::map<int,int> toNum;//map<参加者ナンバー,釣った数>
std::set<int>::iterator itList;
std::map<int,std::set<int> >::iterator itNoList;

int main(){
 	int n,q;
	scanf("%d %d",&n,&q);
	int a,v;
 	while(q--){
		scanf("%d %d",&a,&v);
		int t;
		if(toNum.find(a)==toNum.end()){
			t=0;
		}else{
 			t=toNum[a];
		}
 		noList[t].erase(a);
		if(noList[t].empty()==true){
 			noList.erase(t);
		}
		t+=v;
		toNum[a]=t;
		noList[t].insert(a);
		
 		itNoList=noList.end();
		itNoList--;
		itList=(*itNoList).second.begin();
		printf("%d %d\n",(*itList),(*itNoList).first);
	}
}

---

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);
   }
}