初めての・・・・Hard AC！

人生初の、TopCoder Hard(Division 2)自力AC。

直観でこの問題は簡単と思って、1時間もあれば・・って思ったけど、落とし穴があって結局3時間かかってしまった（泣）

でも、初めて何にも頼らず自力で解けたというのは大きな進歩だと思う。

これが、赤色への記念すべき歴史的第一歩となることを願うばかりである。。

ヘタレすぎるコードですが、記念ということで貼っておきます。

問題は、こちら。基本的な動的計画なのですが、・・・、同じ高さのところの処理をどうするかでかなり悩みました。解説や赤色の人のコードを参考にスマートな解法を探ってみます。

Single Round Match 404 Round 1 - Division II, Level Three:

http://www.topcoder.com/stat?c=problem_statement&pm=9755

class Prb {
public:
    int sweet;
    int x;
    int y;
    int len;

    Prb(int s, int _x, int _y, int l) {
        sweet = s;
        x = _x;
        y = _y;
        len = l;
    }
    bool operator<(const Prb &prb) const {
        if (this->y != prb.y)
            return this->y < prb.y;
        if (this->x != prb.x)
            return this->x < prb.x;
        return this->sweet < prb.sweet;
    }
};

int dp[64];
bool dn[64];
vector<Prb> pp;

class GetToTheTop {
public:
    int collectSweets(int K, vector<int> sweets, vector<int> x, vector<int> y, vector<int> stairLength) {
        pp.clear();
        memset(dp, 0, sizeof(dp));

        pp.PB(Prb(0, 1, 0, 11000));
        REP(i, sweets.size())
            pp.PB(Prb(sweets[i], x[i], y[i], stairLength[i]));
        SORT(pp);
        // same y
        FOR (i, 1, pp.size()) {
            if (pp[i].y != pp[i-1].y)
                continue;
            int l1 = pp[i].x, r1 = l1+pp[i].len;
            int l2 = pp[i-1].x, r2 = l2+pp[i-1].len;

            double r;
            if (l1 >r2)
                r = dist(l1, 0, r2, 0);
            else
                r = dist(l2, 0, r1, 0);
            if (r <= K) {
                pp[i].sweet += pp[i-1].sweet;
                pp[i-1].sweet = -1;
            }
        }

        FOR (i, 1, pp.size())
            if (pp[pp.size()-1-i].sweet == -1)
                pp[pp.size()-1-i].sweet = pp[pp.size()-i].sweet;

        int posy = 0;
        REP(i, pp.size()) {
            if (posy != pp[i].y) {
                posy = pp[i].y;
                meanSameY(i, posy, pp.size(), K);
            }
            if (i && !dp[i])
                continue;
            int l1 = pp[i].x;
            int r1 = l1 + pp[i].len;

            REP(j, pp.size()) {
                if (i == j) continue;
                if (pp[i].y >= pp[j].y) continue;

                int l2 = pp[j].x;
                int r2 = l2 + pp[j].len;
                double r;
                if (r1 < l2) r = dist(r1,pp[i].y, l2, pp[j].y);
                else if (l1 > r2) r = dist(l1,pp[i].y, r2, pp[j].y);
                else r = dist(0, pp[i].y, 0, pp[j].y);

                if (r <= K)
                    dp[j] = max(dp[j], dp[i] + pp[j].sweet);
            }
        }

        return *max_element(dp, dp+pp.size());
    }

    double dist(int x1, int y1, int x2, int y2) {
        return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
    }

    void meanSameY(int pos, int h, int sz, int K) {
        VVI idx;
        VI tmp;
        FOR (i, pos, sz) {
            if (i >= sz  pp[i].y != h) {
                idx.PB(tmp);
                tmp.clear();
                break;
            }
            if (pp[i].x - (pp[i-1].x + pp[i-1].len) > K) {
                idx.PB(tmp);
                tmp.clear();
            }
            tmp.PB(i);
        }
        REP(i, idx.size()) {
            int ret = 0;
            tmp = idx[i];
            REP(j, tmp.size())
                ret = max(ret, dp[tmp[j]]);
            REP(j, tmp.size())
                dp[tmp[j]] = ret;
        }
    }
};