「AOJ Problem Set from ALDS1 問25~29」の編集履歴(バックアップ)一覧はこちら

AOJ Problem Set from ALDS1 問25~29」(2014/01/18 (土) 14:14:20) の最新版変更点

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

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

*Heaps - Maximum Heap http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B きちんとしたヒープを組み立てる問題。 #include<stdio.h> const int SIZE=500005; int heap_size; int A[SIZE]; void maxHeapify(int *A,int i){ int l=2*i; int r=2*i+1; int largest; if(l<=heap_size && A[l]>A[i]){ largest=l; }else{ largest=i; } if(r<=heap_size&&A[r]>A[largest]){ largest=r; } if(largest!=i){ int t=A[i]; A[i]=A[largest]; A[largest]=t; maxHeapify(A,largest); } } void buildMaxHeap(int *A){ for(int i=heap_size/2;i>0;i--)maxHeapify(A,i); } int main(){ int num; scanf("%d",&heap_size); for(int i=1;i<=heap_size;i++){ scanf("%d",&A[i]); } buildMaxHeap(A); for(int i=1;i<=heap_size;i++){ printf(" %d",A[i]); } printf("\n"); } *Heaps - Priority Queue http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C ヒープから優先順位付きキューを作る問題 最下層の適当な数字をとりだしヒープを入れ替えていくとlog nで優先順位付きqueueの次のデータが求まる。 よくできて切るよな。 #include<stdio.h> const int SIZE=2000001; int heap_size=0; int A[SIZE]; const int ERROR=-1; void maxHeapify(int *A,int i){ int l=2*i; int r=2*i+1; int largest; if(l<=heap_size && A[l]>A[i]){ largest=l; }else{ largest=i; } if(r<=heap_size&&A[r]>A[largest]){ largest=r; } if(largest!=i){ int t=A[i]; A[i]=A[largest]; A[largest]=t; maxHeapify(A,largest); } } void heapIncreaseKey(int *A,int i,int key){ if(key<A[i]){ return ; } A[i]=key; while(i>1 && A[i/2]<A[i]){ int t=A[i]; A[i]=A[i/2]; A[i/2]=t; i=i/2; } } void maxHeapInsert(int *A,int key){ heap_size++; A[heap_size]=ERROR; heapIncreaseKey(A,heap_size,key); } int heapExtractMax(int *A){ if(heap_size<1){ return ERROR; } int max=A[1]; A[1]=A[heap_size]; heap_size--; maxHeapify(A,1); return max; } int main(){ int key; char com[10]; while(1){ scanf("%s",com); if(com[0]=='i'){ scanf("%d",&key); maxHeapInsert(A,key); }else if(com[1]=='x'){ int max=heapExtractMax(A); if(max!=ERROR)printf("%d\n",max); }else{ break; } } } *Dynamic Programming - Fibonacci Number http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A n項めのフィナボッチ数列を出力せよという問題。 #include<stdio.h> int main(){ int f[50]; f[0]=f[1]=1; for(int i=2;i<=44;i++)f[i]=f[i-1]+f[i-2]; int n; scanf("%d",&n); printf("%d\n",f[n]); } *Dynamic Programming - Matrix Chain Multiplication http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B 行列演算のスカラー積を最小にして計算した時の計算回数をこたえる問題。 解法 直列に並んだグラフとみればワーシャルフロイド法もどきが適用でき、あとはその時のスカラー積の回数に注意して計算式を立てるだけです。 計算量はn=100でも166500回。 まあこんなもんかな。 #include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> const int LIMIT=101; long long int myMin(long long int a,long long int b){ if(a==0)return b; if(a<b) return a; else return b; } int main(){ int n,rs[LIMIT],cs[LIMIT],now=0,next=1; long long int memo[2][LIMIT][LIMIT]; memset(memo,0,sizeof(memo)); scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d %d",&rs[i],&cs[i]); int count=0; for(int len=1;len<=n;len++){ for(int p=0;p+len<n;p++){ int r=p+len; for(int m=p;m<r;m++){ long long int perm=memo[now][p][m]+memo[now][m+1][r]; perm+=rs[p]*cs[m]*cs[p+len]; memo[next][p][r]=myMin(memo[next][p][r],perm); count++; } } memcpy(memo[now],memo[next],sizeof(memo[now])); } std::cout<<memo[now][0][n-1]<<"\n"; }
*Heaps - Maximum Heap http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B きちんとしたヒープを組み立てる問題。 #include<stdio.h> const int SIZE=500005; int heap_size; int A[SIZE]; void maxHeapify(int *A,int i){ int l=2*i; int r=2*i+1; int largest; if(l<=heap_size && A[l]>A[i]){ largest=l; }else{ largest=i; } if(r<=heap_size&&A[r]>A[largest]){ largest=r; } if(largest!=i){ int t=A[i]; A[i]=A[largest]; A[largest]=t; maxHeapify(A,largest); } } void buildMaxHeap(int *A){ for(int i=heap_size/2;i>0;i--)maxHeapify(A,i); } int main(){ int num; scanf("%d",&heap_size); for(int i=1;i<=heap_size;i++){ scanf("%d",&A[i]); } buildMaxHeap(A); for(int i=1;i<=heap_size;i++){ printf(" %d",A[i]); } printf("\n"); } *Heaps - Priority Queue http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C ヒープから優先順位付きキューを作る問題 最下層の適当な数字をとりだしヒープを入れ替えていくとlog nで優先順位付きqueueの次のデータが求まる。 よくできて切るよな。 #include<stdio.h> const int SIZE=2000001; int heap_size=0; int A[SIZE]; const int ERROR=-1; void maxHeapify(int *A,int i){ int l=2*i; int r=2*i+1; int largest; if(l<=heap_size && A[l]>A[i]){ largest=l; }else{ largest=i; } if(r<=heap_size&&A[r]>A[largest]){ largest=r; } if(largest!=i){ int t=A[i]; A[i]=A[largest]; A[largest]=t; maxHeapify(A,largest); } } void heapIncreaseKey(int *A,int i,int key){ if(key<A[i]){ return ; } A[i]=key; while(i>1 && A[i/2]<A[i]){ int t=A[i]; A[i]=A[i/2]; A[i/2]=t; i=i/2; } } void maxHeapInsert(int *A,int key){ heap_size++; A[heap_size]=ERROR; heapIncreaseKey(A,heap_size,key); } int heapExtractMax(int *A){ if(heap_size<1){ return ERROR; } int max=A[1]; A[1]=A[heap_size]; heap_size--; maxHeapify(A,1); return max; } int main(){ int key; char com[10]; while(1){ scanf("%s",com); if(com[0]=='i'){ scanf("%d",&key); maxHeapInsert(A,key); }else if(com[1]=='x'){ int max=heapExtractMax(A); if(max!=ERROR)printf("%d\n",max); }else{ break; } } } *Dynamic Programming - Fibonacci Number http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A n項めのフィナボッチ数列を出力せよという問題。 #include<stdio.h> int main(){ int f[50]; f[0]=f[1]=1; for(int i=2;i<=44;i++)f[i]=f[i-1]+f[i-2]; int n; scanf("%d",&n); printf("%d\n",f[n]); } *Dynamic Programming - Matrix Chain Multiplication http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B 行列演算のスカラー積を最小にして計算した時の計算回数をこたえる問題。 解法 直列に並んだグラフとみればワーシャルフロイド法もどきが適用でき、あとはその時のスカラー積の回数に注意して計算式を立てるだけです。 計算量はn=100でも166500回。 まあこんなもんかな。 #include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> const int LIMIT=101; long long int myMin(long long int a,long long int b){ if(a==0)return b; if(a<b) return a; else return b; } int main(){ int n,rs[LIMIT],cs[LIMIT],now=0,next=1; long long int memo[2][LIMIT][LIMIT]; memset(memo,0,sizeof(memo)); scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d %d",&rs[i],&cs[i]); int count=0; for(int len=1;len<=n;len++){ for(int p=0;p+len<n;p++){ int r=p+len; for(int m=p;m<r;m++){ long long int perm=memo[now][p][m]+memo[now][m+1][r]; perm+=rs[p]*cs[m]*cs[p+len]; memo[next][p][r]=myMin(memo[next][p][r],perm); count++; } } memcpy(memo[now],memo[next],sizeof(memo[now])); } std::cout<<memo[now][0][n-1]<<"\n"; } *Dynamic Programming - Longest Common Subsequence http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C 最長一致部分文字列の長さをこたえる問題。 memcpyがもったいない感じはするな。 #include<stdio.h> #include<string.h> #include<algorithm> const int LIMIT=1001; int dp[2][LIMIT]; void search(){ char x[LIMIT],y[LIMIT]; memset(dp,0,sizeof(dp)); scanf("%s %s",x,y); int lenA=strlen(x),lenB=strlen(y),ans=0; const int now=0; const int next=1; for(int i=0;i<lenA;i++){ int max=0; for(int j=0;j<lenB;j++){ if(j>0)max=std::max(max,dp[now][j-1]); dp[next][j]=std::max(dp[now][j],max+(x[i]==y[j])); } memcpy(dp[now],dp[next],sizeof(dp[now])); memset(dp[next],0,sizeof(dp[next])); } for(int i=0;i<lenB;i++)ans=std::max(ans,dp[now][i]); printf("%d\n",ans); } int main(){ int n; scanf("%d",&n); while(n--){ search(); } }

表示オプション

横に並べて表示:
変化行の前後のみ表示: