Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-10

WindowWasher

| 14:08

問題文

窓掃除にかかる最短時間を求める。Level-3の問題なのに、あっさり解けてしまった。良い解法がすぐに思いつけば、これぐらいの速度で解けるのか。個人的にはLevel-2の問題の方が難しく感じた。

881.11/1100 - 00:14:58

class WindowWasher {
    public:
        int fastest(int width, int height, vector <int> washTimes) {
            const int numPeople = washTimes.size();
            for (int i = 0; i < numPeople; i++) 
                washTimes[i] *= height;
            vector<int> workTimes(numPeople, 0);
            while (width-- > 0) {
                int minIdx=-1, minTime=INT_MAX;
                for (int i = 0; i < numPeople; i++) {
                    int time = workTimes[i] + washTimes[i];
                    if (time < minTime) {
                        minTime = time;
                        minIdx = i;
                    }
                }
                workTimes[minIdx] += washTimes[minIdx];
            }
            return *max_element(workTimes.begin(), workTimes.end());
        }
};

NumberGuesser

| 19:34

問題文

数字を推測。自力で解けなかった。総当たりで解いたが、数学的な解法もある。

190.54/500 - 01:06:07 (cheated)

class NumberGuesser {
    public:
        int guess(string leftOver) {
            int candidate = 0;
            for (int d = 1; d <= 9; d++) {
                int found = 0;
                for (int i = 0; i < 4; i++) {
                    ostringstream oss;
                    oss << leftOver.substr(0,i) << d << leftOver.substr(i);
                    int z;
                    istringstream(oss.str()) >> z;
                    for (int x = 1; x+z <= 9998; x++) {
                        int y = x + z;
                        if (isDigitMatch(x, y)) {
                            candidate = d;
                            found++;
                            break;
                        }
                    }
                }
                if (found == 4) return d;
            }
            return candidate;
        }
    private:
        bool isDigitMatch(int x, int y) {
            vector<int> ndigits(10, 0);
            while (x > 0) {
                if (x%10 != 0) ndigits[x%10]++;
                x /= 10;
            }
            while (y > 0) {
                if (y%10 != 0) ndigits[y%10]--;
                y /= 10;
            }
            for (int i = 0; i < ndigits.size(); i++) {
                if (ndigits[i] != 0)
                    return false;
            }
            return true;
        }
};

StairClimb

| 19:34

問題文

階段登り。

248.03/250

class StairClimb {
    public:
        int stridesTaken(vector <int> flights, int stairsPerStride) {
            int steps = 0;
            const static int TURN_STEPS = 2;
            for (int i = 0; i < flights.size(); i++) {
                steps += TURN_STEPS;
                steps += flights[i] / stairsPerStride;
                if (flights[i]%stairsPerStride != 0) steps++;
            }
            steps -= TURN_STEPS;
            return steps;
        }
};