結果

問題 No.309 シャイな人たち (1)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:12:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,357 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 77,436 KB
最終ジャッジ日時 2025-06-12 20:16:23
合計ジャッジ時間 2,023 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def compute_probability(probs, t):
    m = len(probs)
    if m == 0:
        return 1.0 if t == 0 else 0.0

    dp = [[0.0] * (m + 1) for _ in range(m + 1)]
    dp[0][0] = 1.0

    for i in range(1, m + 1):
        p = probs[i - 1]
        for k in range(i + 1):
            if k - 1 >= 0:
                dp[i][k] += dp[i - 1][k - 1] * p
            dp[i][k] += dp[i - 1][k] * (1 - p)

    total = 0.0
    for k in range(t, m + 1):
        total += dp[m][k]
    return total

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    R = int(input[ptr])
    ptr += 1
    C = int(input[ptr])
    ptr += 1

    P = []
    for _ in range(R):
        row = list(map(int, input[ptr:ptr + C]))
        ptr += C
        P.append(row)
    
    S = []
    for _ in range(R):
        row = list(map(int, input[ptr:ptr + C]))
        ptr += C
        S.append(row)
    
    q = [[0.0 for _ in range(C)] for __ in range(R)]
    max_iterations = 100000
    threshold = 1e-9

    for _ in range(max_iterations):
        new_q = [[0.0 for _ in range(C)] for __ in range(R)]
        max_diff = 0.0

        for i in range(R):
            for j in range(C):
                p_zhi = P[i][j] / 100.0
                if p_zhi == 0.0:
                    new_q[i][j] = 0.0
                    continue

                s = S[i][j]
                k = 4 - s
                if k >= 4:
                    p_trigger = 1.0
                else:
                    t = 4 - k
                    neighs = []
                    if i > 0:
                        neighs.append(q[i-1][j])
                    if j > 0:
                        neighs.append(q[i][j-1])
                    if j < C - 1:
                        neighs.append(q[i][j+1])
                    m = len(neighs)
                    if m < t:
                        p_trigger = 0.0
                    else:
                        p_trigger = compute_probability(neighs, t)

                new_q[i][j] = p_zhi * p_trigger
                diff = abs(new_q[i][j] - q[i][j])
                if diff > max_diff:
                    max_diff = diff

        q = new_q
        if max_diff < threshold:
            break

    total = 0.0
    for i in range(R):
        for j in range(C):
            total += q[i][j]
    print("{0:.10f}".format(total))

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