Search on the blog

2010年11月11日木曜日

初めての・・・・Hard AC!

人生初の、TopCoder Hard(Division 2)自力AC。
直観でこの問題は簡単と思って、1時間もあれば・・って思ったけど、落とし穴があって結局3時間かかってしまった(泣)

でも、初めて何にも頼らず自力で解けたというのは大きな進歩だと思う。
これが、赤色への記念すべき歴史的第一歩となることを願うばかりである。。

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

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


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

0 件のコメント:

コメントを投稿