JOI2010-2011予選
順当にいけば満点。ソース掲載(提出したものとは違うやつもある)。
1
joi_yo1 =: 3 : 0 data =. ".' '(I.1-CR I.t)}t=.1!:1<'input.txt' (<.@%&60,|~&60)+/data )
2
joi_yo2 =: 3 : 0 s=.>{.data=.;:' '(I.1-CR I.t)}t=.1!:1<'input.txt' +/>(0&<@+/)@(s&E.@,~)L:0(2}.data) )
3
joi_yo3 =: 3 : 0 n=.".>{.data=.t#~>0&<@+/@('0123456789'&e.)L:0 t=.;:1!:1<'input.txt' t+3*0=t=.>3&|@<./@(-(-&(>:n)@+:*(-:>:n)&<))@".L:0(2}.data) )
4
#include<cstdio> using namespace std; int main() { int n,m[100]; long long dp[100][21]={{0}}; scanf("%d", &n); for(int i=0; i<n; ++i) scanf("%d", &m[i]); dp[0][m[0]]=1; for(int i=1; i<n-1; ++i) { for(int j=0; j<=20; ++j) { if(0<=j+m[i]&&j+m[i]<=20) dp[i][j+m[i]]+=dp[i-1][j]; if(0<=j-m[i]&&j-m[i]<=20) dp[i][j-m[i]]+=dp[i-1][j]; } } printf("%lld\n", dp[n-2][m[n-1]]); return 0; }
5
#include<cstdio> #include<queue> using namespace std; int h, w; char F[1024][1024]; int dist(int x1, int y1, int x2, int y2) { int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; char vis[1024][1024] = {{0}}; queue<pair<int, int> > q; q.push(make_pair(y1*1000+x1, 0)); vis[y1][x1]=1; while(!q.empty()) { int x=q.front().first%1000, y=q.front().first/1000, s=q.front().second; q.pop(); if(x==x2 && y==y2) return s; for(int i=0; i<4; ++i) { int nx=x+dx[i], ny=y+dy[i]; if(nx<0||ny<0) continue; if(nx>=w||ny>=h) continue; if(F[ny][nx]=='X'||vis[ny][nx]) continue; vis[ny][nx]=1; q.push(make_pair(ny*1000+nx,s+1)); } } return 100000000; } int main() { int n, x[10], y[10]; scanf("%d%d%d", &h, &w, &n); for(int i=0; i<h; ++i) { scanf("%s", F[i]); for(int j=0; j<w; ++j) { if(F[i][j]=='S') { x[0]=j; y[0]=i; F[i][j]='.'; } else if('0'<=F[i][j]&&F[i][j]<='9') { x[F[i][j]-'0']=j; y[F[i][j]-'0']=i; F[i][j]='.'; } } } int sol=0; for(int i=0; i<n; ++i) sol+=dist(x[i],y[i],x[i+1],y[i+1]); printf("%d\n", sol); return 0; }
6
#include<cstdio> #include<cstring> using namespace std; const int MOD=100000; struct mint { int x; mint(int x_=0) : x(x_%MOD) { } mint operator+(const mint& o) { return x+o.x; } void operator+=(const mint& o) { x=(x+o.x)%MOD; } }; mint dp[2][1<<20][2]; char F[24][24]; #define ok(x,y,c) (F[y][x]==c || F[y][x]=='?') int main() { int N, M; scanf("%d%d", &N, &M); for(int i=0; i<N; ++i) scanf("%s", F[i]); if(ok(0,0,'J')) dp[0][0][1]+=1; if(ok(0,0,'O')) dp[0][0][0]+=1; if(ok(0,0,'I')) dp[0][0][0]+=1; int p=1, q=0; for(int y=0; y<N; ++y) { if(y > 0) memset(dp[p],0,sizeof(dp[p])); int high = 1<<(M-1); if(y > 0) { for(int m=0; m<(1<<M); ++m) { if(ok(0,y,'J')) dp[p][(m&~high)>>1][1]+=dp[q][m][0]+dp[q][m][1]; if(ok(0,y,'O')) dp[p][(m&~high)>>1][0]+=dp[q][m][0]+dp[q][m][1]; if(ok(0,y,'I') && (m&1)==0) dp[p][(m&~high)>>1][0]+=dp[q][m][0]+dp[q][m][1]; } p=1-p; q=1-q; } for(int x=1; x<M; ++x) { memset(dp[p],0,sizeof(dp[p])); for(int m=0; m<(1<<M); ++m) { if(ok(x,y,'J')) { dp[p][(m&~high)>>1][1]+=dp[q][m][0]+dp[q][m][1]; } if(ok(x,y,'O')) { dp[p][(m&~high)>>1][0]+=dp[q][m][0]; dp[p][(m|high)>>1][0]+=dp[q][m][1]; } if(ok(x,y,'I') && (m&1)==0) { dp[p][(m&~high)>>1][0]+=dp[q][m][0]+dp[q][m][1]; } } p=1-p; q=1-q; } } int sol=1; for(int i=0; i<N; ++i) for(int j=0; j<M; ++j) if(F[i][j]=='?') sol=(sol*3)%MOD; for(int i=0; i<(1<<M); ++i) sol = (sol-dp[q][i][0].x-dp[q][i][1].x+2*MOD)%MOD; printf("%d\n", sol); }