CODE FESTIVAL 2014 上海 : F - Yakiniku

こういう問題はいいね。
http://code-festival-2014-china-open.contest.atcoder.jp/tasks/code_festival_china_f

問題

N枚の焼肉を焼く。
各肉は時刻S[i]に網に乗せらる。この肉はT[i]に網から取り出されるとちょうど良い焼け具合になる。
ただし、肉を網から取り除く際、どの肉がどの肉かわからないため、いずれかの肉の焼け終わり時間T[i]に置いて、網にある肉をランダムで１枚取り除く。

各肉が、時間より焼き時間が短いまたは長くなる確率を求めよ。

解法

肉の追加および取り除きを時間順に処理する。
肉を追加する場合は、網の上にある肉の数をインクリメントするだけ。
問題は肉を取り除く場合である。

各肉がT[i]より前に取り除かれない確率は、S[i]＜T[x]＜T[i]である各肉の取り除き時刻T[x]に置いて、その時の肉の数M[T[x]]に対し(1-1/M[T[x]])を全て掛けたものである。

複数の値の積を取るため、SegTreeや平方分割、logを取って累積和を取る方法がある。
以下のコードは平方分割している。

T[i]より前に肉が取り除かれない確率がわかれば、それに1/M[T[i]]を掛けたものが時間通りに取り除かれる確率であり、(1-1/M[T[i]])を掛けたものが焼き時間が超過する確率である。
また、上記確率を1から引けば焼き時間が短くなる場合を求められる。

int N;
int S[102000],T[102000];
double un[102000],sc[102000];

vector<pair<int,int> > ev;
vector<int> keep;
int num;
double rat[102000],rat300[102000];

double dodo(int c) {
	double k=1;
	while(c%300 && c<keep.size()) k*=rat[c++];
	while(c<keep.size()) k*=rat300[c/300], c+=300;
	return k;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i]>>T[i];
		ev.push_back(make_pair(S[i],i));
		ev.push_back(make_pair(T[i],i));
	}
	FOR(i,102000) rat300[i]=1;
	sort(ALL(ev));
	
	FOR(i,ev.size()) {
		x=ev[i].second;
		if(S[x]==ev[i].first) {
			num++;
		}
		else {
			vector<int>::iterator it=lower_bound(keep.begin(),keep.end(),S[x]);
			double k=dodo(it-keep.begin());
			un[x]=1-k;
			sc[x]=(1.0-un[x])*(num-1)/num;
			
			rat[keep.size()]=(num-1.0)/num;
			rat300[keep.size()/300]*=rat[keep.size()];
			keep.push_back(T[x]);
			
			num--;
		}
	}
	
	FOR(i,N) _P("%.12lf %.12lf\n",un[i],sc[i]);
}

まとめ

最初log取って累積和取ったらlog(0)が登場して失敗したけど、0を10^-100とかで置き換えればよかったかもね。