TopCoder SRM 633 Div1
今回はSRM 633の解説です。
Easy (250点)
問題
2次元の無限に広いフィールド上をジャンプしながら進む人がいる。この人のジャンプのパターンは決まっていて、例えば{2, 5}というパターンを持っていれば必ず、距離が2のジャンプ、距離が5のジャンプを繰り返しながら進んでいく。今、この人は(0, 0)から(x, 0)に向かいたい。ジャンプは特に格子点を通る必要はないものとするとき、必要なジャンプの最小数はいくつか？
解法
まず一番単純な結果として、x=0ならばジャンプの回数は0回になる。
気づくべきポイントは行うジャンプの中で最大の飛距離のものをどう扱うのかという問題。実はトータルの飛距離をT, その中の最大のジャンプをMとしたとき
M – (T – M) <= x かつ x <= T
が成り立つ必要がある。
1つ目の条件は最大のジャンプが長すぎたときに、最大ジャンプ以外のジャンプで距離を相殺できるかどうかを表すもの、2つ目の条件はそのそもトータルの飛距離が目的の距離以上なのかというもの。
この2つの条件に気づくことさえできれば、あとはそんなに難しくない。いろいろな人のコードを見た結果、たぶん二分探索でやるのが一番スマート。
class PeriodicJumping {
public:
int minimalTime(lint x, vector <int> jump) {
if(x == 0) return 0;
int n = jump.size();
x = abs(x);
lint ma = 0;
lint sum = 0;
for(int i=0; i<n; i++) {
ma = max(ma, (lint)jump[i]);
sum += jump[i];
if(ma - (sum - ma) <= x && x <= sum) return i+1;
}
lint lo = n;
lint hi = 1ll << 30;
while(lo < hi) {
lint mid = (lo + hi) / 2;
sum = 0;
REP(i,n) sum += jump[i];
sum *= mid / n;
REP(i,mid%n) sum += jump[i];
if(ma -(sum - ma) <= x && x <= sum) {
hi = mid;
} else {
lo = mid + 1;
}
}
return hi;
}
};
Medium (500点)
問題
ノード数は同じだが接続の異なる2つの木構造が与えられる。この木構造から部分集合をとったとき、両方の木が部分木になるようなものをとる。今、各ノードには点数が与えられているが、そのような条件を満たす部分集合の中で点数の合計が最大になるものはいくつか？
解法
なんでそうなるかを言葉で説明するのは難しいのだけど、問題としては有向グラフの最大流問題に帰着できる。
有向グラフは木構造をたどる根を決めて、2つの木構造をたどった時に子から親の方向に向かう辺をもったものとする。
sinkには正のスコアを持つノードを、sourceには負のスコアを持つノードを結ぶ。
で、最後に最大流のコストを正のノードのスコアの合計から引けばいい。
問題は何でこのやり方で良いのかという部分だが、まず1つ分かっていることとして、スコアには負のものがあり、その負のスコアのノードはできるだけ取り外したい。
ところが負のノードを取り外そうとすれば木構造が崩れる恐れがあるため、他の正のノードも外さなければならないかもしれない。
その時、上の最大流問題で解いているのは、負のノードと引き換えに失われる正のノードのコストがいくつになるのかを計算している。
基本的にはsinkからスタートして失われる正コストpのノードを通り、木構造をたどって、最後に負コストを持つノードqからsourceに向かう。
有向グラフは子から親へとエッジを引いてあったので、ここで試しているのは負コストを持つノードqより下の子どもを取っていったときに、コストが特になるのかどうかを計算しているといってもいい。
もし、qを根とする部分木のコストを全て足しても負のコストを相殺できなければq以下の部分木全てが切り落とされることになる。
最後に残る疑問として、このやり方で部分木の構造が崩れないのかと思う。これに関しては作られた有向グラフの一番末端にある正コストのノードから順番に除去されていくのと同等の計算ができているので問題ないはず。
このあたりの意図をコードから推測したけど、どこかまだ間違っている部分があるかもです。コードはとりあえず通ったものをのせます。
struct edge { int to, cap, rev; };
class MincostGraph {
private:
int nodes;
vector<vector<edge> > graph;
vector<int> used;
public:
static const int infinity = 1000000009;
public:
MincostGraph(int n)
: nodes(n)
, graph(n, vector<edge>())
, used(n, 0)
{
}
void add_edge(int from, int to, int cap) {
edge e1 = { to, cap, (int)graph[to].size() };
edge e2 = { from, 0, (int)graph[from].size() };
graph[from].push_back(e1);
graph[to].push_back(e2);
}
int dfs(int f, int t, int c) {
if(f == t) return c;
used[f] = 1;
vector<edge>::iterator it = graph[f].begin();
while(it != graph[f].end()) {
edge& e = (*it);
if(!used[e.to] && e.cap > 0) {
int d = dfs(e.to , t, min(c, e.cap));
if(d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
++it;
}
return 0;
}
int maxflow(int s, int t) {
int flow = 0;
while( 1 ) {
fill(used.begin(), used.end(), 0);
int f = dfs(s, t, infinity);
if(f == 0) break;
flow += f;
}
PRT(flow);
return flow;
}
};
bool t1[55][55];
bool t2[55][55];
int par1[55];
int par2[55];
class DoubleTree {
public:
int n;
void rec1(int cur, int prev) {
par1[cur] = prev;
REP(i,n) {
if(i == prev) continue;
if(t1[cur][i]) {
rec1(i, cur);
}
}
}
void rec2(int cur, int prev) {
par2[cur] = prev;
REP(i,n) {
if(i == prev) continue;
if(t2[cur][i]) {
rec2(i, cur);
}
}
}
int maximalScore(vector <int> a, vector <int> b, vector <int> c, vector <int> d, vector <int> score) {
n = a.size() + 1;
memset(t1, 0, sizeof(t1));
memset(t2, 0, sizeof(t2));
REP(i,n-1) {
t1[a[i]][b[i]] = t1[b[i]][a[i]] = true;
t2[c[i]][d[i]] = t2[d[i]][c[i]] = true;
}
int ans = 0;
for(int r=0; r<n; r++) {
memset(par1, 0, sizeof(par1));
memset(par2, 0, sizeof(par2));
rec1(r, -1);
rec2(r, -1);
int s = n;
int t = n + 1;
MincostGraph graph(n + 2);
for(int i=0; i<n; i++) {
if(i == r) continue;
graph.add_edge(i, par1[i], graph.infinity);
graph.add_edge(i, par2[i], graph.infinity);
}
int sum = 0;
for(int i=0; i<n; i++) {
if(score[i] >= 0) {
sum += score[i];
graph.add_edge(s, i, score[i]);
} else {
graph.add_edge(i, t, -score[i]);
}
}
PRT(r);
ans = max(ans, sum - graph.maxflow(s, t));
}
return ans;
}
};
まとめ
今回のEasyは一応submitしたのですが、あまり当たる気がせず、System Testで落ちました。
僕は最初三角形的に進むのが最小になるのかなと思ったのですが、それよりも緩い条件があったみたいですね。
解説終わります。お読みいただきありがとうございました。