Hatena::Grouptopcoder

yaottiの日記

2010-03-11

SRM 156 DIV2続き

| 16:24

hard

TopCoder Statistics - Problem Statement

greedyに一致させていくと最適にならないケース(問題のsample5)にどう対処すればいいのかわからない…

例えば

original: ABABCDC

compound: ABABABC

だと,greedyにやるとABAB+AB+Cで3になるけど,うまくやればAB+ABABCで2になる.

後者の方が良いと知る方法はあるのかな.全部試すしかない気がする…

class WordParts {
public:
    int partCount(string original, string compound) {
        int result = 0;
        int idx = 0;
        int len = compound.size();
        while (idx < len) {
            int i = 0;
            for (; i < (int)original.size(); i++) {
                if (original[i] != compound[idx+i]) break;
            }
            int j = 0;
            int maxj = 0;
            for (int idxj = 1; idxj < (int)compound.size()-idx+1; idxj++) {
                string s = compound.substr(idx,idxj); // 残っているcompoundから切り取っていく
                // 文字列が見付からないならそこで終了
                if (original.find(s, 1) == string::npos) break;
                int pos = 1;    // 検索開始位置,最後尾の物を得る
                while (original.find(s, pos) != string::npos) {
                    j = original.find(s, pos);
                    pos++;
                }
                // 末尾に一致しなければ,失敗
                if (j + idxj != (int)original.size()) {
                    continue;
                }
                maxj = max(idxj, maxj);
            }
            if (i == 0 && maxj == 0) return -1;
            result++;
            idx += max(i,maxj);
        }
        return result;
    }
}

SRM 156 DIV2再び

| 23:14

hard

Editorial読んでもう一度挑戦.というかそのままコードにしただけ.

memoize!

class WordParts {
public:
    string orig;
    string cmp;
    vector <string> dict;
    int memo[100];
    int minParts(int pos) {
        if (memo[pos] != -1) return memo[pos];
        if (pos == (int)cmp.size()) return 0;
        int ret = 10000;
        LP(dict) {
            if (cmp.substr(pos, dict[i].size()) == dict[i]) { // prefix
                ret = min(ret, 1+minParts(pos+dict[i].size()));
            }
        }
        memo[pos] = ret;
        return ret;
    }
    void setUpDict() {
        // prefix
        dict.clear();
        for (int i = 1; i < (int)orig.size(); i++) {
            dict.push_back(orig.substr(0, i));
        }
        for (int i = 1; i < (int)orig.size(); i++) {
            dict.push_back(orig.substr(i));
        }
        dict.push_back(orig);
    }
    int partCount(string original, string compound) {
        cmp = compound;
        orig = original;
        setUpDict();
        memset(memo, -1, sizeof(memo));
        int ret = minParts(0);
        return  ret < 1000 ? ret : -1;
    }
}

2010-03-08

SRM 156 DIV2

| 22:58

easy

DiskSpace.cpp

score: 231/250(8mins)

こんな問題に8分もかけるなんて…

reverse_sortみたいなのあるかと思って探したけどなかったのでsortして後ろから見ていったけど,解き終えてからreverseというのがあることを知った.

normal

BombSweeper.cpp

180/600(31mins)

system test落ちまくり.正方形だと勝手に解釈していたせいで時間がかかった…

勘違いは気をつけるしかないとしても,

勘違いが影響しているロジック全てを直さずにちょっとずつ直す→システムテスト通らない!→再びチェック,を繰り返したのは駄目だ.


以下ソース

easy

class DiskSpace {

public:

int minDrives(vector <int> used, vector <int> total) {

sort(ALL(total));

int usedSize = accumulate(ALL(used), 0);

int len = total.size();

int j = 0;

for (int i = 0; i < len; i++) {

usedSize-=total[len-i-1];

j++;

if (usedSize <= 0) break;

}

return j;

}

}

normal

class BombSweeper {
public:
    double winPercentage(vector <string> board) {
        int win = 0;
        int lose = 0;
        int len = board.size();
        int len2 = board[0].size();
        if (len == 1 && len2 == 1) {
            double res = board[0][0] == 'B' ? 0 : 1;
            return res;
        }
        LP(board) {
            Lj(board[i]) {
                if (board[i][j] == 'B') {
                    lose++;
                    continue;
                }
                int i1 = i;
                int j1 = j;
                if (i1 == 0) i1++;
                if (j1 == 0) j1++;
                if (board[i1-1][j1-1] == 'B' ||
                    board[i1-1][j] == 'B' ||
                    board[i][j1-1] == 'B') continue;
                int i2 = i;
                int j2 = j;
                if (i2 == len-1) i2--;
                if (j2 == len2-1) j2--;
                if (board[i1-1][j2+1] == 'B' ||
                    board[i][j2+1] == 'B' ||
                    board[i2+1][j1-1] == 'B' ||
                    board[i2+1][j] == 'B' ||
                    board[i2+1][j2+1] == 'B') continue;
                win++;
            }
        }
        return (double)win/(win+lose)*100;
    }
}

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

2010-03-05

SRM 462 DIV2続き

| 14:09

medium

AgeEncoding.cpp

scoreと所用時間はメモしわすれた

例外的なケース実装に手間取った…1, "00101"とかそういうケース

2分探索実装したの初めてだ.


以下ソース

public:
    double getRadix(int age, string candlesLine) {
        // age > BASE > 0
        int len = candlesLine.size();
        double base;
        double l = 0, u = age;
        int i;
        for (i = 0; i < len; i++) {
            if (candlesLine[i] != '0') break;
        }
        if (i == len) {     // 全て0
            return (double)-1;
        }
        if (i + 1 == len) {     // 最後が1
            if (age == 1) return (double) - 2;
            return (double) - 1;
        }
        if (age == 1 && candlesLine[len - 1] == '1') {         // 2ビット以上立っている&最後が1
            return (double) - 1;
        }
        for(;;) {
            base = (l + u) / 2.0;
            double sumup = 0.0;
            double p = 1.0;
            LP(candlesLine) {
                if (candlesLine[len - i - 1] == '1') {
                    sumup += p;
                }
                p *= base;
            }
            if (abs(sumup - age) < EPSM) {
                break;
            }else if (sumup > age) {
                u = base;
            }else {
                l = base;
            }
        }
        return base;
    }
}

DedeDede2012/08/30 06:02Play informative for me, Mr. internet wrietr.

vdsiweebvvdsiweebv2012/08/30 22:57uRlawh <a href="http://dnvcxgpigien.com/">dnvcxgpigien</a>

2010-03-04

SRM 154 DIV2

| 22:25

easy

ProfitCalculator.cpp

score: 263/300 (11mins)

簡単なのにちょっと時間かかった

  • stringstreamの扱いになれていない
  • roundは四捨五入,ceilは切上げ,floorは切り捨て

medium

SuperRot.cpp

score: 388->355/600(時間はかりわすれた)

シンプルに実装できそうだなと思いつつ愚直にやった.他人のソース読んだけどみんなストレートに実装してるなあ

  • charval - '0'は常套手段
  • 与えられたケースに通ったとしても,境界条件にひどいバグを仕込んでることもある

hard

ContestScore.cpp

わからないー

easy

class ProfitCalculator {
public:
    int percent(vector <string> items) {
        double t_price = 0, t_cost = 0;
        LP(items) {
            istringstream iss;
            double price, cost;
            iss.str(items[i]);
            iss >> price;
            iss >> cost;
            t_price += price;
            t_cost += cost;
        }
        return (int)floor(((t_price - t_cost)/t_price)*100 - EPS);
    }
}

medium

13とか5を足してmod取る,とすれば綺麗にかけそう

(message[i] - 'a' + 13)%26 + 'a'

みたいな

class SuperRot {
public:
    string decoder(string message) {
        string result("");
        LP(message) {
            if (0 <= message[i] - '0' && message[i] - '0' <= 9) {
                int r = message[i] - '0' > 4 ? message[i] - 5 : message[i] + 5;
                result.push_back(r);
            }else if (message[i] >= 'a' && message[i] <= 'z') {
                int r = message[i] > 'm' ? message[i] - 13 : message[i] + 13;
                result.push_back(r);
            } else if (message[i] >= 'A' && message[i] <= 'Z'){
                int r = message[i] > 'M' ? message[i] - 13 : message[i] + 13;
                result.push_back(r);
            }else {
                result.push_back(message[i]);
            }
        }
        return result;
    }
}

AneishaAneisha2012/09/01 12:37It's posts like this that make srufing so much pleasure

dfollrvswxzdfollrvswxz2012/09/02 04:26orXP94 <a href="http://sweiyoczqhzr.com/">sweiyoczqhzr</a>

lsaedcwglsaedcwg2012/09/04 05:55Vhnv5F <a href="http://uqiulyojxfat.com/">uqiulyojxfat</a>

hptqprhptqpr2012/09/04 17:49D2w4EV , [url=http://urswupkqqume.com/]urswupkqqume[/url], [link=http://mskgpgcezjau.com/]mskgpgcezjau[/link], http://okhknoxxyvfd.com/