TopCoder SRM 646 Div1
こんにちはtatsyです。本日もSRMの解説いきます。
Easy (250点)
問題
整数からなる数列が与えられる。この数列から適当にk個を選んで、好きなように並べ替えることができる。このとき各々の数を変化させて、数が1ずつ上がる、あるいは1ずつ下がるようにしたい。変化させるべき数の絶対値の合計の最小値はいくつか？
解法
この問題は個人的に少し英語が分かりづらかったなぁと思います。
要するに好きに数をk個選んで並び替えて良いので、数列をソートした後で連続するk個の部分列が1ずつ上がるように変化させれば良いことが分かります。
ある非減少の数列を階段状に変化させるときには、変化数が最小になるものは複数ある可能性がありますが、そのうち少なくとも1つは変化させなくて良い数を含みます。
そうすると、階段の最初の数として考えるべきものは高々k個なので、長さkの連続する部分列の選び方がO(k)あることから全体の計算量はO(k^2)になります。
後半の階段状にするための移動数に関する性質を知っていれば、それほど大変な問題ではないと思います。
class TheConsecutiveIntegersDivOne {
public:
int n;
int k;
vector<int> ns;
int calc(int s) {
int ret = 1 << 30;
for (int i = 0; i < k; i++) {
int b = ns[s + i] - i;
int val = 0;
for (int j = 0; j < k; j++) {
val += abs(b + j - ns[s + j]);
}
ret = min(ret, val);
}
return ret;
}
int find(vector<int> numbers, int k_) {
this->ns = numbers;
this->n = (int)numbers.size();
this->k = k_;
sort(ns.begin(), ns.end());
int ans = 1 << 30;
for (int i = 0; i + k <= n; i++) {
ans = min(ans, calc(i));
}
return (int)ans;
}
};
Medium (600点)
問題
無限に広いグリッドに最大47個のブロックが置かれている。あなたは今、原点にいてブロックを避けながらなるべくx座標が大きい場所に移動したい。移動距離がk以下になるようにするとき、移動可能なx座標の最大値はいくつか？
制約条件
1 <= k <= 1,000,000,000
-1,000,000,000 <= x, y <= 1,000,000,000。
解法
単純に考えると、ダイクストラ法みたいなやり方をして、移動距離がk以下で行ける場所を列挙すればいいのですが、kがかなり大きいのでそのままでは計算量が足りません。
そこで割と王道っぽいのですが、座標を圧縮してあげます。
必要なアイディアは実はこの2つだけで、あとは移動距離がkを超えないように注意しながら移動できるx座標の最大値を求めればいいだけです。
ただし、結構実装が重たいのと、テストケースが若干弱いのとがあって、結構時間内に通すのは難しいんじゃないかなと思いました。
実際、4回くらいSystem Testを走らせてやっとACでました。
const int INF = 1000000011;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool obs[200][200];
int dist[200][200];
struct Node {
int x, y, dist;
Node(int x_, int y_, int dist_) : x(x_), y(y_), dist(dist_) {}
bool operator<(const Node& nd) const {
return dist < nd.dist;
}
bool operator>(const Node& nd) const {
return dist > nd.dist;
}
};
class TheGridDivOne {
public:
int find(vector<int> x, vector<int> y, int K) {
vector<int> xx;
vector<int> yy;
for (int i = 0; i < x.size(); i++) {
for (int k = 0; k < 4; k++) {
xx.push_back(x[i] + dx[k]);
yy.push_back(y[i] + dy[k]);
}
}
xx.push_back(0);
xx.push_back(-INF);
xx.push_back(INF);
yy.push_back(0);
yy.push_back(-INF);
yy.push_back(INF);
sort(xx.begin(), xx.end());
sort(yy.begin(), yy.end());
xx.erase(unique(xx.begin(), xx.end()), xx.end());
yy.erase(unique(yy.begin(), yy.end()), yy.end());
int w = xx.size();
int h = yy.size();
memset(obs, 0, sizeof(obs));
for(int i=0; i<x.size(); i++) {
int xc = lower_bound(xx.begin(), xx.end(), x[i]) - xx.begin();
int yc = lower_bound(yy.begin(), yy.end(), y[i]) - yy.begin();
obs[xc][yc] = true;
}
int ox = lower_bound(ALL(xx), 0) - xx.begin();
int oy = lower_bound(ALL(yy), 0) - yy.begin();
memset(dist, -1, sizeof(dist));
priority_queue<Node, vector<Node>, greater<Node> > que;
que.push(Node(ox, oy, 0));
int ans = 0;
while (!que.empty()) {
Node nd = que.top();
que.pop();
for (int k = 0; k < 4; k++) {
int nx = nd.x + dx[k];
int ny = nd.y + dy[k];
if (nx >= 0 && ny >= 0 && nx < w && ny < h && !obs[nx][ny]) {
int dd = abs(xx[nd.x] - xx[nx]) + abs(yy[nd.y] - yy[ny]);
if (dist[nx][ny] == -1 || dist[nx][ny] > nd.dist + dd) {
if (nd.dist + dd >= K) {
int res = xx[nd.x] + (dx[k] != 0 ? dx[k] * (K - nd.dist) : 0);
ans = max(ans, res);
}
else {
dist[nx][ny] = nd.dist + dd;
que.push(Node(nx, ny, dist[nx][ny]));
ans = max(ans, xx[nx]);
}
}
}
}
}
return ans;
}
};
まとめ
今日はEasyでしょうもない境界判定ミスを埋め込んだせいで信じられないくらいレートが下がりました。
Mediumも時間があればSubmitくらいはできたと思うのですが…
というわけで、今回の解説はこれで終わります。最後までお読みいただきありがとうございました。