読者です 読者をやめる 読者になる 読者になる

天下一プログラマーコンテスト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埋めの効果がありました。みなさんも数え上げやりましょう!