Google Code Jam 1B

基本的に提出したままのコード．解答途中に書いて消しそびれた部分も残ってる．

Problem A - File Fix-it の解答例

mkdirの初期値が-1になっているのは"/"を初期ディレクトリ・リストに入れていなかったせい．あとこのコードだと毎回リストにあるかチェックしているけど，setでチェックされるので初期リスト作成直後と，全追加後の pre_dir.size()　の差を取るだけで十分なはず．

#include <iostream>
#include <string>
#include <set>
using namespace std;

int solve()
{
  int N, M;
  cin >> N >> M;
  set<string> pre_dir;
  for( int i = 0 ; i < N ; ++i ) {
    string dir;
    cin >> dir;
    pre_dir.insert(dir);
  }
  int mkdir = -1;
  for( int i = 0 ; i < M ; ++i ) {
    string dir;
    cin >> dir;
    dir += "/";
    int id = dir.size();
    while( (id = dir.find_last_of('/')) != string::npos ) {
      dir[id] = '\0';
      string ndir(dir.c_str());
      if( pre_dir.find(ndir) == pre_dir.end() ) {
        ++mkdir;
        pre_dir.insert(ndir);
      }
    }
  }
  return mkdir;
}

int main(void)
{
  int T;
  cin >> T;
  for( int i = 1 ; i <= T ; ++i ) {
    cerr << "Case #" << i << "\n";
    cout << "Case #" << i << ": " << solve() << "\n";
  }
  return 0;
}

Problem B - Picking Up Chicks の解答例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solve()
{
  int N, K, B, T;
  cin >> N >> K >> B >> T;
  vector<int> x(N), v(N);
  for( int i = 0 ; i < N ; ++i ) cin >> x[i];
  for( int i = 0 ; i < N ; ++i ) cin >> v[i];

  int nSwap = 0, nOK = 0;
  vector<int>::iterator px, pv, qx, qv;
  reverse(x.begin(), x.end());
  reverse(v.begin(), v.end());
  for( int i = 0 ; i < N && nOK < K ; ++i ) {
    if( x[i] + v[i] * T >= B ) {
      nSwap += i - nOK;
      ++nOK;
    }
  }
  if( nOK < K ) return -1;

  return nSwap;
}

int main(void)
{
  int C;
  cin >> C;
  for( int i = 1 ; i <= C ; ++i ) {
    cerr << "Case #" << i << "\n";
    int r = solve();
    if( r >= 0 ) {
      cout << "Case #" << i << ": " << r << "\n";
    } else {
      cout << "Case #" << i << ": IMPOSSIBLE\n";
    }
  }
  return 0;
}

Problem C - Your Rank is Pure の解答例

largeサイズはRejectされたので修正．100003²≧32bitだったせいでアウトだったので15行目の

  ret = (ret + (long long)tmp[k][i] * cmb[n-k-1][k-i-1]) % MOD;

このキャストを入れれば通ったのです．気づいたのは競技終わっての帰り道．残念．

#include <iostream>
using namespace std;

const int MOD = 100003;
int ans[501];

void init(void)
{
  int cmb[501][501];
  int tmp[501][501];
  cmb[0][0] = 1;
  for( int n = 1 ; n <= 500 ; ++n ) {
    cmb[n][0] = cmb[n][n] = 1;
    for( int k = 1 ; k < n ; ++k ) {
      cmb[n][k] = (cmb[n-1][k] + cmb[n-1][k-1]) % MOD;
    }
  }
  for( int n = 2 ; n <= 500 ; ++n ) {
    tmp[n][1] = tmp[n][2] = 1;
    for( int k = 3 ; k < n ; ++k ) {
      int ret = 0;
      for( int i = k - 1 ; i >= 2 * k - n && i >= 1 ; --i ) {
        ret = (ret + (long long)tmp[k][i] * cmb[n-k-1][k-i-1]) % MOD;
      }
      tmp[n][k] = ret;
    }
    tmp[n][n] = 0;
  }

  for( int i = 2 ; i <= 500 ; ++i ) {
    int ret = 0;
    for( int j = 1 ; j < i ; ++j ) {
      ret = (ret + tmp[i][j]) % MOD;
    }
    ans[i] = ret;
  }
}

int main(void)
{
  int T;
  cin >> T;
  init();
  for( int i = 1 ; i <= T ; ++i ) {
    int n;
    cin >> n;
    cerr << "Case #" << i << "\n";
    cout << "Case #" << i << ": " << ans[n] << "\n";
  }
  return 0;
}