Google Code Jam Qualification Round 2009: 予選会

去年に引き続き今年も参加しました. C の large を落としたので, 76 点.

A - Alien Language

正規表現で一撃で解けるようですが, そんなことには気づかない私は, 全パターンを探索して求める方法をとりました.

単純に全探索すると small ですら通らないので, 辞書のワードの全接頭語も辞書に追加して, 枝刈りする小手先の細工で, large も 49 秒で通りました.

全探索などしなくても, パターンが簡単なので, 辞書のワードそれぞれに対して, 一文字づつ照合すればよいだけだったのでした.

#include <iostream>
#include <vector>

int main() {
  size_t L, D, N;
  std::cin >> L >> D >> N;
  std::vector<std::string> dic(D, std::string());
  for(size_t i = 0; i < D; ++i) {
    std::cin >> dic[i];
  }
  for(size_t i = 1; i <= N; ++i) {
    std::string pattern;
    std::cin >> pattern;
    std::vector<std::string> pv;
    for(size_t index = 0; index < pattern.size();) {
      if('(' == pattern[index]) {
	std::string::size_type endparen = pattern.find(")", index);
	pv.push_back(pattern.substr(index+1, endparen-index-1));
	index = endparen+1;
      } else {
	pv.push_back(pattern.substr(index,1));
	++index;
      }
    }
    
    int total = 0;
    for(size_t d = 0; d < D; ++d) {
      const std::string& word = dic[d];
      bool found = true;
      for(size_t i = 0; i < word.size(); ++i) {
	if(pv[i].find(word[i]) == std::string::npos) {
	  found = false;
	  break;
	}
      }
      if(found) {
	++total;
      }
    }
    std::cout << "Case #" << i << ": " << total << std::endl;
  }
}

アルファベット小文字に限定されているので, 'a' がパターンにあるなら, 1 ビット目をセット, 'b' があるなら, 2 ビット目をセットと言う風にビットパターンにして, 照合をビット演算にすると速く解けます. i 番めの文字パターン列 p[i] をビットパターンにすると

int bitpattern[i] = 0;
for(size_t k = 0; k < p[i].size(); ++k) {
  bitpattern[i] |= 1 << (p[i][k]-'a');
}

辞書内のワード W と照合するには, W[i]&bitpattern[i] が 0 なら照合失敗, 1 なら次の文字の照合に進みます.

#include <iostream>
#include <vector>

int main() {
  size_t L, D, N;
  std::cin >> L >> D >> N;
  std::vector<std::string> dic(D, std::string());
  for(size_t i = 0; i < D; ++i) {
    std::cin >> dic[i];
  }
  for(size_t i = 1; i <= N; ++i) {
    std::string pattern;
    std::cin >> pattern;
    std::vector<unsigned int> pv;
    for(size_t index = 0; index < pattern.size();) {
      if('(' == pattern[index]) {
	std::string::size_type endparen = pattern.find(")", index);
	std::string p = pattern.substr(index+1, endparen-index-1);
	unsigned int x = 0;
	for(size_t k = 0; k < p.size(); ++k) {
	  x |= 1 << (p[k]-'a');
	}
	pv.push_back(x);
	index = endparen+1;
      } else {
	pv.push_back(1 << (pattern[index]-'a'));
	++index;
      }
    }
    
    int total = 0;
    for(size_t d = 0; d < D; ++d) {
      const std::string& word = dic[d];
      bool found = true;
      for(size_t i = 0; i < word.size(); ++i) {
	if(!(pv[i] & (1 << (word[i]-'a')))) {
	  found = false;
	  break;
	}
      }
      if(found) {
	++total;
      }
    }
    std::cout << "Case #" << i << ": " << total << std::endl;
  }
}

B - Watersheds

私にとってはこれが一番簡単でした. 問題読むのが面倒でしたが. 'drainage basins' ってなんぞや, って感じで.

左上のマスから順に, すべてのマスを舐めて, 流れる方向を決めていきます.
次に, すでにラベル付けされているマスはスキップしながら, 左上のマスから順に, 流れる方向をたどって, sink を探します. そして, sink から流れを逆順に辿って, ラベル付けします. 最後にラベルを更新します.

C - Welcome to Code Jam

提出したものは, 再帰で解いたもので, 文章の位置と "welcome to .." の位置のペアをキーにして, その時点での個数をメモしました. 残念ながら large が失敗していました.

ここでは表を用いて解いてみます. T を文章, W を "welcome to code jam" とします.
t を T の長さ, w を W の長さをします.
C[ i ][ j ] を W[ i ], T[ j ] まで見たときの場合の数とします.
W[ i ] == T[ j ] の時, C[ i-1 ][ j-1 ] だけ, 場合の数が増えることになります.
W[ i ] != T[ j ] の時は, 場合の数は増えないので, C[ i ][ j-1 ] までの場合の数と同じになります. これを漸化式にすると,

C[i][j] = C[i][j-1]+C[i-1][j-1] if W[i] == T[j]
          C[i][j-1]             if W[i] != T[j]

i = 0 のときに W[ i ] == T[ j ] となったら, 場合の数が 1 増えるので,

C[0][j] = 1, 0 <= j <= t
C[i][0] = 0, 0 <= i <= w

としておきます. これでプログラムが簡単になります.

あとは, O(W*T) の時間をかけて, C[ w ][ t ] を計算します. C[ w ][ t ] が答えです.

#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>

int main() {
  const std::string W = "welcome to code jam";
  int N;
  std::cin >> N;
  std::string line;
  getline(std::cin, line);
  for(int n = 1; n <= N; ++n) {
    std::string T;
    getline(std::cin, T);

    int C[20][501];

    memset(C, 0, sizeof(C));
    std::fill(&C[0][0], &C[0][501], 1);

    for(size_t i = 1; i <= W.size(); ++i) {
      for(size_t j = 1; j <= T.size(); ++j) {
	C[i][j] = C[i][j-1];
	if(W[i-1] == T[j-1]) {
	  C[i][j] += C[i-1][j-1];
	}
	C[i][j] %= 10000;
      }
    }
    std::cout << "Case #" << n << ": " << std::setfill('0')
	      << std::setw(4) << C[W.size()][T.size()] << std::endl;
  }
}

これが本番にできればよいのですね. 眠いとか深夜とか明日早いとかいろいろ言い訳はできるんですが.