問96 Sum of 4 Integers II
解法
昔の自分のほうがかしこいコードを書いてたのでこちらを掲載。
今書いてみたほうは、計算量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
解法
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
解法
左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
#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
解法
出力する順番が出現順であることにだけ注意して集計するだけです。
#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);
}
}
最終更新:2014年02月06日 10:30