Typical DP Contest 過去問埋め
これも新年企画ということで、ACするごとにここにソースコードとかをアップロードしていく予定です。適宜更新してみてください。
A:
やるだけ
#include<stdio.h> int dp[10001]; int b[120]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",b+i); dp[0]=1; for(int i=0;i<a;i++){ for(int j=10000;j>=b[i];j--){ dp[j]|=dp[j-b[i]]; } } int ret=0; for(int i=0;i<=10000;i++)ret+=dp[i]; printf("%d\n",ret); }
B:
自分でも何書いてるかわからないが一瞬
#include<stdio.h> #include<algorithm> using namespace std; int dp[1100][1100]; int a,b; int c[1100]; int d[1100]; int solve(int p,int q){ if(p==a&&q==b)return 0; if(dp[p][q])return dp[p][q]; if((p+q)%2==0){ if(p==a)return dp[p][q]=solve(p,q+1)+d[q]; if(q==b)return dp[p][q]=solve(p+1,q)+c[p]; return dp[p][q]=max(solve(p,q+1)+d[q],solve(p+1,q)+c[p]); }else{ if(p==a)return solve(p,q+1); if(q==b)return solve(p+1,q); return dp[p][q]=min(solve(p,q+1),solve(p+1,q)); } } int main(){ scanf("%d%d",&a,&b); for(int i=0;i<a;i++)scanf("%d",c+i); for(int i=0;i<b;i++)scanf("%d",d+i); printf("%d\n",solve(0,0)); }
C:
やるだけ
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; double calc(int a,int b){ return 1.0/(1.0+pow(10,(double)(b-a)/400)); } double dp[12][2000]; int b[2000]; int main(){ int a; scanf("%d",&a); for(int i=0;i<(1<<a);i++)scanf("%d",b+i); for(int i=0;i<(1<<a);i++)dp[0][i]=1; for(int i=1;i<=a;i++){ for(int j=0;j<(1<<a);j++){ for(int k=0;k<(1<<a);k++){ if((j>>i)!=(k>>i))continue; if((j>>(i-1))==(k>>(i-1)))continue; dp[i][j]+=dp[i-1][j]*dp[i-1][k]*calc(b[j],b[k]); } } } for(int i=0;i<(1<<a);i++)printf("%.12f\n",dp[a][i]); }
D:
変なことしたけど変なことしなくても解けますかこれ
#include<stdio.h> #include<algorithm> using namespace std; double dp[111][64][40][25]; int main(){ int a; long long b; scanf("%d%lld",&a,&b); int c=0; int d=0; int e=0; while(b%2==0){ b/=2; c++; } while(b%3==0){ b/=3; d++; } while(b%5==0){ b/=5; e++; } if(b!=1){ printf("0.0000000\n"); return 0; } dp[0][0][0][0]=1; for(int i=0;i<a;i++){ for(int j=0;j<64;j++){ for(int k=0;k<40;k++){ for(int l=0;l<25;l++){ dp[i+1][j][k][l]+=dp[i][j][k][l]/6; dp[i+1][min(63,j+1)][k][l]+=dp[i][j][k][l]/6; dp[i+1][j][min(39,k+1)][l]+=dp[i][j][k][l]/6; dp[i+1][min(j+2,63)][k][l]+=dp[i][j][k][l]/6; dp[i+1][min(63,j+1)][min(39,k+1)][l]+=dp[i][j][k][l]/6; dp[i+1][j][k][min(24,l+1)]+=dp[i][j][k][l]/6; } } } } double ret=0; for(int i=0;i<64;i++) for(int j=0;j<40;j++) for(int k=0;k<25;k++){ if(c<=i&&d<=j&&e<=k)ret+=dp[a][i][j][k]; } printf("%.12f\n",ret); }
E:
よくあるやつ
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; long long dp[2][11000][110]; int mod=1000000007; char str[11000]; int main(){ int a; scanf("%d%s",&a,str); int n=strlen(str); dp[0][0][0]=1; for(int i=0;i<n;i++){ // printf("%lld %lld\n",dp[0][i][0],dp[1][i][0]); for(int j=0;j<10;j++){ for(int k=0;k<a;k++){ dp[1][i+1][(j+k)%a]=(dp[1][i+1][(j+k)%a]+dp[1][i][k])%mod; } } for(int j=0;j<a;j++){ for(int k=0;k<str[i]-'0';k++){ dp[1][i+1][(j+k)%a]=(dp[1][i+1][(j+k)%a]+dp[0][i][j])%mod; } } for(int j=0;j<a;j++){ dp[0][i+1][(j+str[i]-'0')%a]=(dp[0][i+1][(j+str[i]-'0')%a]+dp[0][i][j])%mod; } } printf("%lld\n",(dp[0][n][0]+dp[1][n][0]+mod-1)%mod); }
F:
補集合を数える。累積和的なアレ
#include<stdio.h> #include<algorithm> using namespace std; long long dp[1100001]; int mod=1000000007; int main(){ int a,b; scanf("%d%d",&a,&b); dp[0]=1; long long sum=1; for(int i=2;i<a;i++){ dp[i]=sum; sum=(sum+dp[i])%mod; if(i>=b)sum=(sum+mod-dp[i-b])%mod; } sum=(sum+mod-dp[a-b])%mod; printf("%lld\n",sum); }
I:
iiwiiwiwiみたいなケースでWAが出ていました。区間DPの再帰関数の中で必ず両端がiで真ん中にwがあり、間も条件を満たすケースで全部取り除けると思ってたけど違いますね。
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; char str[1000]; int dp[1000][1000]; int solve(int a,int b){ if(~dp[a][b])return dp[a][b]; if((b-a)%3)return dp[a][b]=0; if(a==b)return dp[a][b]=1; if(str[a]!='i'||str[b-1]!='i')return dp[a][b]=0; for(int i=a+1;i<b-1;i++){ if(str[i]=='w'&&solve(a+1,i)&&solve(i+1,b-1))return dp[a][b]=1; if(solve(a,i)&&solve(i,b))return dp[a][b]=1; } return dp[a][b]=0; } int dp2[1000]; int main(){ scanf("%s",str); int n=strlen(str); for(int i=0;i<1000;i++) for(int j=0;j<1000;j++) dp[i][j]=-1; for(int i=0;i<n;i++){ for(int j=i+1;j<=n;j++)solve(i,j); } for(int i=0;i<1000;i++)dp2[i]=-99999999; dp2[0]=0; for(int i=0;i<n;i++){ dp2[i+1]=max(dp2[i+1],dp2[i]); for(int j=i+1;j<=n;j++){ if(dp[i][j]==1)dp2[j]=max(dp2[j],dp2[i]+(j-i)/3); } } printf("%d\n",dp2[n]); }
J:
初歩的な期待値DPの問題です。少し慣れてきました。
#include<stdio.h> #include<algorithm> using namespace std; int b[20]; double dp[1<<16]; int c[20]; double solve(int a){ if(dp[a]>-0.5)return dp[a]; if(a==0)return dp[a]=0; double ret=999999999; for(int i=1;i<15;i++){ int x1=c[i-1]; int x2=c[i]; int x3=c[i+1]; int to1=a; int to2=a; int to3=a; if(~x1)to1&=~(1<<x1); if(~x2)to2&=~(1<<x2); if(~x3)to3&=~(1<<x3); int same=0; double val=0; if(to1==a)same++; else val+=solve(to1); if(to2==a)same++; else val+=solve(to2); if(to3==a)same++; else val+=solve(to3); if(same!=3){ val=(val/3+1)*3/(3-same); ret=min(ret,val); } } return dp[a]=ret; } int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",b+i); for(int i=0;i<20;i++)c[i]=-1; for(int i=0;i<a;i++)c[b[i]]=i; for(int i=0;i<(1<<a);i++)dp[i]=-1; printf("%.12f\n",solve((1<<a)-1)); }
N:
問題名+コンテスト名が解法
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; vector<int> g[1100]; long long dp[1100]; int size[1100]; long long C[2000][2000]; int mod=1000000007; long long solve(int a,int b){ int v=0; size[a]++; for(int i=0;i<g[a].size();i++){ if(b!=g[a][i]){ solve(g[a][i],a); size[a]+=size[g[a][i]]; v++; } } if(v==0)return dp[a]=1LL; int m=size[a]-1; long long ret=1; for(int i=0;i<g[a].size();i++){ if(b!=g[a][i]){ ret=ret*dp[g[a][i]]%mod; } } for(int i=0;i<g[a].size();i++){ if(b!=g[a][i]){ ret=ret*C[m][size[g[a][i]]]%mod; m-=size[g[a][i]]; } } return dp[a]=ret; } int main(){ int a; scanf("%d",&a); C[0][0]=1; for(int i=0;i<1500;i++){ for(int j=0;j<=i;j++){ C[i+1][j]=(C[i+1][j]+C[i][j])%mod; C[i+1][j+1]=(C[i+1][j+1]+C[i][j])%mod; } } for(int i=0;i<a-1;i++){ int b,c; scanf("%d%d",&b,&c); b--;c--; g[b].push_back(c); g[c].push_back(b); } long long ret=0; for(int i=0;i<a;i++){ for(int j=0;j<a;j++)size[j]=0; ret=(ret+solve(i,-1))%mod; } printf("%lld\n",ret*500000004%mod); }
T:
実は台湾で解いてました。
#include<stdio.h> #include<algorithm> using namespace std; int mod=1000000007; struct wolf{ long long d[3000]; wolf(){ for(int i=0;i<3000;i++)d[i]=0; } }; int n,k; wolf Div; wolf solve(int a){ if(a==0){ wolf ret=wolf(); ret.d[0]=1; return ret; } wolf p=solve(a/2); wolf ret=wolf(); for(int i=0;i<k;i++){ for(int j=0;j<k;j++){ ret.d[i+j+(a&1)]=(ret.d[i+j+(a&1)]+p.d[i]*p.d[j]%mod)%mod; } } for(int i=2*k;i>=k;i--){ int val=ret.d[i]; for(int j=0;j<=k;j++){ ret.d[i-j]=(ret.d[i-j]-Div.d[k-j]*val)%mod; if(ret.d[i-j]<0LL)ret.d[i-j]+=mod; } } //printf("%d:",a); //for(int i=0;i<k;i++)printf(" %d",ret.d[i]); //printf("\n"); return ret; } int main(){ scanf("%d%d",&k,&n); for(int i=0;i<k;i++){ Div.d[i]=-1; } Div.d[k]=1; wolf D=solve(n-1); int ret=0; for(int i=0;i<k;i++)ret=(ret+D.d[i])%mod; printf("%d\n",ret); }