結果

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

ソースコード

diff # 

import sys

def calc_Q(m, s, ps):
    if m == 0:
        return 1.0 if s <= 0 else 0.0
    elif m == 1:
        p = ps[0]
        if s <= 0:
            return 1.0
        elif s == 1:
            return p
        else:
            return 0.0
    elif m == 2:
        p1, p2 = ps
        if s <= 0:
            return 1.0
        elif s == 1:
            return 1.0 - (1.0 - p1) * (1.0 - p2)
        elif s == 2:
            return p1 * p2
        else:
            return 0.0
    elif m == 3:
        p1, p2, p3 = ps
        if s <= 0:
            return 1.0
        elif s == 1:
            return 1.0 - (1.0 - p1) * (1.0 - p2) * (1.0 - p3)
        elif s == 2:
            return (p1 * p2) + (p1 * p3) + (p2 * p3) - 2.0 * p1 * p2 * p3
        elif s == 3:
            return p1 * p2 * p3
        else:
            return 0.0

def main():
    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)

    E = [[0.0 for _ in range(C)] for __ in range(R)]
    for i in range(R):
        for j in range(C):
            if S[i][j] == 0:
                E[i][j] = P[i][j] / 100.0
            else:
                E[i][j] = 0.0

    eps = 1e-8
    max_iter = 100000
    for _ in range(max_iter):
        E_prev = [row[:] for row in E]
        diff = 0.0
        for i in range(R):
            for j in range(C):
                if P[i][j] == 0:
                    continue
                neighbors = []
                if i > 0:
                    neighbors.append(E_prev[i-1][j])
                if j > 0:
                    neighbors.append(E_prev[i][j-1])
                if j < C - 1:
                    neighbors.append(E_prev[i][j+1])
                m = len(neighbors)
                s = S[i][j]
                if m == 0:
                    q = 1.0 if s <= 0 else 0.0
                else:
                    q = calc_Q(m, s, neighbors)
                new_val = (P[i][j] / 100.0) * q
                diff += (E[i][j] - new_val) ** 2
                E[i][j] = new_val
        if diff < eps:
            break

    total = sum(sum(row) for row in E)
    print("{0:.10f}".format(total))

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