結果

問題 No.813 ユキちゃんの冒険
ユーザー qwewe
提出日時 2025-05-14 12:55:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,585 bytes
コンパイル時間 385 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 123,520 KB
最終ジャッジ日時 2025-05-14 12:55:50
合計ジャッジ時間 5,458 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from decimal import Decimal, getcontext

getcontext().prec = 50  # High precision to handle up to 18 decimal places

def main():
    N = int(sys.stdin.readline())
    p = Decimal(sys.stdin.readline())
    q = Decimal(sys.stdin.readline())
    one = Decimal(1)
    zero = Decimal(0)

    # Initialize DP arrays. dp[i][d] is the probability of being at gate i with direction d.
    # Using lists of Decimal for higher precision.
    prev_dp = [[zero] * 2 for _ in range(N + 2)]  # gates 0 to N+1, directions 0 and 1
    prev_dp[1][0] = one  # start at gate 1, moving forward

    r = zero
    epsilon = Decimal('1e-30')  # Convergence threshold
    max_iterations = 1000000  # Prevent infinite loop

    for _ in range(max_iterations):
        next_dp = [[zero] * 2 for _ in range(N + 2)]
        delta_r = zero

        for i in range(1, N + 1):
            for d in [0, 1]:
                current = prev_dp[i][d]
                if current == zero:
                    continue

                # Escape (probability p)
                p_cont = current * p
                if d == 0:
                    next_i = i - 1
                    next_direction = 1
                else:
                    next_i = i + 1
                    next_direction = 0

                if next_i == 0:
                    delta_r += p_cont
                elif 1 <= next_i <= N:
                    next_dp[next_i][next_direction] += p_cont

                # Pass through (probability q)
                q_cont = current * q
                if d == 0:
                    next_i_pass = i + 1
                    next_direction_pass = 0
                else:
                    next_i_pass = i - 1
                    next_direction_pass = 1

                if next_i_pass == 0:
                    delta_r += q_cont
                elif 1 <= next_i_pass <= N:
                    next_dp[next_i_pass][next_direction_pass] += q_cont

        r += delta_r

        # Check for convergence
        converged = True
        for i in range(N + 2):
            for d in [0, 1]:
                diff = abs(prev_dp[i][d] - next_dp[i][d])
                if diff > epsilon:
                    converged = False
                    break
            if not converged:
                break

        if converged:
            break

        prev_dp, next_dp = next_dp, prev_dp  # Swap for next iteration

    # Output with sufficient precision
    print("{0:.20f}".format(r).rstrip('0').rstrip('.') if '.' in "{0:.20f}".format(r) else "{0:.20f}".format(r))

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