Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-04

SMBus

| 12:55

問題文

バスの調停のシミュレーション。

class SMBus {
    public:
        int transmitTime(vector <string> messages, vector <int> times) {
            const int size = messages.size();
            vector<bool> transmitted(size, false);
            int totalTime = 0;
            for (int i = 0; i < size; i++) {
                list<int> candidates;
                for (int j = 0; j < size; j++) {
                    if (!transmitted[j]) candidates.push_back(j);
                }
                int idx = 0;
                while (candidates.size() > 1) {
                    int slowest = INT_MIN;
                    char smallest = '9'+1;
                    for (list<int>::const_iterator itr = candidates.begin(); 
                            itr != candidates.end(); itr++) {
                        if (messages[*itr].length() > idx) {
                            slowest = max(slowest, times[*itr]);
                            smallest = min(smallest, messages[*itr][idx]);
                        }
                    }
                    for (list<int>::iterator itr = candidates.begin();
                            itr != candidates.end(); ) {
                        if (messages[*itr][idx] > smallest) {
                            itr = candidates.erase(itr);
                        } else {
                            itr++;
                        }
                    }
                    totalTime += slowest;
                    idx++;
                }
                const int winner = *candidates.begin();
                totalTime += (messages[winner].length()-idx) * times[winner];
                transmitted[winner] = true;
            }

            return totalTime;
        }
};

PaperFold

| 18:43

問題文

8回以下の回数だけ紙を折ることで、箱にその紙を納められるか。

class PaperFold {
    public:
        int numFolds(vector <int> paper, vector <int> box) {
            box.push_back(0);
            queue<vector<int> > Q;
            Q.push(box);
            while (!Q.empty()) {
                vector<int> b = Q.front(); Q.pop();
                if (b[2] > 8) continue;
                if (isFit(paper, b)) return b[2];
                b[2]++;
                b[0] *= 2; Q.push(b);
                b[0] /= 2; b[1] *= 2; Q.push(b);
            }
            return -1;
        }
    private:
        bool isFit(const vector<int>& paper, const vector<int>& box) {
            return (paper[0] <= box[0] && paper[1] <= box[1]) ||
                (paper[0] <= box[1] && paper[1] <= box[0]);
        }
};

LCMRange

| 18:43

問題文

最小公倍数の問題。

class LCMRange {
    public:
        int lcm(int first, int last) {
            int result = first;
            for (int i = first+1; i <= last; i++) {
                result = lcd(result, i);
            }
            return result;
        }
    private:
        int gcd(int c, int d) {
            int v;
            v = c;
            while (v > 0) {
                v = c % d;
                c = d;
                d = v;
            }
            return c;
        }
        int lcd(int c, int d) {
            return c*d / gcd(c,d);
        }
};