JOI予選

http://www.ioi-jp.org/joi/2010/2011-yo-prob_and_sol/index.html
問いてみた．

1 Total Time

足して割るだけ

int main()
{
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  const int sec = a+b+c+d;
  cout << sec/60 << endl;
  cout << sec%60 << endl;
  return 0;
}

2 Ring

やるだけ．指輪の長さが10固定で，探したい文字列の長さが10以下なので2つ繋げて探すだけでもよさそう．

bool check(const string& key, const string& s)
{
  const int key_len = key.size();
  const int s_len = s.size();
  for (int i = 0; i < s_len; i++) {
    for (int j = 0; j < key_len; j++) {
      if (key[j] != s[(i+j)%s_len]) {
        goto FAIL;
      }
    }
    return true;
FAIL:
    ;
  }
  return false;
}

int main()
{
  string key;
  int N;
  cin >> key >> N;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    if (check(key, s)) {
      ++ans;
    }
  }
  cout << ans << endl;
  return 0;
}

3 Tile

対称性からとりあえず左上の領域に点を移して考えて，a, b の小さいほうの3の剰余で判断．

int main()
{
  int N, K;
  cin >> N >> K;
  for (int i = 0; i < K; i++) {
    int a, b;
    cin >> a >> b;
    --a;  --b;
    a = min(a, N-a-1);
    b = min(b, N-b-1);
    if (b <= a) {
      cout << (b%3)+1 << endl;
    } else {
      cout << (a%3)+1 << endl;
    }
  }
  return 0;
}

4 A First Grader

まず 2^N を考えたけど N ≦ 100 なので無理．ちょっとしてから DP に気付く．これくらいならすぐ気付いて書けるようにしたい…

int main()
{
  int N;
  cin >> N;
  vector<int> v(N);
  for (int i = 0; i < N; i++) {
    cin >> v[i];
  }

  vector<vector<long long> > dp(N-1, vector<long long>(21, 0));
  dp[0][v[0]] = 1;
  for (int i = 1; i < N-1; i++) {
    for (int j = 0; j <= 20; j++) {
      const int add = j + v[i];
      if (add <= 20) {
        dp[i][add] += dp[i-1][j];
      }
      const int sub = j - v[i];
      if (0 <= sub) {
        dp[i][sub] += dp[i-1][j];
      }
    }
  }
  cout << dp[N-2][v.back()] << endl;
  return 0;
}

5 Cheese

一見何通りかチーズ工場を巡る順番があるように思えるけど，よく読むと1から小さい順に巡るしかない．
N回BFSするだけ．

struct P {
  int i, j;
  P() {}
  P(int i_, int j_) : i(i_), j(j_) {}
  bool operator==(const P& rhs) const
  {
    return i == rhs.i && j == rhs.j;
  }
};

int bfs(const vector<string>& grid, const P& start, const P& goal)
{
  const int H = grid.size();
  const int W = grid[0].size();
  queue<pair<int, P> > q;
  q.push(make_pair(0, start));
  vector<vector<bool> > visited(H, vector<bool>(W, false));
  visited[start.i][start.j] = true;
  while (!q.empty()) {
    const pair<int,P> p = q.front();
    q.pop();
    if (p.second == goal) {
      return p.first;
    }
    for (int d = 0; d < 4; d++) {
      static const int di[] = {-1, 1, 0, 0};
      static const int dj[] = {0, 0, -1, 1};
      const P t = P(p.second.i + di[d], p.second.j + dj[d]);
      if (0 <= t.i && t.i < H && 0 <= t.j && t.j < W
          && grid[t.i][t.j] != 'X'
          && !visited[t.i][t.j]) {
        q.push(make_pair(p.first+1, t));
        visited[t.i][t.j] = true;
      }
    }
  }
  return -1;
}

int main()
{
  int H, W, N;
  cin >> H >> W >> N;
  vector<string> grid(H);
  vector<P> points(N+1);
  for (int i = 0; i < H; i++) {
    cin >> grid[i];
    for (int j = 0; j < W; j++) {
      if (grid[i][j] == 'S') {
        points[0] = P(i, j);
      } else if ('1' <= grid[i][j] && grid[i][j] <= '9') {
        points[grid[i][j]-'0'] = P(i, j);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans += bfs(grid, points[i], points[i+1]);
  }
  cout << ans << endl;
  return 0;
}

6 JOI Flag

わからん…