Codeforces Beta Round #99 (Div. 1) C : Mushroom Gnomes - 2
問題概要
木が数直線上にN(<10^5)本並んでいて、各木は高さと右に倒れる確率、左に倒れる確率が決まっている。また同じ数直線上にM(<10^5)個のキノコがあって、各キノコには得点が定められている。木が倒れてきたらキノコは潰れてしまう。最終的に潰されなかったキノコの得点の和の期待値を求める問題。
解法
平面走査法するだけ。ただし、確率を計算する時は0のときに注意する必要があり、またアンダーフローにも気を配る必要がある。前者は0の出現回数をカウンタで持っておき、後者は対数に落とすことによって回避可能。
acceptされたコード
#include <cstdio> #include <set> #include <algorithm> #include <cmath> using namespace std; const int MAX_N = 1e5; const int MAX_M = 1e4; struct tree{ int pos, h; double l, r; }; struct mash{ int pos, a; }; bool operator<(const mash& lhs, const mash& rhs){ return lhs.pos < rhs.pos; } bool operator<(const tree& lhs, const tree& rhs){ return lhs.pos < rhs.pos; } int N, M; tree ts[MAX_N]; mash ms[MAX_M]; pair<int,int> rights[MAX_N], lefts[MAX_N];//(先端、tsのindex) void init(){ scanf("%d%d", &N, &M); for(int i=0; i<N; i++){ int a, b, c, d; scanf("%d%d%d%d", &a, &b,&c,&d); ts[i] = (tree){a, b, c/100.0, d/100.0}; } for(int i=0; i<M; i++){ int x, y; scanf("%d%d", &x, &y); ms[i] = (mash){x, y}; } } double solve(){ set<int> line; for(int i=0; i<N; i++){ line.insert(ts[i].pos); line.insert(ts[i].pos + ts[i].h); line.insert(ts[i].pos - ts[i].h); } for(int i=0; i<M; i++){ line.insert(ms[i].pos); } sort(ts, ts + N); sort(ms, ms + M); for(int i=0; i<N; i++){ rights[i] = make_pair(ts[i].pos + ts[i].h, i); lefts[i] = make_pair(ts[i].pos - ts[i].h, i); } sort(rights, rights + N); sort(lefts, lefts + N); double ans = 0.0; double left_prob = 1.0, right_prob = 1.0; //倒れてない確率 double left_log = 0.0, right_log = 0.0; int left_cnt = 0, right_cnt = 0; int mp = 0, rp = 0, lp = 0, tp = 0; for(set<int>::iterator itr=line.begin(); itr!=line.end(); itr++){ int cur = *itr; int tmp_tp = tp; //// //左に倒れているのを追加する while(lp< N && lefts[lp].first == cur){ int idx =lefts[lp].second; if(ts[idx].l < 1.0){ left_prob *= 1.0 - ts[idx].l; left_log += log(1.0 - ts[idx].l); } else{ left_cnt++; } lp++; } //左に倒れてるのを新たに取り除く while(tp < N && ts[tp].pos == cur){ if(ts[tp].l < 1.0){ left_prob /= 1.0 - ts[tp].l; left_log -= log(1.0 - ts[tp].l); } else{ left_cnt--; } tp++; } double lpp = left_cnt > 0 ? 0.0 : exp(left_log); double rpp = right_cnt > 0 ? 0.0 : exp(right_log); //// //マッシュルームは生きているか? while(mp < M && ms[mp].pos == cur){ ans += lpp * rpp * ms[mp++].a; } //右に倒れてるのを追加する while(rp < N && rights[rp].first == cur){ int idx =rights[rp].second; if(ts[idx].r < 1.0){ right_prob /= 1.0 - ts[idx].r; right_log -= log(1.0 - ts[idx].r); } else{ right_cnt--; } rp++; } //右に倒れているのを除く tp = tmp_tp; while(tp < N && ts[tp].pos == cur){ if(ts[tp].r < 1.0){ right_prob *= 1.0 - ts[tp].r; right_log += log(1.0 - ts[tp].r); } else{ right_cnt++; } tp++; } } return ans; } int main(){ init(); printf("%.8f\n", solve()); return 0; }