問題一覧 > 通常問題

No.1173 Endangered Species

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-5}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 28
作問者 : optopt / テスター : koprickykopricky
9 ProblemId : 4255 / 出題時の順位表
問題文最終更新日: 2020-08-24 17:04:29

問題文

ある生物の各個体は,生まれると同時に個体値として $1, \dots, N$ のいずれかの整数値が与えられます. また,生まれてからちょうど $1$ 日後に $0$ 個以上の個体を生み,それと同時に自身は消滅します.

生まれる個体の個体値と,$1$ 個体が生む個体数は,以下のように他の個体とは独立に確率的に定まります:

  • 生まれる個体の個体値が $i\ (=1,\dots,N)$ である確率は $p_i$,
  • 個体値 $i$ の $1$ 個体が生む個体数が $k\ (=0,1,\dots)$ である確率は $(1-q_i) q_i^k$.

今,個体値 $1,\dots,N$ の個体が $A_1,\dots,A_N$ 個ずつ生まれました.他に個体は存在しません. $10^{10^{100}}$ 日後に生物が絶滅している,つまり個体数が $0$ になっている確率 $P$ を求めて下さい.

$P$ は非常に小さい可能性があるため,自然対数 $\log P$ の値を出力してください. この問題の制約の下,$P > 0$ となることが示せます.

入力

入力は以下の形式で与えられる:

$N$
$p_1 \quad p_2 \quad \cdots \quad p_N$
$q_1 \quad q_2 \quad \cdots \quad q_N$
$A_1 \quad A_2 \quad \cdots \quad A_N$
  • $N,\ A_1,\dots,A_N$ は整数
  • $p_1,\dots,p_N,\ q_1,\dots,q_N$ は小数点以下 $6$ 桁の小数($6$ 桁になるよう $0$ 埋めされる)
  • $1 \leq N \leq 10^5$
  • $0 < p_i \leq 1 \quad (1 \leq i \leq N)$
  • $\sum_{i=1}^N p_i = 1$
  • $\color{red}{0.6 \leq q_i \leq 0.9} \quad (1 \leq i \leq N)$
  • $0 \leq A_i \leq 10^4 \quad (1 \leq i \leq N)$

補足: 少々不自然に見える $q_i$ に関する制約は,double 型を使えば数値誤差をさほど気にしなくても正解となるようにするためのものです.

出力

$10^{10^{100}}$ 日後に生物が絶滅している確率 $P$ に対し,自然対数 $\log P$ の値を出力せよ. 最後に改行を出力すること.

なお,想定解答との絶対誤差または相対誤差が $10^{-5}$ 以下であれば正解となる.

サンプル

サンプル1
入力
1
1.000000
0.600000
1
出力
-0.4054651081

全ての個体が,確率 $(2/5) \times (3/5)^k$ で $k$ 個の個体を生みます.

計算過程は省略しますが,絶滅確率は $P = 2/3$ です. そのため $\log (2/3) = -0.4054651081\dots$ の近似値を出力します.

サンプル2
入力
2
0.900000 0.100000
0.900000 0.900000
0 0
出力
0

最初から絶滅している場合もあります.

サンプル3
入力
6
0.332343 0.068862 0.076451 0.120693 0.263170 0.138481
0.839426 0.728493 0.810372 0.839476 0.827081 0.890719
7481 5029 9181 6723 8291 9836
出力
-75700.00551

$P \simeq 10^{-32876}$ で非常に小さいです.絶滅危惧種ではありません.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。