情オリ予選

たぶん116点。凡ミスで4点落とすのはもう嫌だお……。

というか2でミスったの俺だけだろ……。

5問目

#include<cstdio>

using namespace std;

int dp[100][100][2];

int main()
{
  for(int i=0; i<100; ++i) {
    dp[i][0][0] = 1;
    dp[0][i][1] = 1;
  }
  for(int i=1; i<100; ++i) {
    dp[i][1][0] = dp[i][1][1] = 1;
    dp[1][i][0] = dp[1][i][1] = 1;
  }
  for(int i=2; i<100; ++i) {
    for(int j=2; j<100; ++j) {
      dp[i][j][0] = dp[i-2][j][0] + dp[i-2][j-1][1] + dp[i-1][j-1][1];
      dp[i][j][1] = dp[i][j-2][1] + dp[i-1][j-2][0] + dp[i-1][j-1][0];
      dp[i][j][0] %= 100000;
      dp[i][j][1] %= 100000;
    }
  }
  int n, m;
  scanf("%d%d", &n, &m);
  printf("%d\n", (dp[n-1][m-1][0]+dp[n-1][m-1][1])%100000);
}

6問目

汚い

#include<cstdio>
#include<vector>
#include<cstring>

using namespace std;

int m, n, f[10][10], house, hid[10][10], sx, sy;
vector<int> hx[10], hy[10];
vector<int> xx, yy;
int memo[23][1<<23];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int dfs(int hn, int hu)
{
  if(memo[hn][hu] >= 0) return memo[hn][hu];
  int x = xx[hn], y = yy[hn];
  if(hu == 0) {
    if(x == sx) {
      int dy = y > sy ? -1 : 1;
      while(y < n && y >= 0) { 
	y += dy;
	if(f[y][x] == 2) return 1;
	if(f[y][x] == 3) return 0;
      }
    } else if(y == sy) {
      int dx = x > sx ? -1 : 1;
      while(x < m && x >= 0) {
	x += dx;
	if(f[y][x] == 2) return 1;
	if(f[y][x] == 3) return 0;
      }
    }
    return 0;
  }
  memo[hn][hu] = 0;
  for(int i=0; i<4; ++i) {
    int tx = x+dx[i], ty = y+dy[i];
    while(tx >= 0 && ty >= 0 && tx < m && ty < n) {
      if(f[ty][tx] == 3) break;
      if(f[ty][tx] == 1) {
	int hi = hid[ty][tx];
	f[ty][tx] = 3;
	memo[hn][hu] += dfs(hi, hu ^ (1 << hi));
	f[ty][tx] = 1;
      }
      tx += dx[i], ty += dy[i];
    }
  }
  return memo[hn][hu];
}

int main()
{
  scanf("%d%d", &m, &n);
  for(int i=0; i<n; ++i)
    for(int j=0; j<m; ++j)
      scanf("%d", &f[i][j]);
  for(int i=0; i<n; ++i)
    for(int j=0; j<m; ++j)
      if(f[i][j] == 1) {
	xx.push_back(j);
	yy.push_back(i);
	hid[i][j] = house++;
	hx[j].push_back(i);
	hy[i].push_back(j);
      }
      else if(f[i][j] == 2) sx = j, sy = i;
  int sol = 0, mm = (1<<house)-1;
  memset(memo, -1, sizeof(memo));
  for(int i=0; i<hy[sy].size(); ++i) {
    f[sy][hy[sy][i]] = 3;
    sol += dfs(hid[sy][hy[sy][i]], mm ^ (1 << hid[sy][hy[sy][i]]));
    f[sy][hy[sy][i]] = 1;
  }
  for(int i=0; i<hx[sx].size(); ++i) {
    f[hx[sx][i]][sx] = 3;
    sol += dfs(hid[hx[sx][i]][sx], mm ^ (1 << hid[hx[sx][i]][sx]));
    f[hx[sx][i]][sx] = 1;
  }
  printf("%d\n", sol);
}