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

editorial

17:04

Login - TopCoder Wiki

なにこれ超やさしい…いままで解いた問題のやつざっと見直してみよう.

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落ちまくり.正方形だと勝手に解釈していたせいで時間がかかった…

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

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


以下ソース

続きを読む

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で母親由来の文字を飛ばしつつループを回す.


以下ソース

続きを読む

解いた過去問まとめ

| 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

2010-03-05

SRM 462 DIV2続き

| 14:09

medium

AgeEncoding.cpp

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

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

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


以下ソース

続きを読む

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

わからないー

続きを読む

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/