Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-21

CrossWord

| 17:29

問題文, SRM 174

size個だけ連続した横方向の空白が、いくつあるのかを数える。

230.35/250

class CrossWord {
public:
    int countWords(vector <string> board, int size) {
        int count = 0;
        string pat(size, '.');
        pat = "X" + pat + "X";
        for (int i = 0; i < board.size(); i++) {
            board[i] = "X" + board[i] + "X";
            int idx = 0;
            while ((idx = board[i].find(pat,idx)) != string::npos) {
                count++;
                idx += size + 1;
            }
        }
        return count;
    }
};

WordForm

| 17:15

問題文, SRM 173

与えられた文字列は、どのような母音と子音の組み合わせから成るのか。

468.65/500

class WordForm {
public:
    string getSequence(string word) {
        string sequence;
        bool isPreVowel = false;
        for (int i = 0; i < word.length(); i++) {
            const char c = toupper(word[i]);
            bool isVowel = (i!=0 && !isPreVowel && c=='Y') ||
                c=='A' || c=='E' || c=='I' || c=='O' || c=='U';
            if (i == 0 || isVowel != isPreVowel) {
                if (isVowel) sequence += "V";
                else sequence += "C";
                isPreVowel = isVowel;
            }
        }
        return sequence;
    }
};

SmartElevator

| 13:12

問題文, SRM 156

エレベータが、全ての乗客を運び終えるのにかかる最短の時間を求める。

231.89/550

class SmartElevator {
public:
    int timeWaiting(vector <int> arrivalTime, vector <int> startingFloor, vector <int> destinationFloor) {
        int numPeople = arrivalTime.size();
        string pat(numPeople*2, '0');
        for (int i = 0; i < numPeople; i++)
            pat[i*2] = pat[i*2+1] = i+'0';  
        int minTime = INT_MAX;
        do {
            int floor = 1;
            int time = 0;
            vector<bool> pickedup(numPeople, false);
            for (int i = 0; i < numPeople*2; i++) {
                int e = pat[i]-'0';
                if (pickedup[e]) {
                    int distance = abs(floor-destinationFloor[e]);
                    time += abs(distance);
                    floor = destinationFloor[e];
                } else {
                    int distance = abs(floor-startingFloor[e]);
                    time = max(arrivalTime[e], time+distance);
                    floor = startingFloor[e];
                    pickedup[e] = true;
                }
            }
            minTime = min(minTime, time);
        } while (next_permutation(pat.begin(), pat.end()));
        return minTime;
    }
};