2009-08 << 2009-09 >> 2009-10

2009-09-04 (金)

*Google Code Jam 2009 (Qualification Round)

昨夜は眠かったので何もせずに寝てしまったのだけど，4時過ぎに目が覚めたのでGoogle Code Jamのサイトを見てみる．

やりたくなったので，とりあえず少しやってみることに．

レギュレーションをよく知らないけど，Qualification Roundは別に全部解く必要はなかった気がする．

A

Largeもそんなに大きくないし，素直に実装．一度目は「Case#」が抜けていて失敗．

大丈夫そうなので，largeもやっておく．一瞬ですね．Perlとかでも良かったかも．

ソース．使ってなかった変数とか消して多少整形しなおしてあります．

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

int match(const string &d, const string &s)
{
    int p=0;
    int L = d.size();
    for (int k=0;k<L;k++) {
        char c = d[k];
        if (s[p]=='(') {
            p++;
            int f=0;
            while(s[p]!=')') {
                if (s[p++]==c) f=1;
            }
            if (f==0) return 0;
        } else if (s[p]!=c) {
            return 0;
        }
        p++;
    }
    return 1;
}

int main()
{
    int L,D,N;

    cin >> L >> D >> N;

    string s;
    vector<string> dic;

    for (int i=0;i<D;i++) {
        cin >> s;
        dic.push_back(s);
    }

    for (int i=0;i<N;i++) {
        cin >> s;
        int count = 0;
        for (int j=0;j<D;j++) {
            count += match(dic[j],s);
        }
        cout << "Case #" << i+1 << ": " << count << endl;
    }

    return 0;
}

B

BとCの問題を読んで，少しCの方が面白そうだけど気力がないのでBを．これも問題のサイズが小さい．何も考えないで良さそう．

今度は出力の後ろに余分なスペースが混入しているのに気付かずに失敗．問題文をかなりいい加減にしか読んでいなかったので，読み間違えたんだろうと思って読み直す．ここで初めて単語の意味とか調べだして，やっぱり間違ってないことを確認．コードもどう見ても間違っていないので，出力ファイルをよく見たらスペースが…．まさかと思って，スペースを出さないようにして再提出．

大丈夫そうなので，largeもやる．これも一瞬で終わりますね．やっぱり速度とか気にする必要はなかった．

#include <iostream>
using namespace std;

int T,H,W;
int map[128][128];
char ans[128][128];
char cc;

void calc(int x,int y) {
    static int dx[] = {0, -1, 1, 0};
    static int dy[] = {-1,0,0,1};
    if (ans[y][x]) return;

    int min = map[y][x], dd = -1;
    for (int d=0;d<4;d++) {
        if (map[y+dy[d]][x+dx[d]] < min) {
            min = map[y+dy[d]][x+dx[d]];
            dd = d;
        }
    }

    if (dd<0) {
        ans[y][x] = cc++;
    } else {
        calc(x+dx[dd],y+dy[dd]);
        ans[y][x] = ans[y+dy[dd]][x+dx[dd]];
    }
}

int main()
{
    cin >> T;

    for (int i=0;i<T;i++) {
        cin >> H >> W;

        for (int j=0;j<=H+1;j++) {
            for (int k=0;k<=W+1;k++) {
                map[j][k] = 999999999;
                ans[j][k] = 0;
            }
        }

        for (int j=1;j<=H;j++) {
            for (int k=1;k<=W;k++) {
                cin >> map[j][k];
            }
        }

        cc = 'a';
        cout << "Case #" << i+1 << ":" <<  endl;
        for (int j=1;j<=H;j++) {
            for (int k=1;k<=W;k++) {
                calc(k,j);
                cout << ans[j][k] << ((k<W)?" ":"");
            }
            cout << endl;
        }
    }
    return 0;
}

Bに時間がかかりすぎた．Cも頭の中ではできていたので，もしかしたらBより楽だったかも．

Cもやりたかったけど，眠いので寝る．睡眠時間が２時間削られてしまったが仕方がない．

結果

朝起きたら，A,Bともに問題なく通っていた．

追記

そもそも，なんで夜中に目が覚めたのかを忘れていたけど思い出した．

WindowsUpdateのせいで，X200が勝手に再起動を始めた音で目が覚めたんだった．そして，再起動後に中ボタンのクリックができなくなっていることに気付いて，トラックポイントのドライバの再インストールをしたら，マウスカーソル自体が消えた．とりあえず，再起動したら治ったけど．

2009-08 << 2009-09 >> 2009-10