結果

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

ソースコード

diff # 

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)
    
    # Initialize E
    E = [[0.5 for _ in range(C)] for _ in range(R)]
    threshold = 1e-9
    max_iter = 100000  # To prevent infinite loops, though unlikely
    iter_count = 0

    while iter_count < max_iter:
        E_new = [[0.0 for _ in range(C)] for _ in range(R)]
        max_change = 0.0

        for i in range(R):
            for j in range(C):
                if P[i][j] == 0:
                    E_new[i][j] = 0.0
                    continue

                p_neighbors = []
                # front: i-1, j
                if i > 0:
                    p_neighbors.append(E[i-1][j])
                # left: i, j-1
                if j > 0:
                    p_neighbors.append(E[i][j-1])
                # right: i, j+1
                if j < C - 1:
                    p_neighbors.append(E[i][j+1])

                n = len(p_neighbors)
                required = S[i][j]

                total = 0.0
                for mask in range(1 << n):
                    bits = bin(mask).count('1')
                    if bits < required:
                        continue
                    prob = 1.0
                    for k in range(n):
                        if (mask >> k) & 1:
                            prob *= p_neighbors[k]
                        else:
                            prob *= (1 - p_neighbors[k])
                    total += prob

                e_new = (P[i][j] / 100.0) * total
                E_new[i][j] = e_new
                change = abs(e_new - E[i][j])
                if change > max_change:
                    max_change = change

        # Check for convergence
        if max_change < threshold:
            break

        # Update E
        E = E_new
        iter_count += 1

    # Compute the expected total
    expected = 0.0
    for i in range(R):
        for j in range(C):
            expected += E[i][j]
    
    # Print with sufficient precision
    print("{0:.10f}".format(expected))

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