夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

srm div.1 デビュー戦 while 中間テスト

Opened Unopened Unopened
0.0pt 339th(?)
1239 -> 1246 (+7) (Highest)
誤差とはまさにこのことなり

デビュー戦が275点問題で自動レート上昇ってどうなのよ…

SRM557 Div.1Easy

リハビリにちょっと。
単純問題だったけどさすがに頭なまってて一発ACできなかった

class FoxAndMountainEasy {
public:
    string possible( int n, int h0, int hn, string history ) {
        string yes="YES", no="NO";

        int hl = history.length();
        int cm = n - hl;
        int minmove = 100001, move = 0;
        for (int i=0; i<hl; i++) {
            if (history[i] == 'U') {
                move++;
            } else {
                move--;
                minmove = min(minmove, move);
            }
        }
        // i歩は上に行った時
        for (int i=0; i<=cm; i++) {
            if (h0+i+move<0||h0+i+minmove<0) continue;
            int hnext = i - (cm - i) + move;
            if (h0 + hnext == hn) return yes;
        }
        return no;
    }
};

SRM558Div.1Easy

DPくさくて、DPで、しかも考え方が複雑すぎるDP。
辿りつけなかった…
ちなみにがんばってDPじゃなく解こうとした爪あとが以下

class Stamp {
public:
    string dc;
    vector<P> vc;
    int sc, pc, code[50];
    int getMinimumCost( string desiredColor, int stampCost, int pushCost ) {
        int n = desiredColor.length();
        dc = desiredColor;
        sc = stampCost; pc = pushCost;

        bool flag = false;
        for (int i=0; i<n; i++) {
            if (dc[i] == 'R') code[i] = 0;
            else if (dc[i] == 'G') code[i] = 1;
            else if (dc[i] == 'B') code[i] = 2;
            else {
                code[i] = -1;
                flag = true;
            }
        }

        vec.push_back(P(code[0], 1));
        int mcost = INT_MAX;
        for (int i=1; i<n; i++) {
            if (vec[vec.size()-1].first==code[i])
                vec[vec.size()-1].second++;
            else {
                mcost = min(mcost, vec[vec.size()-1].second);
                vec.push_back(P(code[i], 1));
            }
        }
        int res = INT_MAX;
        if (flag) {
            deque<P> deq;
            for (int i=0; i<vec.size(); i++) deq.push_back(vec[i]);
            while (deq.size()>1&&deq[0].first==-1) {
                deq[1].second += deq[0].second;
                deq.pop_front();
            }
            while (deq.size()>1&&deq[deq.size()-1].first==-1) {
                deq[deq.size()-1].second += deq[deq.size()-2].second;
                deq.pop_back();
            }
            for (int i=1; i<=n; i++) {
                int cnt = 0;
                for (int j=0; j<deq.size(); j++) {
                    if (deq[j].first!=-1) {
                        cnt += deq[j].second / i;
                        int x = i - deq[j].second % i;
                        deq[j].second = x;
                    }
                }
                vector<P> vec2;
                vec2.push_back(P(deq[0].first==-1, deq[0].second));
                for (int j=1; j<deq.size(); j++) {
                    if (vec2[vec2.size()-1] == (deq[j].first==-1))
                        vec2[vec2.size()-1] += deq[j].second;
                    else
                        vec2.push_back(P(deq[j].first==-1, deq[j].second));
                }
                vec2.
            }
            return res;
        } else {
            for (int i=1; i<=mcost; i++) {
                int cost = i * sc;
                for (int j=0; j<vec.size(); j++) {
                    cost += ((vec[j].second+i-1)/i * pc);
                }
                res = min(res, cost);
            }
            return res;
        }
    }
};

雑多なこと

今日はテストがとてーも楽で、なんか気が抜けて色々やってました。
あんま自由な時間ってもう持てないしUbuntu12.10にアップグレードしてみたりしてたんだけども…

terminatorとcinnamonが使えなくなっててちょっと残念。。。

もうちょい整備しないとあれですね、使いにくい。
あとrepository弄ってるからかなんか変なふうに…


あぁ・・・Webアプリ作ってみたい・・・
大学入ってから(そのころには時代遅れになってる可能性大w