Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-06

CaptureThemAll

| 19:09

問題文, SRM 207

Algorithm Tutorials -- How to Find a Solutionから。

Knightだけで、RookとQueenをとるのに最低何ステップかかるか。BFSで解ける。どのように実装すればよいのかで迷った。1回目と2回目に出したときは、setを使って同じ条件の時にはもう調べないようにしなかったために、queueの許容量を超えてしまい、例外が発生して落ちた(例外が発生しなくても時間制限に引っかかったと思うが)。

300.00/1000 (2 failed)

struct State {
    const static int ROOK_VAL = 1;
    const static int QUEEN_VAL = 10;
    const static int BOTH_VAL = ROOK_VAL+QUEEN_VAL;
    pair<int,int> p;
    int step, val;
    State() {}
    State(const pair<int,int> p) : p(p) {
        step = 0;
        val = 0;
    }
    State(const pair<int,int> p, const int step) : p(p), step(step) {
        val = 0;
    }
};
bool operator< (const State& a, const State& b) {
    if (a.step < b.step) {
        return true;
    } else if (a.step > b.step) {
        return false;
    } else {
        if (a.val > b.val) {
            return true;
        } else if (a.val < b.val) {
            return false;
        } else {
            return a.p < b.p;
        }
    }
}

class CaptureThemAll {
public:
    int fastKnight(string knight, string rook, string queen) {
        const pair<int,int> rPos = getPos(rook);
        const pair<int,int> qPos = getPos(queen);
        queue<State> Q;
        Q.push(State(getPos(knight)));
        set<State> checked;
        checked.insert(Q.front());
        while (!Q.empty()) {
            State k = Q.front(); Q.pop();
            if (k.val == State::BOTH_VAL) return k.step;
            for (int dy = -2; dy <= 2; dy++) {
                for (int dx = -2; dx <= 2; dx++) {
                    if (dy*dy+dx*dx != 5) continue;
                    const int ny = k.p.first + dy;
                    const int nx = k.p.second + dx;
                    if (0<=ny&&ny<BOARD_SZ && 0<=nx&&nx<BOARD_SZ) {
                        State next(make_pair(ny,nx), k.step+1);
                        if (k.val%10 == 1 || next.p == rPos) 
                            next.val += State::ROOK_VAL;
                        if (k.val/10 == 1 || next.p == qPos)
                            next.val += State::QUEEN_VAL;
                        if (checked.find(next) == checked.end()) {
                            Q.push(next);
                            checked.insert(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
private:
    const static int BOARD_SZ = 8;
    pair<int,int> getPos(const string& s) {
        return make_pair(s[1]-'1', s[0]-'a');
    }
};

SmartWordToy

| 16:33

問題文, SRM 233

Algorithm Tutorials -- How to Find a Solutionから。

startからfinishに禁止された文字列を経由するためにかかる変換回数。BFSで解ける。時間制限がきつかった。

157.45/500 (1 failed)

class SmartWordToy {
public:
    int minPresses(string start, string finish, vector <string> forbid) {
        forbids.clear();
        for (int i = 0; i < forbid.size(); i++) {
            istringstream iss(forbid[i]);
            vector<string> token(WORD_LEN);
            for (int j = 0; j < WORD_LEN; j++)
                iss >> token[j];
            generateForbids(0, 0, token);
        }

        queue<pair<int,int> > Q;
        const int startCode = encode(start);
        const int finishCode = encode(finish);
        Q.push(make_pair(startCode, 0));
        set<int> checked;
        checked.insert(startCode);
        while (!Q.empty()) {
            pair<int,int> p = Q.front(); Q.pop();
            if (p.first == finishCode) return p.second;
            for (int i = 0; i < 4; i++) {
                for (int pad = -1; pad <= 1; pad += 2) {
                    int nextCode(next(p.first, pad, i));
                    if (checked.find(nextCode) == checked.end() && 
                            forbids.find(nextCode) == forbids.end()) {
                        checked.insert(nextCode);
                        Q.push(make_pair(nextCode, p.second+1));
                    }
                }
            }
        }
        return -1;
    }
private:
    set<int> forbids;
    const static int WORD_LEN = 4;
    void generateForbids(const int code, const int idx, const vector<string>& token) {
        if (idx == WORD_LEN) {
            forbids.insert(code);
            return;
        }
        for (int i = 0; i < token[idx].size(); i++)
            generateForbids(code*100+token[idx][i]-'a', idx+1, token);
    }
    int encode(const string& s) {
        int code = 0;
        for (int i = 0; i < WORD_LEN; i++)
            code = 100*code + s[i]-'a';
        return code;
    }
    int next(int code, const int pad, const int i) {
        const static int table[5] = {100*100*100*100,100*100*100,100*100,100,1};
        int v = code % table[i] / table[i+1];
        code -= v * table[i+1];
        v = (v+pad+26) % 26;
        code += v * table[i+1];
        return code;
    }
};

MedalTable

| 14:35

問題文, SRM 209

Algorithm Tutorials -- How to Find a Solutionから。

オリンピックで、国ごとのメダル獲得数が多い順に表示。単純な問題なのに、解くのに時間かかりすぎ。

193.53/300

struct Country {
    string name;
    const static int MEDAL_KINDS = 3;
    int medals[MEDAL_KINDS];
    Country() {}
    Country(const string& name) : name(name) {
        for (int i = 0; i < MEDAL_KINDS; i++) medals[i] = 0;
    }
    string getInfo() {
        ostringstream oss;
        oss << name;
        for (int i = 0; i < MEDAL_KINDS; i++) oss << " " << medals[i];
        return oss.str();
    }
};
bool operator< (const Country& a, const Country& b) {
    for (int i = 0; i < Country::MEDAL_KINDS; i++) {
        if (a.medals[i] > b.medals[i]) return true;
        else if (a.medals[i] < b.medals[i]) return false;
    }
    return a.name < b.name;
}

class MedalTable {
public:
    vector <string> generate(vector <string> results) {
        map<string,Country> countries;
        for (int i = 0; i < results.size(); i++) {
            istringstream iss(results[i]);
            for (int j = 0; j < Country::MEDAL_KINDS; j++) {
                string name;
                iss >> name;
                if (countries.find(name) == countries.end()) 
                    countries[name] = Country(name);
                countries[name].medals[j]++; 
            }
        }
        set<Country> countriesSet;
        for (map<string,Country>::const_iterator itr = countries.begin();
                itr != countries.end(); itr++)
            countriesSet.insert(itr->second);
        vector<string> result;
        for (set<Country>::iterator itr = countriesSet.begin();
                itr != countriesSet.end(); itr++) {
            Country c = *itr;
            result.push_back(c.getInfo());
        }
        return result;
    }
};

BusinessTasks

| 09:12

問題文, SRM 236

Algorithm Tutorials -- How to Find a Solutionから。

円形に並べた仕事をn個飛ばしで選んで処理する。Joseph問題の一種。この問題サイズだったらvectorのeraseを使える。書き終わって気づいた。このプログラムにforループはいらなくて、whileループでいい。

238.23/250

class BusinessTasks {
public:
    string getTask(vector <string> list, int n) {
        int p = 0;
        for (int i = 0; list.size() > 1; i++) {
            p = (p + n-1) % list.size();
            p = list.erase(list.begin()+p) - list.begin();
        }
        return list[0];
    }
};