Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-03

TennisRallies

| 13:00

このDIV2の問題セットは、初めて時間内に全問を解くことができた。合計1255.1点で、overviewによると部門2位に当たる成績。

問題文

禁止されたショットの連続を含まないラリーを何種類作れるか。最悪のケースが2の18乗(=262144)なので、Brute-forceな方法でも終わる。

class TennisRallies {
    public:
        int howMany(int numLength, vector <string> forbidden, int allowed) {
            count = 0;
            string raly(numLength, ' ');
            go(raly, 0, 0, numLength, forbidden, allowed);
            return count;
        }
    private:
        int count;
        void go(string& raly, int p, int fCount, const int numLength,
                const vector<string>& forbidden, const int allowed) {
            for (int i = 0; i < forbidden.size(); i++) {
                const int fLen = forbidden[i].length();
                if (p >= fLen && raly.substr(p-fLen,fLen) == forbidden[i])
                    fCount++;
            }
            if (fCount >= allowed) return;
            if (p == numLength) {
                count++;
                return;
            }
            raly[p] = 'c';
            go(raly, p+1, fCount, numLength, forbidden, allowed);
            raly[p] = 'd';
            go(raly, p+1, fCount, numLength, forbidden, allowed);
        }
};

DennysDennys2012/07/10 08:54There's a trefriic amount of knowledge in this article!

ptkxkwfiufxptkxkwfiufx2012/07/11 08:32rW3Q5y <a href="http://lvoddmvsamev.com/">lvoddmvsamev</a>

ssurmbuvpsmssurmbuvpsm2012/07/11 21:20GnFEME , [url=http://jcvsaeuskkgr.com/]jcvsaeuskkgr[/url], [link=http://iseogblgtggc.com/]iseogblgtggc[/link], http://nsaattulsfhk.com/

xtmpsysmfgnxtmpsysmfgn2012/07/12 13:058VKorp <a href="http://qspzckisagzz.com/">qspzckisagzz</a>

ueblizedjueblizedj2012/07/12 18:376GmZzo , [url=http://rtmucgtfbosq.com/]rtmucgtfbosq[/url], [link=http://dzmpwnhervlx.com/]dzmpwnhervlx[/link], http://trmherritlub.com/