Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-24

ClockWalk

| 17:39

問題文, SRM 175

時計を動かし終わった後は、何時か。テストをしないで出したら、tailの場合の計算で、馬鹿なバグがあり、落とされた。

214.27/250

class ClockWalk {
public:
    int finalPosition(string flips) {
        int hour = 0;
        for (int i = 0; i < flips.size(); i++) {
            if (flips[i] == 'h') hour = (hour + i+1) % 12;
            else  hour = (hour - (i+1) + 120) % 12;
        }
        if (hour == 0) hour = 12;
        return hour;
    }
};

StripePainter

| 13:03

問題文, SRM 150

最低何回ペンキを塗りつける必要があるか。DP+メモ化で解ける問題。

224.12/500

class StripePainter {
public:
    int minStrokes(string stripes) {
        const int size = stripes.size();
        memo = vector<vector<vector<int> > >(size,vector<vector<int> >(size+1,vector<int>(128,-1)));
        return go(stripes, 0, size, '?');
    }
private:
    vector<vector<vector<int> > > memo;
    int go(const string& stripes, 
            const int left, const int size, const char color) {
        if (size <= 0) return 0;
        if (memo[left][size][color] >= 0) return memo[left][size][color];
        int best = INT_MAX;
        if (stripes[left] == color) {
            best = go(stripes, left+1, size-1, color);
        } else {
            for (int i = 1; i <= size; i++) 
                best = min(best, 1
                        + go(stripes,left+1,i-1,stripes[left])
                        + go(stripes,left+i,size-i,color));
        }
        memo[left][size][color] = best;
        return best;
    }
};