Google Code Jam 2009 - Qualification Round

Code Jam - Google’s Coding Competitions
参戦記録として書いておく。
結果は約1時間半で全問解けて、65位。それぞれ30分ぐらいずつかかった。出だし好調と言える結果だが、全問解いた方は約2400人もいる。Round 1の合計通過人数が3000人なので、Round 1を通過するだけでも大変そうだ。

以下、適当な解説と書いたプログラムのソースコード。

Problem A. Alien Language

宇宙人のメッセージを解読。簡単な正規表現。実際、正規表現をサポートしている言語を使って問題を解いた参加者もいたみたいだ。僕は、メッセージの一文字ごとの候補を作り、それをwordの文字と比較して、表現できるかどうかを調べた。

#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <cstdio>
using namespace std;

int main(void)
{
    int L, D, N;
    string line;
    getline(cin, line);
    istringstream iss(line);
    iss >> L >> D >> N;

    set<string> words;
    while (D-- > 0) {
        getline(cin, line);
        words.insert(line);
    }

    for (int caseNo = 1; caseNo <= N; caseNo++) {
        getline(cin, line);
        istringstream iss2(line);
        vector<string> token(L, "");
        bool isInPara = false;
        char c;
        int i = 0;
        while (iss2 >> c) {
            if (c == '(') {
                isInPara = true;
            } else if (c == ')') {
                isInPara = false;
                i++;
            } else if (isInPara) {
                token[i] += string(1,c);
            } else {
                token[i] = string(1,c);
                i++;
            }
        }

        int K = 0;
        for (set<string>::const_iterator wd = words.begin();
                wd != words.end(); wd++) {
            for (int i = 0; i < L; i++) {
                if (token[i].find((*wd)[i]) == string::npos)
                    break;
                if (i == L-1) {
                    K++;
                    break;
                }
            }
        }

        printf("Case #%d: %d\n", caseNo, K);
    }

    return 0;
}

Problem B. Watersheds

どこに水がたまるか。シミュレーション。再帰で解いた。1回調べたマスはもう調べないようにして計算量を削減した。

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

int H, W;
vector<vector<int> > basin;
vector<vector<char> > sink;

char go(const int y, const int x, const char label) 
{
    static int d[4][2] = {
        {-1, 0}, { 0,-1}, { 0, 1}, { 1, 0} };
    if (sink[y][x] != '?') return sink[y][x];
    int lowest = -1;
    int lowestApptitude = INT_MAX;
    for (int i = 0; i < 4; i++) {
        const int dy = y + d[i][0];
        const int dx = x + d[i][1];
        if (0<=dy&&dy<H && 0<=dx&&dx<W
                && basin[dy][dx] < lowestApptitude 
                && basin[dy][dx] < basin[y][x]) {
            lowest = i;
            lowestApptitude = basin[dy][dx];
        }
    }
    if (lowest == -1) {
        sink[y][x] = label;
    } else {
        sink[y][x] = go(y+d[lowest][0],x+d[lowest][1],label);
    }
    return sink[y][x];
}

int main(void)
{
    int T;
    cin >> T;
    for (int caseNo = 1; caseNo <= T; caseNo++) {
        cin >> H >> W;
        basin = vector<vector<int> >(H, vector<int>(W));
        sink = vector<vector<char> >(H, vector<char>(W,'?'));
        for (int y = 0; y < H; y++)
            for (int x = 0; x < W; x++)
                cin >> basin[y][x];

        char label = 'a';
        for (int y = 0; y < H; y++) 
            for (int x = 0; x < W; x++)
                if (sink[y][x] == '?') {
                    if (go(y, x, label) == label)
                        label++;
                }

        printf("Case #%d:\n", caseNo);
        for (int y = 0; y < H; y++)
            for (int x = 0; x < W; x++) {
                cout << sink[y][x];
                if (x == W-1) cout << endl;
                else cout << " ";
            }
    }

    return 0;
}

Problem C. Welcome to Code Jam

文字列中に"welcome to code jam"が何個隠れているかを数える。入力例があまり親切とは言えなく、どういう問題だと解釈すればいいのか迷った。通ったので解釈はあっていたのだと思う。だけど、このプログラム、余計な処理を行っている気がする。気が向いたら削れるかどうかを考える。

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

int main(void)
{
    string line;
    getline(cin, line);
    int N;
    istringstream(line) >> N;
    const string message = "welcome to code jam";
    const int mesLen = message.length();
    for (int caseNo = 1; caseNo <= N; caseNo++) {
        int counter = 0;
        getline(cin, line);
        const int lineLen = line.length();
        vector<vector<int> > memo(lineLen,vector<int>(mesLen,0));
        for (int i = 0; i < lineLen; i++)
            if (line[i] == message[0])
                memo[i][0] = 1;
        for (int i = 0; i < lineLen; i++) {
            for (int j = mesLen-1; j > 0; j--) {
                if (line[i] != message[j]) continue;
                for (int k = 0; k < i; k++)
                    memo[i][j] += memo[k][j-1];
                memo[i][j] %= 10000;
            }
        }
        for (int i = 0; i < lineLen; i++) {
            counter += memo[i][mesLen-1];
            counter %= 10000;
        }
        printf("Case #%d: %04d\n", caseNo, counter);
    }

    return 0;
}