「AOJ再挑戦96～100」の編集履歴（バックアップ）一覧はこちら
「AOJ再挑戦96～100」(2014/02/06 (木) 10:30:03) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問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までの数で数ｎを作る方法は何通りあるか？
解法
昔の自分のほうがかしこいコードを書いてたのでこちらを掲載。
今書いてみたほうは、計算量800万回。
それに対してこちらの計算量は１万回。
昔のほうが賢いコード書いてるな私。
aで作れる数は0～1000までが一通り。
それにｂを足すと1000～2000までの数が作れてその組み合わせをab[n]とする。
a+b+c=n3としてn3はn3-1000～n3までのab[n3-1000～n3]までの和となる。
ｄを足しても同様。
#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までの数を同じ数を使わずにｎ個取り出しその和がｓになる組み合わせは何通りあるか？
解法
0を足す場合、１を足す場合、、、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以上ならそれより上を足す。
でないならその行から和をとる。
という発想で３重ループを達成。
２重ループにできるかはよくわからない。
#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);
}
}
*問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までの数で数ｎを作る方法は何通りあるか？
解法
昔の自分のほうがかしこいコードを書いてたのでこちらを掲載。
今書いてみたほうは、計算量800万回。
それに対してこちらの計算量は１万回。
昔のほうが賢いコード書いてるな私。
aで作れる数は0～1000までが一通り。
それにｂを足すと1000～2000までの数が作れてその組み合わせをab[n]とする。
a+b+c=n3としてn3はn3-1000～n3までのab[n3-1000～n3]までの和となる。
ｄを足しても同様。
#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までの数を同じ数を使わずにｎ個取り出しその和がｓになる組み合わせは何通りあるか？
解法
0を足す場合、１を足す場合、、、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以上ならそれより上を足す。
でないならその行から和をとる。
という発想で３重ループを達成。
２重ループにできるかはよくわからない。
#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);
}
}
