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