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; } }
これが本番にできればよいのですね. 眠いとか深夜とか明日早いとかいろいろ言い訳はできるんですが.