結果

問題 No.1173 Endangered Species
ユーザー lam6er
提出日時 2025-03-31 17:24:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 138 ms / 2,000 ms
コード長 1,744 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 124,644 KB
最終ジャッジ日時 2025-03-31 17:25:04
合計ジャッジ時間 2,955 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    
    p = list(map(float, input[ptr:ptr + N]))
    ptr += N
    
    q = list(map(float, input[ptr:ptr + N]))
    ptr += N
    
    A = list(map(int, input[ptr:ptr + N]))
    ptr += N

    # Solve for s using Newton-Raphson
    s = 0.5  # Initial guess
    eps = 1e-12
    max_iterations = 100
    for _ in range(max_iterations):
        sum1 = 0.0
        sum2 = 0.0
        for j in range(N):
            pj = p[j]
            qj = q[j]
            denom = 1.0 - qj * s
            if denom <= 0:
                denom = 1e-12  # Prevent division by zero, though problem states it's unnecessary
            term1 = pj * (1.0 - qj) / denom
            sum1 += term1
            term2 = term1 * qj / denom
            sum2 += term2
        
        g = sum1 - s
        if abs(g) < 1e-15:
            break
        g_deriv = sum2 - 1.0
        if g_deriv == 0:
            break  # Prevent division by zero
        s_new = s - g / g_deriv
        if abs(s_new - s) < eps:
            s = s_new
            break
        s = s_new

    # Calculate log probability
    log_p = 0.0
    for i in range(N):
        ai = A[i]
        if ai == 0:
            continue
        qi = q[i]
        denom = 1.0 - qi * s
        if denom <= 0:
            ei = 0.0  # Should not happen according to problem constraints
        else:
            ei = (1.0 - qi) / denom
        if ei <= 0.0:
            # This would be an error as per problem statement
            ei = 1e-20
        log_p += ai * math.log(ei)
    
    # Print with sufficient precision
    print("{0:.10f}".format(log_p))

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