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);
}