※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

問96 Sum of 4 Integers II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0096
a+b+c+d=n nは4000以下の自然数 a,b,c,dは0~1000までの数で数nを作る方法は何通りあるか?

解法
昔の自分のほうがかしこいコードを書いてたのでこちらを掲載。
今書いてみたほうは、計算量800万回。
それに対してこちらの計算量は1万回。
昔のほうが賢いコード書いてるな私。
aで作れる数は0~1000までが一通り。
それにbを足すと1000~2000までの数が作れてその組み合わせをab[n]とする。
a+b+c=n3としてn3はn3-1000~n3までのab[n3-1000~n3]までの和となる。
dを足しても同様。



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




問97 Sum of Integers II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0097
0~100までの数を同じ数を使わずにn個取り出しその和がsになる組み合わせは何通りあるか?

解法
0を足す場合、1を足す場合、、、100を足す場合と順番に動的計画法で計算すれば解けます。
昔考えたのと全く同じ解法でこれより早いのはちょっと思いつきません。


#include<stdio.h>
#include<string.h>
#include<iostream>

int main(){
	long long int dp[10][1001];
 	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int i=0;i<=100;i++){
		for(int k=9;k>=1;k--){
			for(int j=0;j+i<=1000;j++){
				dp[k][j+i]+=dp[k-1][j];
			}
 		}	
	}
	int n,s;
	while(1){
		scanf("%d %d",&n,&s);
 		if(n==0&&s==0)break;
		std::cout<<dp[n][s]<<"\n";
	}
}



問98 Maximum Sum Sequence II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098
行列の部分和の最大値をこたえよという問題。

解法
左L右Rと足す部分の両端の幅を決めたら、それより上が0以上ならそれより上を足す。
でないならその行から和をとる。
という発想で3重ループを達成。
2重ループにできるかはよくわからない。


#include<stdio.h>
int main(){
	int dp[101][101],n,row[101],ans;
	scanf("%d",&n);
 	for(int r=0;r<n;r++){
		for(int c=0;c<n;c++)scanf("%d",&row[c]);
		if(r==0)ans=row[0];
		for(int L=0;L<n;L++){
			int sum=0;
			for(int R=L;R<n;R++){
				sum+=row[R];
 				if(r==0){
					dp[L][R]=sum;
				}else{
					dp[L][R]=dp[L][R]>=0?dp[L][R]+sum:sum;
				}
				if(ans<dp[L][R])ans=dp[L][R]; 
			}
 		}
	}
	printf("%d\n",ans);
}


問99 Surf Smelt Fishing Contest II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0099
ワカサギ釣りで次々と釣果が報告されるので現在一位の人を表示する問題。
解法
普通に中の上くらいの成績のコード。
メモリ低減とか速度よりもわかりやすさを重視して記述。
出てきた番号の人が何匹つってるかの記録と、全員の順位を保管しているmemoの二つを使ってみている。


#include<stdio.h>
#include<set>
#include<map>

struct S{
	int no,v;
	bool operator<(const S& s)const{
		if(v!=s.v)return v>s.v;
		return no<s.no;
	}
};
std::map<int,int> noToV;
std::set<S> memo;

int main(){
	int n,q,v;
	std::set<S>::iterator it;
	S s1;
	scanf("%d %d",&n,&q);
	while(q--){
 		scanf("%d %d",&s1.no,&v);
		if(noToV.find(s1.no)==noToV.end()){
			s1.v=v;
			noToV[s1.no]=s1.v;
		}else{
 			s1.v=noToV[s1.no];
			memo.erase(s1);
			s1.v+=v;
			noToV[s1.no]=s1.v;
 		}
		memo.insert(s1);
		it=memo.begin();
		printf("%d %d\n",(*it).no,(*it).v);
 	}
}



問100 Sale Result

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0100
社員の売り上げデータと単価を集計して100万以上売り上げた社員を出力するだけの問題。

解法
出力する順番が出現順であることにだけ注意して集計するだけです。


#include<stdio.h>
#include<vector>
#include<iostream>

void calc(int n){
	long long int sales[4001]={0},v,c;
	std::vector<int> nos;
	int no;
	while(n--){
		std::cin>>no>>v>>c;
		if(sales[no]==0)nos.push_back(no);
		sales[no]+=v*c;
 	}
	bool notNA=false;
	for(int i=0;i<nos.size();i++){
		if(sales[nos[i]]>=1000000){
			std::cout<<nos[i]<<"\n";
 			notNA=true;
		}
	}
	if(notNA==false)std::cout<<"NA\n";
 }

int main(){
	int n;
 	while(scanf("%d",&n)!=EOF){
		if(n==0)break;
		calc(n);
	}
}