Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-10-23

PizzaDelivery

| 07:29

問題文, SRM 451

2人の配達人を使って、ピザを配達し終えるのにかかる最短時間を求める。

解くのに2時間強かかった。しょうもないバグにより3回、時間制限により1回、システムテストで落とされた。解法はBFS+Brute Forceなので割と単純だが、異常に調子が良い時でないと本番の時間内にバグなしで解ける気がしない。

300.00/1000 (4-failed)

const static int INFTY = INT_MAX/2;

class PizzaDelivery {
    public:
        int deliverAll(vector <string> terrain) {
            const int H = terrain.size();
            const int W = terrain[0].size();
            vector<pair<int,int> > piza;
            pair<int,int> r;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (terrain[y][x] == 'X') {
                        r = make_pair(y, x);
                    } else if (terrain[y][x] == '$') {
                        piza.push_back(make_pair(y,x));
                    }
                }

            int D[100];
            int T[100][100];
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++)
                    T[y][x] = INFTY;
            T[r.first][r.second] = 0;
            queue<pair<int,int> > Q;
            Q.push(r);
            while (!Q.empty()) {
                pair<int,int> a = Q.front(); Q.pop();
                const int y = a.first, x = a.second;
                const static int d[4][2] = {
                    {0,1}, {0,-1}, {1,0}, {-1,0} };
                for (int i = 0; i < 4; i++) {
                    const int ny = y + d[i][0];
                    const int nx = x + d[i][1];
                    if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                        if (!isdigit(terrain[ny][nx]) || !isdigit(terrain[y][x])) {
                            if (T[y][x]+2 < T[ny][nx]) {
                                T[ny][nx] = T[y][x] + 2;
                                Q.push(make_pair(ny, nx));
                            }
                            continue;
                        }
                        if (abs(terrain[ny][nx]-terrain[y][x]) == 0 && 
                                T[y][x]+1 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 1;
                            Q.push(make_pair(ny, nx));
                        } else if (abs(terrain[ny][nx]-terrain[y][x]) == 1 && 
                                T[y][x]+3 < T[ny][nx]) {
                            T[ny][nx] = T[y][x] + 3;
                            Q.push(make_pair(ny, nx));
                        }
                    }
                }
            }
            for (int i = 0; i < piza.size(); i++) {
                D[i] = T[piza[i].first][piza[i].second];
                if (D[i] == INFTY) return -1;
            }

            int minTime = INFTY;
            for (int i = 0; i < 1<<(piza.size()-1); i++) {
                bitset<20> pat(i);
                vector<int> vboy1, vboy2;
                for (int j = 0; j < piza.size(); j++) {
                    if (pat[j]) vboy1.push_back(D[j]);
                    else        vboy2.push_back(D[j]);
                }
                int boy1=0, boy2=0;
                if (vboy1.size() > 0)
                    boy1 = 2*accumulate(vboy1.begin(), vboy1.end(), 0) 
                        - *max_element(vboy1.begin(), vboy1.end());
                if (vboy2.size() > 0)
                    boy2 = 2*accumulate(vboy2.begin(), vboy2.end(), 0) 
                        - *max_element(vboy2.begin(), vboy2.end());
                //cout << pat << " " << boy1 << " " << boy2 << endl;
                minTime = min(minTime, max(boy1, boy2));
            }
            return minTime;
        }
};

nphuuejznphuuejz2011/02/28 17:01PX5gMr <a href="http://thxvtmuhvzkh.com/">thxvtmuhvzkh</a>, [url=http://aegsueyzfdwj.com/]aegsueyzfdwj[/url], [link=http://juwwqktqnkxe.com/]juwwqktqnkxe[/link], http://fuvdtrdrrxop.com/

2009-10-21

BoredPhilosophers

| 12:48

問題文, SRM 451

教室にN人の哲学者がいます。彼らはとても退屈なので、本から抜粋した適当なテキスト使ってゲームを始めました。1番目の哲学者はテキスト中の語の種類数を言います。2番目の哲学者は2個の連続する語からなるセンテンスの種類数を言います。同様にi番目の哲学者はi個の連続する語からなるセンテンスの種類数を言います。このゲームはN人全ての哲学者が発言した後に終了します。

テキストとして vector<string> が与えられます。このvectorの要素を結合(concatenate)し、テキストを完成させ、N個の要素からなる vector<int> を返しなさい(i番目の要素にはi人目の哲学者が言った数を入れる)。テキスト中の語はシングルスペースで区切られています。

問題文中のconcatenateの意味を理解するのに時間がかかった。意味が理解できれば実装は難しくない。

265.46/500

class BoredPhilosophers {
public:
    vector <int> simulate(vector <string> text, int N) {
        string T;
        for (int i = 0; i < text.size(); i++)
            T += text[i];
        vector<string> words;
        istringstream iss(T);
        string s;
        while (iss >> s) words.push_back(s);
        vector <int> result;
        for (int d = 1; d <= N; d++) {
            set<string> difWords;
            for (int i = 0; i < words.size()-d+1; i++) {
                string t(words[i]);
                for (int j = i+1; j < i+d; j++)
                    t += " " + words[j];
                difWords.insert(t);
            }
            result.push_back(difWords.size());
        }
        return result;
    }
};

ReverseMagicalSource

| 12:48

SRM 451 Div2 は250と500を通せて、511.38(245.92+265.46)点だった。Ratingは 1074 から 1119 に上がった。

問題文, SRM 451

 x=10^0s+10^1s+10^2s+\cdots10^is > A \mbox{ } (i \ge 0)を満たす最小の xを求める。

245.92/250

class ReverseMagicalSource {
public:
    int find(int source, int A) {
        int x = source;
        while (x <= A) {
            source *= 10;
            x += source;
        }
        return x;
    }
};

ivcbmcaeivcbmcae2011/02/28 07:41NZm68y <a href="http://ilbauxmjluym.com/">ilbauxmjluym</a>, [url=http://xbddmcdppokz.com/]xbddmcdppokz[/url], [link=http://sjwaelhpgvzy.com/]sjwaelhpgvzy[/link], http://uddhrwxfjfig.com/