Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-13

grafixMask

| 14:18

問題文, SRM 211

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

マスクしていない部分の面積。Flood fill。

351.71/500

class grafixMask {
public:
    vector <int> sortedAreas(vector <string> rectangles) {
        const static int H = 400, W = 600;
        char canvas[H][W];
        memset(canvas, ' ', H*W);
        for (int i = 0; i < rectangles.size(); i++) {
            int r0, c0, r1, c1;
            sscanf(rectangles[i].c_str(), "%d %d %d %d", &r0, &c0, &r1, &c1);
            for (int r = r0; r <= r1; r++)
                for (int c = c0; c <= c1; c++)
                    canvas[r][c] = '#';
        }

        vector<int> areas;
        for (int r = 0; r < H; r++)
            for (int c = 0; c < W; c++) {
                if (canvas[r][c] == '#') continue;
                canvas[r][c] = '#';
                int area = 1;
                queue<pair<int,int> > Q;
                Q.push(make_pair(r, c));
                while (!Q.empty()) {
                    pair<int,int> p(Q.front()); Q.pop();
                    for (int i = 0; i < 4; i++) {
                        const static int d[4][2] = {
                            {1,0}, {-1,0}, {0,1}, {0,-1} };
                        const int nr = p.first + d[i][0];
                        const int nc = p.second + d[i][1];
                        if (0<=nr&&nr<H && 0<=nc&&nc<W && canvas[nr][nc] != '#') {
                            canvas[nr][nc] = '#';
                            Q.push(make_pair(nr,nc));
                            area++;
                        }
                    }
                }
                areas.push_back(area);
            }
        sort(areas.begin(), areas.end());
        return areas;
    }
};

2009-09-10

WalkingHome

| 16:29

問題文, SRM 222

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

学校から家に帰るまでに、最低何回道路を横断すればよいのか。道路は2つまでしか横断できないと勘違いしたために、1回落ちた。

150.00/500 (1 failed)

struct Johnny {
    int y, x, times;
    Johnny() { Johnny(0,0,0); }
    Johnny(const int y, const int x, const int times) :
        y(y), x(x), times(times) {}
};

class WalkingHome {
public:
    int fewestCrossings (vector <string> map) {
        const int H = map.size();
        const int W = map[0].size();
        Q = queue<Johnny>();
        visited = vector<vector<int> >(H, vector<int>(W, INT_MAX));
        int homeY=0, homeX=0;
        for (int y = 0; y < H; y++) {
            // cout << map[y]<< endl;
            for (int x = 0; x < W; x++) {
                if (map[y][x] == 'S') {
                    checkAndPush(Johnny(y,x,0));
                } else if (map[y][x] == 'H') {
                    homeY = y;
                    homeX = x;
                    map[y][x] = '.';
                }
            }
        }

        int result = INT_MAX;
        while (!Q.empty()) {
            Johnny j(Q.front());  Q.pop();
            if (j.y == homeY && j.x == homeX)
                result = min(result, j.times);
            const static int d[4][2] = {
                {1,0}, {-1,0}, {0,1}, {0,-1} };
            for (int i = 0; i < 4; i++) {
                const int ny = j.y + d[i][0];
                const int nx = j.x + d[i][1];
                int nnx, nny;
                if (!(0<=ny&&ny<H && 0<=nx&&nx<W)) continue;
                switch (map[ny][nx]) {
                    case '.':
                        checkAndPush(Johnny(ny,nx,j.times));
                        break;
                    case '|':
                        if (d[i][1] == 0) break;
                        nnx = nx + d[i][1];
                        while (0<=nnx&&nnx<W && map[ny][nnx] == '|')
                            nnx += d[i][1];
                        if (0<=nnx&&nnx<W && map[ny][nnx] == '.')
                            checkAndPush(Johnny(ny,nnx,j.times+1));
                        break;
                    case '-':
                        if (d[i][0] == 0) break;
                        nny = ny + d[i][0];
                        while (0<=nny&&nny<H && map[nny][nx] == '-')
                            nny += d[i][0];
                        if (0<=nny&&nny<H && map[nny][nx] == '.')
                            checkAndPush(Johnny(nny,nx,j.times+1));
                        break;
                }

            }
        }
        if (result == INT_MAX) return -1;
        else return result;
    }
private:
    queue<Johnny> Q;
    vector<vector<int> > visited;
    void checkAndPush(const Johnny& j) {
        if (j.times < visited[j.y][j.x]) {
            Q.push(j);
            visited[j.y][j.x] = j.times;
        }
    }
};

2009-09-06

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];
    }
};

2009-09-05

Jumper

| 19:49

問題文, SRM 158

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

一番上までいくのに何ステップかかるか。BFSで解ける。問題を理解するのに1時間。そして、解法が浮かばなくてEditorialを見ながら解くのに2時間ぐらいかかった。

304.01/1000 (cheated)

struct State {
    int x, y, t;
    State() {}
    State(const int x, const int y, const int t) :
        x(x), y(y), t(t) {}
};
bool operator< (const State& a, const State& b) {
    if (a.t < b.t) {
        return true;
    } else if (a.t > b.t) {
        return false;
    } else {
        if (a.y > b.y) {
            return true;
        } else if (a.y < b.y) {
            return false;
        } else {
            return a.x < b.x;
        }
    }
}

class Jumper {
public:
    int minTime(vector <string> patterns, vector <int> speeds, string rows) {
        const int HEIGHT = rows.size()+1;
        const int WIDTH = 20;
        vector<string> grid(HEIGHT+1);
        grid[0] = grid[HEIGHT] = string(WIDTH, '#');
        for (int i = 0; i < rows.size(); i++) 
            for (int j = 0; j < 4; j++)
                grid[i+1] += patterns[rows[i]-'0'];
        queue<State> Q;
        Q.push(State(0,0,0));
        set<State> checked;
        while (!Q.empty()) {
            State s = Q.front(); Q.pop();
            if (s.t > 2100) break;
            if (s.y >= HEIGHT) return s.t;
            const static int MOVE_KINDS = 5;
            const static int d[MOVE_KINDS][2] = {
                {0,0},{1,0},{-1,0},{0,1},{0,-1} };
            for (int i = 0; i < MOVE_KINDS; i++) {
                const int dx = s.x + d[i][0];
                const int dy = s.y + d[i][1];
                if (0<=dx&&dx<WIDTH && 0<=dy) {
                    int offset = (dy==0||dy==HEIGHT) ? 0 : 
                        (((-s.t*speeds[rows[dy-1]-'0'])%5)+5)%5;
                    if (grid[dy][(dx+offset)%WIDTH] == '#') {
                        const int ddx = dx + ((dy==0||dy==HEIGHT)? 0 :
                                speeds[rows[dy-1]-'0']);
                        if (0<=ddx && ddx<WIDTH) {
                            State next(ddx, dy, s.t+1);
                            if (checked.find(next) == checked.end()) {
                                checked.insert(next);
                                Q.push(next);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
};

TickTick

| 13:04

問題文, SRM 177

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

何種類のイベントの組み合わせができるか。問題の意味がわからなかった。Editorialを読んでようやく理解できた。

122.36/300 (cheated)

class TickTick {
public:
    int count(vector <string> events) {
        vector<double> e; 
        e.push_back(0.0);
        for (int i = 0; i < events.size(); i++) 
            e.push_back(atof(events[i].c_str()));
        set<string> ret;
        for (int i = 0; i < e.size(); i++) {
            double tick = e[i] + 5e-8;
            double prev = DBL_MIN;
            string seq;
            for (int j = 0; j < e.size(); j++) {
                double tickIndex = floor(e[j]-tick);
                if (tickIndex == prev) seq += "S";
                else seq += "D";
                prev = tickIndex;
            }
            ret.insert(seq);
        }
        return ret.size();
    }
};

TallPeople

| 10:33

問題文, SRM 208

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

一番小さい人の中から一番大きい人を選び、一番大きい人の中から一番小さい人を選ぶ。

210.68/250

class TallPeople {
public:
    vector <int> getPeople(vector <string> people) {
        R = people.size();
        ppl = vector<vector<int> >(R);
        for (int i = 0; i < R; i++) {
            istringstream iss(people[i]);
            int t;
            while (iss >> t) ppl[i].push_back(t);
        }
        C = ppl[0].size();

        vector <int> result(2);
        result[0] = tallestOfShortest();
        result[1] = shortestOfTallest();
        return result;
    }
private:
    int R, C;
    vector<vector<int> > ppl;
    int tallestOfShortest() {
        int tallest = INT_MIN;
        for (int i = 0; i < R; i++)
            tallest = max(tallest, 
                    *min_element(ppl[i].begin(),ppl[i].end()));
        return tallest;
    }
    int shortestOfTallest() {
        int shortest = INT_MAX;
        for (int i = 0; i < C; i++) {
            int tallest = INT_MIN;
            for (int j = 0; j < R; j++)
                tallest = max(tallest, ppl[j][i]);
            shortest = min(shortest, tallest);
        }
        return shortest;
    }
};

2009-09-02

MatchMaking

| 13:52

問題文, SRM 203

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

相性のよい組み合わせを作る。

462.48/600

struct Person {
    string name, answer;
    Person() {}
    Person(const string& name, const string& answer) :
        name(name), answer(answer) {}
};

bool operator< (const Person& a, const Person& b) {
    return a.name < b.name;
}

class MatchMaking {
public:
    string makeMatch(vector <string> namesWomen, vector <string> answersWomen, vector <string> namesMen, vector <string> answersMen, string queryWoman) {
        const int numPersons = namesWomen.size();
        const int numAnswers = answersWomen[0].size();
        vector<Person> women, men;
        for (int i = 0; i < numPersons; i++) {
            women.push_back(Person(namesWomen[i], answersWomen[i]));
            men.push_back(Person(namesMen[i], answersMen[i]));
        }
        sort(women.begin(), women.end());
        sort(men.begin(), men.end());

        vector<bool> selected(numPersons, false);
        for (int i = 0; i < numPersons; i++) {
            int maxIdx=0, maxCount=INT_MIN;
            for (int j = 0; j < numPersons; j++) {
                if (selected[j]) continue;
                int count = 0;
                for (int k = 0; k < numAnswers; k++)
                    if (women[i].answer[k] == men[j].answer[k])
                        count++;
                if (count > maxCount) {
                    maxCount = count;
                    maxIdx = j;
                }
            }
            if (women[i].name == queryWoman)
                return men[maxIdx].name;
            selected[maxIdx] = true;
        }
        return "";
    }
};

2009-08-31

StampPads

| 13:51

問題文, SRM 158

欲しい色を全部そろえるには、何種類のスタンプパッドを買えば良いのか。Brute forceで解ける問題だったが、DPで解こうとした。2回タイムアウトで落とされたが、始めにmaskを作る方法に変えたら通った。

150.00/500 (2 failed)

class StampPads {
public:
    int bestCombo(vector <string> pads, vector <string> wishlist) {
        numPads = pads.size();
        pds = vector<vector<string> >(numPads, vector<string>(5));
        for (int i = 0; i < numPads; i++) {
            istringstream iss(pads[i]);
            for (int j = 0; iss >> pds[i][j]; j++) ;
        }
        bitset<32> got;
        numWishes = wishlist.size();
        wishL = wishlist;
        mask = vector<bitset<32> >(numPads);
        for (int i = 0; i < numPads; i++)
            for (int j = 0; j < numWishes; j++)
                mask[i][j] = find(pds[i].begin(),pds[i].end(),wishL[j]) != pds[i].end();
        return go(0, 0, got);
    }
    int numPads;
    vector<vector<string> > pds;
    vector<string> wishL;
    vector<bitset<32> > mask;
    int numWishes;
    int go(const int bought, const int idx, const bitset<32>& got) {
        if (got.count() >= numWishes) return bought;
        if (idx >= numPads) return -1;
        bitset<32> next(got | mask[idx]);
        if (next != got) {
            int retBuy = go(bought+1, idx+1, next);
            int retNot = go(bought, idx+1, got);
            if (retBuy == -1 && retNot == -1) return -1;
            else if (retBuy == -1) return retNot;
            else if (retNot == -1) return retBuy;
            else return min(retBuy, retNot);
        } else {
            return go(bought, idx+1, got);
        }
    }
};

2009-08-30

InstantRunoff

| 17:56

問題文, SRM 175

選挙で、誰が過半数の票を獲得するか。

166.88/550 (1 failed)

class InstantRunoff {
public:
    string outcome(string candidates, vector <string> ballots) {
        const int numCandidates = candidates.size();
        const int numVoters = ballots.size();
        vector<int> idx(numVoters, 0);
        vector<char> failed;
        for (int i = 0; i < numCandidates; ) {
            map<char,int> votes;
            for (int k = 0; k < numCandidates; k++) 
                if (find(failed.begin(),failed.end(),candidates[k]) == failed.end())
                    votes[candidates[k]] = 0;
            for (int j = 0; j < numVoters; j++) {
                while (votes.find(ballots[j][idx[j]]) == votes.end()) idx[j]++;
                votes[ballots[j][idx[j]]]++;
            }
            int minimum = INT_MAX;
            for (map<char,int>::const_iterator v = votes.begin();
                    v != votes.end(); v++) {
                if (v->second > numVoters/2)
                    return string(1,v->first);
                if (v->second < minimum)
                    minimum = v->second;
            }
            for (map<char,int>::const_iterator v = votes.begin();
                    v != votes.end(); v++) {
                if (v->second == minimum) {
                    failed.push_back(v->first);
                    i++;
                    for (int j = 0; j < numVoters; j++) {
                        if (v->first == ballots[j][idx[j]])
                            idx[j]++;
                    }
                }
            }
        }
        return "";
    }
};

Matching

| 16:40

問題文, SRM 176

全て同じか、全て違う。

347.03/500

const static string memory[4][3] = {
    { "CIRCLE", "DIAMOND", "SQUIGGLE" },
    { "BLUE", "GREEN", "RED" },
    { "EMPTY", "SOLID", "STRIPED" },
    { "ONE", "THREE", "TWO" } };
    
class Matching {
public:
    vector <string> findMatch(vector <string> first, vector <string> second) {
        vector<string> third(4);
        for (int i = 0; i < 4; i++) 
            third[i] = getSymbol(first[i], second[i], i);
        return third;
    }
private:
    string getSymbol(string f, string s, const int kind) {
        if (f == s) return f;
        if (f > s) swap(f, s);
        if (f == memory[kind][0]) {
            if (s == memory[kind][1]) return memory[kind][2];
            else return memory[kind][1];
        } else {
            return memory[kind][0];
        }
    }
};

BadClock

| 15:23

問題文, SRM 172

何時間後に2つの時計が同時刻を指すか。

class BadClock {
public:
    double nextAgreement(string trueTime, string skewTime, int hourlyGain) {
        int X = getTime(trueTime);
        int Y = getTime(skewTime);
        if (hourlyGain < 0) {
            hourlyGain = -hourlyGain;
            swap(X, Y);
        }
        while (X < Y) X += 12*60*60;
        return (double) (X - Y) / hourlyGain;
    }
private:
    int getTime(const string& time) {
        int hh, mm, ss;
        sscanf(time.c_str(), "%d:%d:%d", &hh, &mm, &ss);
        return (hh*60 + mm)*60 + ss;
    }
};

Table

| 14:44

問題文, SRM 157

テーブルの形式を変換。

366.23/500

class Table {
public:
    vector <string> layout(vector <string> tbl) {
        const int rows = tbl.size();
        vector <string> result(rows, string(51, '?'));
        for (int r = 0; r < rows; r++) {
            istringstream iss(tbl[r]);
            int colspan, rowspan;
            char content, pad;
            int c = 0;
            while (iss >> pad >> colspan >> pad >> rowspan 
                     >> pad >> content >> pad) {
                while (result[r][c] != '?') c++;
                for (int rr = r; rr < r+rowspan; rr++)
                    for (int cc = c; cc < c+colspan; cc++)
                        result[rr][cc] = content;
                c = c + colspan;
            }
        }
        const int cols = result[0].find("?");
        for (int r = 0; r < rows; r++)
            result[r] = result[r].substr(0, cols);
        return result;
    }
};

MineField

| 11:43

問題文, SRM 169

マインスイーパ。

225.69/250

class MineField {
public:
    vector <string> getMineField(string mineLocations) {
        const static int SIZE = 9;
        vector <string> result(SIZE,string(SIZE,'0'));
        istringstream iss(mineLocations);
        char pad;
        int y, x;
        while (iss >> pad >> y >> pad >> x >> pad)
            result[y][x] = 'M';
        const static int d[8][2] = {
            {-1,-1}, {-1, 0}, {-1, 1},
            { 0,-1},          { 0, 1},
            { 1,-1}, { 1, 0}, { 1, 1} };
        for (y = 0; y < SIZE; y++)
            for (x = 0; x < SIZE; x++) {
                if (result[y][x] == 'M') continue;
                int counter = 0;
                for (int i = 0; i < 8; i++) {
                    int dy = y + d[i][0];
                    int dx = x + d[i][1];
                    if (0<=dy&&dy<SIZE && 0<=dx&&dx<SIZE 
                            && result[dy][dx] == 'M')
                        counter++;
                }
                result[y][x] += counter;
            }
        return result;
    }
};

UserId

| 11:21

問題文, SRM 164

ユーザIDを決める。

207.86/300

class UserId {
public:
    string id(vector <string> inUse, string first, string middle, string last) {
        first = truncate(first);
        middle = truncate(middle);
        last = truncate(last);
        if ((first == "BAD DATA" || middle == "BAD DATA" || last == "BAD DATA") ||
                first.length() < 2 || last.length() < 2)
            return "BAD DATA";

        string candidate = first[0] + last;
        if (candidate.length() > 8) candidate = candidate.substr(0,8);
        if (find(inUse.begin(),inUse.end(),candidate) == inUse.end())
            return candidate;
        if (middle.length() >= 1) {
            candidate = first[0] + string(1,middle[0]) + last;
            if (candidate.length() > 8) candidate = candidate.substr(0,8);
            if (find(inUse.begin(),inUse.end(),candidate) == inUse.end())
                return candidate;
        }
        for (int i = 1; i <= 99; i++) {
            candidate = first[0] + last;
            if (candidate.length() > 6) candidate = candidate.substr(0,6);
            ostringstream oss;
            oss << candidate << setw(2) << setfill('0') << i;
            candidate = oss.str();
            if (find(inUse.begin(),inUse.end(),candidate) == inUse.end())
                return candidate;
        }
        return "BAD DATA";
    }
private:
    string truncate(const string& s) {
        string ret;
        for (int i = 0; i < s.length(); i++) {
            if (isalpha(s[i])) ret += tolower(s[i]);
            else if (s[i] != '\'' && s[i] != ' ') return "BAD DATA";
        }
        return ret;
    }
};

2009-08-29

Rochambo

| 17:09

問題文, SRM 163

じゃんけんの勝数。

157.83/250

class Rochambo {
public:
    int wins(string opponent) {
        int counter = 0;
        for (int i = 0; i < 2 && i < opponent.size(); i++)
            if (isWin('R', opponent[i]))
                counter++;
        for (int i = 2; i < opponent.size(); i++) {
            string pre2 = opponent.substr(i-2, 2);
            char move;
            if (pre2 == "RR") move = 'P';
            else if (pre2 == "SS") move = 'R';
            else if (pre2 == "PP") move = 'S';
            else if (pre2.find("R") == string::npos) move = 'P';
            else if (pre2.find("S") == string::npos) move = 'R';
            else move = 'S';
            if (isWin(move, opponent[i]))
                counter++;
        }
        return counter;
    }
private:
    bool isWin(const char a, const char b) {
        return (a=='R'&&b=='S') || (a=='S'&&b=='P') || (a=='P'&&b=='R');
    }
};

IsHomomorphism

| 16:05

問題文, SRM 161

同じ答えを返すかどうかを調べる。問題の意味がわかりにくいが、わかれば簡単な問題。

196.13/300

class IsHomomorphism {
public:
    vector <string> numBad(vector <string> source, vector <string> target, vector <int> mapping) {
        vector <string> result;
        for (int i = 0; i < source.size(); i++) {
            for (int j = 0; j < source[0].size(); j++) {
                if (mapping[source[i][j]-'0'] != target[mapping[i]][mapping[j]]-'0') {
                    ostringstream oss;
                    oss << "(" << i << "," << j << ")";
                    result.push_back(oss.str());
                }
            }
        }
        return result;
    }
};

QuipuReader

| 14:05

問題文, SRM 155

特殊な数記法で表わされた数を処理。解くのに時間かかり過ぎ。

191.33/450

class QuipuReader {
public:
    vector <int> readKnots(vector <string> knots) {
        const int sz = knots.size();
        const int len = knots[0].length();
        vector<vector<int> > num(sz), start(sz), last(sz);
        for (int i = 0; i < sz; i++) {
            int j = 0;
            while (j < len) {
                while (j < len && knots[i][j] != 'X') j++;
                if (j == len && knots[i][len-1] != 'X') break;
                start[i].push_back(j);
                j++;
                while (j < len && knots[i][j] == 'X') j++;
                num[i].push_back(j-start[i].back());
                last[i].push_back(j-1);
            }
        }

        vector <int> result(sz,0), idx(sz,0);
        int i = 0;
        while (i < len) {
            int s = INT_MAX, l=INT_MAX;
            for (int j = 0; j < sz; j++) {
                if (idx[j] < start[j].size() && start[j][idx[j]] < s) {
                    s = start[j][idx[j]];
                    l = last[j][idx[j]];
                }
            }
            if (s == INT_MAX) break;
            for (int j = 0; j < sz; j++) {
                result[j] *= 10;
                if (idx[j] < start[j].size() &&
                        ((s<=start[j][idx[j]] && last[j][idx[j]]<=l) ||
                        (start[j][idx[j]]<=s && l<=last[j][idx[j]]))) {
                    result[j] += num[j][idx[j]];
                    idx[j]++;
                } 
            }
            i = l + 1;
        }
        return result;
    }
};

Iditarod

| 10:30

問題文, SRM 160

所要時間の平均を求める。

212.31/250

class Iditarod {
public:
    int avgMinutes(vector <string> times) {
        int total = 0;
        for (int i = 0; i < times.size(); i++)
            total += getTime(times[i]);
        return (int)((double) total / times.size() + 0.5);
    }
private:
    int getTime(string& time) {
        int hh, mm, n;
        char apm;
        sscanf(time.c_str(), "%d:%d %cM, DAY %d", &hh, &mm, &apm, &n);
        if (hh == 12) hh = 0;
        if (apm == 'P') hh += 12;
        return 24*(n-1)*60 + hh*60 + mm - 8*60;
    }
};

2009-08-28

Collision

| 13:32

問題文, SRM 153

2つの確率の差を求める。

178.38/450 (cheated)

class Collision {
public:
    double probability(vector <int> assignments, int ids) {
        double p1=1, p2=1;
        int d = ids;
        for (int i = 0; i < assignments.size(); i++) {
            if (assignments[i] > ids) return 0;
            int n = ids;
            for (int j = 0; j < assignments[i]; j++) {
                p1 *= (double) d / ids;
                p2 *= (double) d / n;
                d--; n--;
            }
        }
        return p2 - p1;
    }
};

2009-08-27

FryingHamburgers

| 11:29

問題文, SRM 159

すべてのハンバーガーを焼くのにかかる時間。解けなくて、さんざん悩んで、Editorialを見て、数学の問題だと気づいた。

75.0/250

class FryingHamburgers {
public:
    int howLong(int panSize, int hamburgers) {
        if (hamburgers == 0) return 0;
        if (hamburgers <= panSize) return 10;
        return 5*(int)ceil(2.0*hamburgers/panSize);
    }
};