初めての・・・・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

view plainprint?

1. class Prb {  
2. public:  
3.     int sweet;  
4.     int x;  
5.     int y;  
6.     int len;  
7.   
8.     Prb(int s, int _x, int _y, int l) {  
9.         sweet = s;  
10.         x = _x;  
11.         y = _y;  
12.         len = l;  
13.     }  
14.     bool operator<(const Prb &prb) const {  
15.         if (this->y != prb.y)  
16.             return this->y < prb.y;  
17.         if (this->x != prb.x)  
18.             return this->x < prb.x;  
19.         return this->sweet < prb.sweet;  
20.     }  
21. };  
22.   
23. int dp[64];  
24. bool dn[64];  
25. vector<Prb> pp;  
26.   
27. class GetToTheTop {  
28. public:  
29.     int collectSweets(int K, vector<int> sweets, vector<int> x, vector<int> y, vector<int> stairLength) {  
30.         pp.clear();  
31.         memset(dp, 0, sizeof(dp));  
32.   
33.         pp.PB(Prb(0, 1, 0, 11000));  
34.         REP(i, sweets.size())  
35.             pp.PB(Prb(sweets[i], x[i], y[i], stairLength[i]));  
36.         SORT(pp);  
37.         // same y  
38.         FOR (i, 1, pp.size()) {  
39.             if (pp[i].y != pp[i-1].y)  
40.                 continue;  
41.             int l1 = pp[i].x, r1 = l1+pp[i].len;  
42.             int l2 = pp[i-1].x, r2 = l2+pp[i-1].len;  
43.   
44.             double r;  
45.             if (l1 >r2)  
46.                 r = dist(l1, 0, r2, 0);  
47.             else  
48.                 r = dist(l2, 0, r1, 0);  
49.             if (r <= K) {  
50.                 pp[i].sweet += pp[i-1].sweet;  
51.                 pp[i-1].sweet = -1;  
52.             }  
53.         }  
54.   
55.         FOR (i, 1, pp.size())  
56.             if (pp[pp.size()-1-i].sweet == -1)  
57.                 pp[pp.size()-1-i].sweet = pp[pp.size()-i].sweet;  
58.   
59.         int posy = 0;  
60.         REP(i, pp.size()) {  
61.             if (posy != pp[i].y) {  
62.                 posy = pp[i].y;  
63.                 meanSameY(i, posy, pp.size(), K);  
64.             }  
65.             if (i && !dp[i])  
66.                 continue;  
67.             int l1 = pp[i].x;  
68.             int r1 = l1 + pp[i].len;  
69.   
70.             REP(j, pp.size()) {  
71.                 if (i == j) continue;  
72.                 if (pp[i].y >= pp[j].y) continue;  
73.   
74.                 int l2 = pp[j].x;  
75.                 int r2 = l2 + pp[j].len;  
76.                 double r;  
77.                 if (r1 < l2) r = dist(r1,pp[i].y, l2, pp[j].y);  
78.                 else if (l1 > r2) r = dist(l1,pp[i].y, r2, pp[j].y);  
79.                 else r = dist(0, pp[i].y, 0, pp[j].y);  
80.   
81.                 if (r <= K)  
82.                     dp[j] = max(dp[j], dp[i] + pp[j].sweet);  
83.             }  
84.         }  
85.   
86.         return *max_element(dp, dp+pp.size());  
87.     }  
88.   
89.     double dist(int x1, int y1, int x2, int y2) {  
90.         return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));  
91.     }  
92.   
93.     void meanSameY(int pos, int h, int sz, int K) {  
94.         VVI idx;  
95.         VI tmp;  
96.         FOR (i, pos, sz) {  
97.             if (i >= sz  pp[i].y != h) {  
98.                 idx.PB(tmp);  
99.                 tmp.clear();  
100.                 break;  
101.             }  
102.             if (pp[i].x - (pp[i-1].x + pp[i-1].len) > K) {  
103.                 idx.PB(tmp);  
104.                 tmp.clear();  
105.             }  
106.             tmp.PB(i);  
107.         }  
108.         REP(i, idx.size()) {  
109.             int ret = 0;  
110.             tmp = idx[i];  
111.             REP(j, tmp.size())  
112.                 ret = max(ret, dp[tmp[j]]);  
113.             REP(j, tmp.size())  
114.                 dp[tmp[j]] = ret;  
115.         }  
116.     }  
117. };  

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