Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-05

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();
    }
};