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