Hatena::Grouptopcoder

yaottiの日記

2010-03-07

SRM155 DIV2

| 22:18

easy

Quipu.cpp

score: 240/250(5mins)

特に問題なくクリア

medium

BenfordsLaw.cpp

score: 373/500(18mins)

ミスポイント

doubleを期待してるところでintを渡して0になる,というのは前もやった気がする…

ostringstreamを使うところでistringstreamを使ってた.

結構綺麗に書けた気がするし,それ以外は満足

hard

PaternityTest.cpp

score: 557/1000 (31mins)

これは方針が立てばそれほどはまらずに書けた.時間内にhardまでsystem test通したの久しぶりな気がする…

でもStatisticsによると参加者の1/4ぐらいは正解してたみたいなので,簡単な問題だったんだろうな.

方針

ソース読んだほうがわかりやすいだろうけど,一応自然言語で説明してみる.

まず母親と子供で一致している文字のindexをvectorに保存する.

利用するのは文字列半分の長さまでなので,その組み合わせ表現のために0/1からなるvectorを用意する.

(0:母親と一致してるけど利用しない 1:母親と一致していて利用する)

あとはnext_permutationで母親由来の文字を飛ばしつつループを回す.


以下ソース

easy

class Quipu {
public:
    int readKnots(string knots) {
        int res = 0;
        int stack = 0;
        LP(knots) {
            if (knots[i] == '-') {
                res *= 10;
                res += stack;
                stack = 0;
            }else {
                stack++;
            }
        }
        return res;
    }
}

medium

class BenfordsLaw {
public:
    int questionableDigit(vector <int> transactions, int threshold) {
        int times[10] = {0};
        int len = transactions.size();
        LP(transactions) {
            ostringstream ss;
            ss << transactions[i];
            string s = ss.str();
            times[s[0]-'0']++;
        }
        for (int i = 1; i < 10; i++) {
            double expected = log10(1.0+1.0/(double)i) * len;
            if (times[i] - EPS > expected * threshold ||
                times[i] - EPS < expected / threshold)
                return i;
        }
        return -1;
    }

}

hard

class PaternityTest {
public:
    vector <int> possibleFathers(string child, string mother, vector <string> men) {
        int len = child.size();
        vector <int> corIdx;    // 一致するindex list
        LP(child) {
            if (child[i] == mother[i]) corIdx.push_back(i);
        }
        vector <int> perm;      // corIdxで一致して利用するindex(0なら使わない,1なら使う)
        for (int i = 0; i < (int)corIdx.size() - len/2; i++) {
            perm.push_back(0);
        }
        for (int i = 0; i < len/2; i++) {
            perm.push_back(1);
        }
        vector<int> result;
        //vector<int> result;
        LP(men) {
            do {
                if (find(ALL(result), i) != result.end()) break;
                bool match = true;
                Lj(men[i]) {
                    vector<int>::iterator it = find(ALL(corIdx), j);
                    if (it != corIdx.end() && perm[it-corIdx.begin()] == 1) continue; // 父親との一致には使えない
                    if (men[i][j] != child[j]) {
                        match = false;
                    }
                }
                if (match) result.push_back(i);
            } while (next_permutation(ALL(perm)));
        }
        return result;
    }
}

解いた過去問まとめ

| 00:06

DIV2easynormalharddate
1442/18
1452/20
1462/20
1472/20
1482/23
1492/24
1502/26
1512/28
1523/2
153x(PickTeam)3/3
154x(ContestScore)3/4
1553/7
462x(SteeplechaseTrack)3/2
4633/2

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/yaotti/20100307