Revenge of JOI2011 予選

選手時代の参加記はここです

スクリーンキャストをしようと思ったので、4年前に解いたセットをもう一度といてみました。

スクリーンキャストはここです

前回に比べて6の方針がすっきりしたと思います。

1: (01:28)

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int a,b,c,d,e;
	scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
	printf("%d\n",min(a,min(b,c))+min(d,e)-50);
}

2: (04:32)

#include<stdio.h>
#include<algorithm>
using namespace std;
int p[200];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<(a*(a-1)/2);i++){
		int b,c,d,e;
		scanf("%d%d%d%d",&b,&c,&d,&e);
		b--;c--;
		if(d>e)p[b]+=3;
		else if(e>d)p[c]+=3;
		else {p[b]++;p[c]++;}
	}
	for(int i=0;i<a;i++){
		int num=1;
		for(int j=0;j<a;j++){
			if(p[j]>p[i])num++;
		}
		printf("%d\n",num);
	}
}

3: (07:38)

#include<stdio.h>
#include<algorithm>
using namespace std;
int e[1100];
int main(){
	int a;scanf("%d",&a);
	int b,c;scanf("%d%d",&b,&c);
	int d;scanf("%d",&d);
	for(int i=0;i<a;i++){
		scanf("%d",e+i);
	}
	std::sort(e,e+a);
	int ret=d/b;
	int now=d;
	int cost=b;
	for(int i=a-1;i>=0;i--){
		now+=e[i];
		cost+=c;
		ret=max(ret,now/cost);
	}
	printf("%d\n",ret);
}

4: (12:02)

#include<stdio.h>
#include<algorithm>
using namespace std;
int mod=10000;
int dp[110][3][3];
int p[110];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<110;i++)p[i]=-1;
	for(int i=0;i<b;i++){
		int s,t;scanf("%d%d",&s,&t);
		s--;t--;
		p[s]=t;
	}
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(p[0]!=-1&&p[0]!=i)continue;
			if(p[1]!=-1&&p[1]!=j)continue;
			dp[2][i][j]=1;
		}
	}
	for(int i=2;i<a;i++){
		for(int j=0;j<3;j++)for(int k=0;k<3;k++)for(int l=0;l<3;l++){
			if(j==k&&k==l)continue;
			if(p[i]!=-1&&l!=p[i])continue;
			dp[i+1][k][l]=(dp[i+1][k][l]+dp[i][j][k])%mod;
		}
	}
	int ret=0;
	for(int i=0;i<3;i++)for(int j=0;j<3;j++){
		ret=(ret+dp[a][i][j])%mod;
	}
	printf("%d\n",ret);
}

5: (21:36)

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int c[1100][1100];
int bfs[1100][1100];
int dx[2][6]={{-1,0,1,1,0,-1},{0,1,1,0,-1,-1}};
int dy[2][6]={{0,1,0,-1,-1,-1},{1,1,0,-1,0,1}};
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++)for(int j=0;j<a;j++){
		scanf("%d",&c[i+1][j+1]);
	}
	queue<pair<int,int> > Q;
	Q.push(make_pair(0,0));
	while(Q.size()){
		int row=Q.front().first;
		int col=Q.front().second;
		Q.pop();
		for(int i=0;i<6;i++){
			int tr=row+dx[row%2][i];
			int tc=col+dy[row%2][i];
			if(tr<0||tc<0||tr>=b+2||tc>=a+2)continue;
			if(c[tr][tc])continue;
			if(bfs[tr][tc])continue;
			bfs[tr][tc]=1;
			Q.push(make_pair(tr,tc));
		}
	}
	//for(int i=1;i<=b;i++){
	//	for(int j=1;j<=a;j++)printf("%d ",bfs[i][j]);
	//	printf("\n");
	//}
	int ret=0;
	for(int i=1;i<=b;i++){
		for(int j=1;j<=a;j++){
			if(!c[i][j])continue;
			for(int k=0;k<6;k++){
				int tr=i+dx[i%2][k];
				int tc=j+dy[i%2][k];
				if(bfs[tr][tc])ret++;
			}
		}
	}
	printf("%d\n",ret);
}

6: (40:16) +2 MLE

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
char A[1100];
char B[1100];
int mod=10000;
short int dp[2][520][3][11][11];
char tc[1100];
int c;
int calc(){
	int n=strlen(tc);
	for(int i=0;i<2;i++)for(int j=0;j<520;j++)for(int k=0;k<3;k++)
		for(int l=0;l<11;l++)for(int m=0;m<11;m++)
			dp[i][j][k][l][m]=0;
	dp[0][0][1][10][10]=1;
	int ret=0;
	for(int i=0;i<n;i++){
		int t=i%2;
		for(int j=0;j<520;j++)for(int k=0;k<3;k++)
		for(int l=0;l<11;l++)for(int m=0;m<11;m++)
			dp[!t][j][k][l][m]=0;
		for(int j=0;j<c;j++){
			for(int k=0;k<3;k++)for(int l=0;l<11;l++)for(int m=0;m<11;m++){
				if(!dp[t][j][k][l][m])continue;
				for(int n=0;n<10;n++){
					if(i==0&&n==0)continue;
					if(m==n)continue;
					int tm=(j*10+n)%c;
					int tk=k;
					if(tk==1&&n<tc[i]-'0')tk=0;
					if(tk==1&&n>tc[i]-'0')tk=2;
					if(l<10&&m<10&&(l-m)*(n-m)<=0)continue;
					dp[!t][tm][tk][m][n]=(dp[!t][tm][tk][m][n]+dp[t][j][k][l][m])%mod;
				}
			}
		}
		for(int j=0;j<3;j++){
			for(int k=0;k<11;k++)for(int l=0;l<11;l++){
				if(i+1==n&&j==2)continue;
				ret=(ret+dp[!t][0][j][k][l])%mod;
			}
		}
	}
	return ret;
}
int main(){
	scanf("%s%s",A,B);
	scanf("%d",&c);
	for(int i=0;i<1100;i++)tc[i]=B[i];
	int ret=calc();
	for(int i=0;i<1100;i++)tc[i]=A[i];
	ret=(ret+mod-calc())%mod;
	int now=0;
	bool ok=true;
	for(int i=0;A[i];i++){
		now*=10;
		now+=A[i]-'0';
		now%=c;
		if(i>=1&&A[i]==A[i-1])ok=false;
		if(i>=2&&(A[i]-A[i-1])*(A[i-2]-A[i-1])<=0){
			ok=false;
		}
	}
	if(ok&&now==0)ret=(ret+1)%mod;
	printf("%d\n",ret);
}