TopCoder SRM 642 Div1
今回もSRM 642の解説行きます。今回からソースコードのヘッダ部分は切ります(一応マクロは残します)。
今回の問題は
- Easy: メモ化 / 確率
- Medium: 最小費用流
となっております。
Easy (250点)
問題
ある町にはバスがN本あり、それぞれのバスは駅を出発してtime[i]分で駅に戻ってくる。一度に運行できるバスは1本だけであるため、ひとたびバスが出発するとtime[i]分はバスがでない。出発するバスはそれぞれprob[i] %の確率で選ばれる。今あなたが時刻sに駅に到着したとすると待ち時間の期待値はいくつか？
制約条件
1 <= N <= 100
0 <= s <= 100000
解法
ある時刻tにバスが出発する確率をメモ化で求める。すなわち、ある時刻にバスが出る確率をmemo[t]とするとき、
memo[t+time[i]] = sum {i: memo[t] * (prob[i] / 100.0)}
が成り立つ。
今求めたいのは時刻sから初めてバスが出る時刻なので、上のメモ化を時刻がs以上になったら打ち切る。
するとs以上に現れる確率の合計が1になるようになる。
あとは、これをsと時刻の差を取りながら期待値計算していけばいい。
double memo[200011];
class WaitingForBus {
public:
double whenWillBusArrive(vector<int> time, vector<int> prob, int s) {
memset(memo, 0, sizeof(memo));
memo[0] = 1.0;
int upper = s;
for (int i = 0; i < s; i++) {
for (int j = 0; j < time.size(); j++) {
memo[i + time[j]] += memo[i] * (prob[j] / 100.0);
upper = max(upper, i + time[j]);
}
}
double ret = 0.0;
for (int t = s; t <= upper; t++) {
ret += memo[t] * (t - s);
}
return ret;
}
};
Meidum (500点)
問題
あなたの庭には木がN本ある。その木はそれぞれheight[i]の高さを持っており、1日にadd[i]だけ伸びる。また、あなたはチェーンソーをM本もっていて、そのチェーンソーで木をdevice[j]の高さにすることができる。ただし、1日に各チェーンソーは1回しか使えず、木も1日に1回しか切れない。適切に木の手入れをしていった時のtime日目の木の高さの合計の最小値を求めよ。
解法
まず、着眼点としてはそれぞれの木はtime日の間でただ1回だけきればよく、それ以上切ってもチェーンソーの無駄遣いにしかなりません。
また、もしt日目に木を切ったとすれば最終日の木の高さはdevice[t] + add[i] * (time – t)です(tは1からtime)。
仮に木を切ることができないのであれば、その高さはheight[i] + add[i] * timeとなるが、木を切ることができないというのを言い換えると、height[i] + add[i] * timeがいずれのdevice[t] + add[i] * (time – t)よりも小さくなるということになります。
ということは、各木について何日目にどのチェーンソーを割り当てるのが最小になるかを求める問題になり、組み合わせ＋最小化ということで最小費用流が使えそうです。
問題はどうグラフを持つかですが、まず各木は1回しか切れないという条件から、sourceから各木のノードへcap=1, cost=0のエッジを引きます。
もし、各木を何日目かに切ったとするとそのあとに伸びる高さはadd[i] * jと表せるので、各木ノードと各日ノードの間にadd[i] * jのエッジを引きます。このとき、各木ノードにはそもそも1しかフローが流れないので、木が2日以上の日に切られることはありません。
次に、その日にどのチェーンソーを使うかという部分ですが、各日には各チェーンソーが1回しか使えないので、これは各日ノードから各チェーンソーノードにcap=1, cost=0のエッジを張ればいいです。
最後にチェーンソーは全体で合計time回ずつ使えて、使った時には残りの高さがdevice[i]になるので、各チェーンソーノードからsinkに向かってcap=time, cost=devide[i]のエッジを張ります。
以上で、大体OKなのですが、木を切れない場合があるので、それを別にノードとして用意します。このノードをUとすると各木ノード
からUに向かってcap=1, cost=height[i] + add[i] * timeのエッジを張り、さらにUからTへcap=N, cost=0のエッジをはればOKです。
後は木を切る本数N本をフローとして流して、最小費用流を求めればいいです。ちなみにBellman-Fordを使った実装で問題なく通りました。
struct MincostGraph {
static const long long infty = 1ll << 60;
struct Edge {
int to, cap;
Ty cost;
int rev;
};
vector<vector<Edge> > graph;
vector<Ty> dist;
vector<int> prevv;
vector<int> preve;
MincostGraph(int n)
: graph(n)
, dist(n)
, prevv(n)
, preve(n)
{
}
void addEdge(int from, int to, int cap, Ty cost) {
Edge e1 = { to, cap, cost, (int)graph[to].size() };
Edge e2 = { from, 0, -cost, (int)graph[from].size() };
graph[from].push_back(e1);
graph[to].push_back(e2);
}
Ty mincost(int s, int t, int f) {
Ty ret = 0;
while (f > 0) {
bellmanFord(s);
if (dist[t] == infty) return infty;
int cap = f;
for (int v = t; v != s; v = prevv[v]) {
Edge& e = graph[prevv[v]][preve[v]];
cap = min(cap, e.cap);
}
f -= cap;
ret += cap * dist[t];
for (int v = t; v != s; v = prevv[v]) {
Edge& e = graph[prevv[v]][preve[v]];
e.cap -= cap;
graph[v][e.rev].cap += cap;
}
}
return ret;
}
void bellmanFord(int s) {
fill(dist.begin(), dist.end(), (Ty)infty);
dist[s] = 0;
bool update = true;
while (update) {
update = false;
for (int i = 0; i < graph.size(); i++) {
if (dist[i] == infty) continue;
for (int j = 0; j < graph[i].size(); j++) {
Edge& e = graph[i][j];
if (e.cap > 0 && dist[e.to] > dist[i] + e.cost) {
dist[e.to] = dist[i] + e.cost;
prevv[e.to] = i;
preve[e.to] = j;
update = true;
}
}
}
}
}
};
class TaroCutting {
public:
int getNumber(vector<int> height, vector<int> add, vector<int> device, int time) {
int n = height.size();
int m = device.size();
int U = n + m + time;
int S = U + 1;
int T = S + 1;
MincostGraph<lint> graph(T+1);
for (int i = 0; i < n; i++) {
graph.addEdge(S, i, 1, 0);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < time; j++) {
graph.addEdge(i, n + j, 1, add[i] * j);
}
}
for (int i = 0; i < time; i++) {
for (int j = 0; j < m; j++) {
graph.addEdge(n + i, n + time + j, 1, 0);
}
}
for (int i = 0; i < m; i++) {
graph.addEdge(n + time + i, T, time, device[i]);
}
for (int i = 0; i < n; i++) {
graph.addEdge(i, U, 1, height[i] + add[i] * time);
}
graph.addEdge(U, T, n, 0);
return (int)graph.mincost(S, T, n);
}
};
まとめ
今回はEasyは結構簡単だった気がします。途中確率がパーセントで与えられているのに気付かなくて、少し時間かかりましたがw
Mediumはフローっぽいなぁとは思いましたが、グラフの作り方が思いつかず時間切れという感じです。
というわけで、今回の解説を終わります。最後までお読みいただきありがとうございました。