kmjp's blog

競技プログラミング参加記です

yukicoder : No.1173 Endangered Species

yukicoder

これ系ちゃんと練習しないとな。
https://yukicoder.me/problems/no/1173

問題

生物は1～Nのいずれかの個体値を持つ。
個体値iの生物は、生まれた翌日に何体かの個体を生み消滅する。その際以下が成り立つ。

  • 生む個体の数は、個体値に対するパラメータP[i]で定まり、k体生む確率は(1-Q[i])*Q[i]^kである。

また、生まれる個体の個体値の値iは、誰から生まれたかによらず確率P[i]をとる(P[i]の和は1である)

初期状態として各個体値iの生物の数A[i]が与えられる。
非常に長い時間がたったのち、個体数が0になっている確率の対数を求めよ。

解法

個体値iの生物から派生した個体がd日後に0体になっている確率をX(d,i)とする。
全体が0体になる確率は \displaystyle P=\prod_i X_{d,i}^{A_i}なので、対数を取ると \displaystyle log(P)=\sum_i \log(X_{d,i})*A_iである。

X(d,i)を個別に考えると面倒なので、個体値未確定の生物1体から派生した個体がd日後に0体になっている確率をY(d)とする。
\displaystyle Y_d=\sum_i P_iX_{d,i}で、 \displaystyle X_{d,i}=\sum_k (1-Q_i)Q_i^kY_d^k = \frac{1-Q_i}{1-Q_iY_d}となる。
すると
\displaystyle Y_{d+1}=\sum_i P_iX_{d+1,i} = \sum_i P_i\frac{1-Q_i}{1-Q_iY_d}となり、個々のXを考える必要がなくなる。
あとはこのYの極限を考えよう。

詳細はEditorialを参照していただくとして、この漸化式は単調増加でかつ極限を持つ。
よって極限値をYとし、 \displaystyle Y\le \sum_i P_iX_{d+1,i} = \sum_i P_i\frac{1-Q_i}{1-Q_iY}となる最小のYを求めよう。
これは二分探索で行えばよい。

int N;
double P[101010],Q[101010];
int A[101010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	FOR(i,N) cin>>Q[i];
	
	double L=0,R=1;
	FOR(i,100) {
		double M=(L+R)/2;
		double F=0;
		FOR(x,N) F+=P[x]*(1-Q[x])/(1-Q[x]*M);
		if(M<=F) L=M;
		else R=M;
	}
	
	double ret=0;
	FOR(i,N) {
		cin>>A[i];
		ret+=A[i]*log((1-Q[i])/(1-Q[i]*L));
	}
	_P("%.12lf\n",ret);
}

まとめ

本番は「N大きくて連立方程式には持ち込めないしな…」と唸ってました。