結果

問題 No.1173 Endangered Species
ユーザー lam6er
提出日時 2025-03-26 15:45:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 142 ms / 2,000 ms
コード長 1,616 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 124,544 KB
最終ジャッジ日時 2025-03-26 15:45:38
合計ジャッジ時間 2,864 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    
    p = list(map(float, data[idx:idx+N]))
    idx += N
    
    q = list(map(float, data[idx:idx+N]))
    idx += N
    
    A = list(map(int, data[idx:idx+N]))
    idx += N
    
    def compute_F_Fprime(s):
        F = 0.0
        Fprime = 0.0
        for j in range(N):
            pj = p[j]
            qj = q[j]
            denom = 1.0 - qj * s
            term_F = pj * (1.0 - qj) / denom
            F += term_F
            term_Fprime = pj * (1.0 - qj) * qj / (denom ** 2)
            Fprime += term_Fprime
        return F, Fprime
    
    # Initial guess: compute F(0)
    s = sum(pj * (1.0 - qj) for pj, qj in zip(p, q))
    if s == 0.0:
        s = 0.5  # avoid division by zero in Newton step if initial sum is 0
    
    for _ in range(100):
        F, Fprime = compute_F_Fprime(s)
        if F == s:
            break
        denominator = Fprime - 1.0
        if denominator == 0:
            break
        delta = (F - s) / denominator
        s_new = s - delta
        if abs(delta) < 1e-12:
            s = s_new
            break
        s = s_new
    
    sum_log = 0.0
    for i in range(N):
        a = A[i]
        if a == 0:
            continue
        qi = q[i]
        denom = 1.0 - qi * s
        if denom <= 0:
            xi = 0.0
        else:
            xi = (1.0 - qi) / denom
        sum_log += a * math.log(xi)
    
    # Handle the case when all A are zero
    print("{0:.10f}".format(sum_log))

if __name__ == '__main__':
    main()
0