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