天下一プログラマーコンテスト2013 本戦
5位でした！
A:
ビットDPするだけなので飛ばす。あとから戻ってきて面倒だが書く。
#include<stdio.h> #include<algorithm> using namespace std; int dp[15][15][1<<16]; int mod=1000000007; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<(1<<a);i++){ bool ok=true; for(int j=0;j<a-1;j++){ if((i&(1<<j))&&(i&(1<<(j+1))))ok=false; } if(ok)dp[0][a-1][i*2]=1; } for(int i=1;i<b;i++){ for(int j=0;j<a;j++){ for(int k=0;k<(1<<(a+1));k++){ if((j==0||(!(k&(1<<(a)))&&!(k&1)))&&!(k&2)&&(j==a-1||!(k&4))){ if(j)dp[i][j][k/2+(1<<a)]=(dp[i][j][k/2+(1<<a)]+dp[i][j-1][k])%mod; else dp[i][j][k/2+(1<<a)]=(dp[i][j][k/2+(1<<a)]+dp[i-1][a-1][k])%mod; } if(j)dp[i][j][k/2]=(dp[i][j][k/2]+dp[i][j-1][k])%mod; else dp[i][j][k/2]=(dp[i][j][k/2]+dp[i-1][a-1][k])%mod; } } } int ret=0; for(int i=0;i<(1<<(a+1));i++)ret=(ret+dp[b-1][a-1][i])%mod; printf("%d\n",(ret+mod-1)%mod); }
B:
よんでません
C:
実装する。こういう複雑なのは難しい…forループで2重にjを使っていてバグっていて大変でした。
156点。
#include<stdio.h> #include<algorithm> using namespace std; int d[64][4]; int type[64]; int ans[8][8]; int trn[8][8]; int used[64]; int dx[]={0,1,0,-1,0}; int dy[]={1,0,-1,0,0}; char str[10]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<a*b;i++){ for(int j=0;j<4;j++)scanf("%d",&d[i][j]); } for(int i=0;i<a*b;i++){ for(int j=0;j<4;j++){ if(d[i][j])type[i]++; } } for(int i=0;i<8;i++) for(int j=0;j<8;j++) ans[i][j]=-1; int row=0; int col=1; for(int i=0;i<a*b;i++){ if(type[i]==2){ used[i]=1; for(int j=0;j<4;j++){ if(d[i][(j+2)&3]==0&&d[i][(j+3)&3]==0){ ans[0][0]=i; trn[0][0]=j; break; } } break; } } int dd=0; int width=0; for(int i=1;i<a+b+a+b;i++){ for(int j=0;j<a*b;j++){ if(type[j]<4&&!used[j]){ for(int k=0;k<4;k++){ if(d[j][(k+dd)&3]==0&&d[j][(k+dd+3)&3]!=0&&d[ans[row-dx[dd]][col-dy[dd]]][(trn[row-dx[dd]][col-dy[dd]]+dd)%4]+d[j][(k+dd+3)%4]==3){ printf("? %d %d %d %d\n",ans[row-dx[dd]][col-dy[dd]]+1,(trn[row-dx[dd]][col-dy[dd]]+dd)%4+1,j+1,(k+dd+3)%4+1); fflush(stdout); scanf("%s",str); if(str[0]=='y'){ ans[row][col]=j; used[j]=1; trn[row][col]=(k+1)%4; if(type[j]==2){ dd++; if(!width)width=i+1; } break; } } } if(~ans[row][col])break; } } row+=dx[dd]; col+=dy[dd]; } int height=a*b/width; for(int i=1;i<height-1;i++){ for(int j=1;j<width-1;j++){ for(int k=0;k<a*b;k++){ if(!used[k]){ for(int l=0;l<4;l++){ if(d[ans[i][j-1]][(trn[i][j-1])%4]+d[k][(l+2)%4]!=3)continue; if(d[ans[i-1][j]][(trn[i-1][j]+1)%4]+d[k][(l+3)%4]!=3)continue; printf("? %d %d %d %d\n",ans[i][j-1]+1,(trn[i][j-1])%4+1,k+1,(l+2)%4+1); fflush(stdout); scanf("%s",str); if(str[0]=='y'){ ans[i][j]=k; used[k]=1; trn[i][j]=l; break; } } } } } } if(width==b){ printf("!\n"); for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ printf("%d %d ",ans[i][j]+1,(5-trn[i][j])%4+1); } printf("\n"); } }else{ printf("!\n"); for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ printf("%d %d ",ans[b-1-j][i]+1,(6-trn[b-1-j][i])%4+1); } printf("\n"); } } }
D:
包除でDPするだけ。最初に解いたらFAでした。
#include<stdio.h> #include<algorithm> using namespace std; int c[30]; long long dp[31][31][901]; long long C[1000][1000]; long long inv[1000]; int mod=1000000007; int M; long long Com(int a,int b){ // M-a C b if(C[a][b]>=0LL)return C[a][b]; long long ret=1LL; for(int i=0;i<b;i++){ ret=ret*(M-a-i)%mod*inv[i+1]%mod; } return C[a][b]=ret; } int main(){ int a,b; scanf("%d%d",&a,&b); M=b; inv[1]=1LL; for(int i=2;i<1000;i++){ inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod; } for(int i=0;i<1000;i++){ for(int j=0;j<1000;j++){ C[i][j]=-1LL; } } for(int i=0;i<a;i++)scanf("%d",c+i); int ch=0; for(int i=0;i<a;i++){ ch+=c[i]; } if(ch>b){ printf("0\n"); return 0; } dp[0][0][0]=1LL; for(int i=0;i<a;i++){ for(int j=0;j<=a;j++){ for(int k=0;k<=a*30;k++){ if(!dp[i][j][k])continue; dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod; for(int l=0;l<c[i];l++){ dp[i+1][j+1][k+l]=(dp[i+1][j+1][k+l]+dp[i][j][k]*Com(k,l))%mod; } } } } long long ret=0LL; for(int i=0;i<a;i++){ for(int j=0;j<=a*30;j++){ long long v=a-i; long long si=b-j; long long val=1LL; while(si){ if(si%2){ val=val*v%mod; } v=v*v%mod; si/=2; } val=val*dp[a][i][j]%mod; if(i%2)ret=(ret+mod-val)%mod; else ret=(ret+val)%mod; } } printf("%lld\n",ret); }
E:
60点はsetでDPです。
結果は5位。まあセットの運のおかげでした。iwiさんとは20点差でBかEの部分点で抜かせたので、残念といったら残念だが…
Dは、連日のCF埋めの効果がありました。みなさんも数え上げやりましょう！
