結果

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

ソースコード

diff #
raw source code 

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

    P = []
    for _ in range(R):
        row = list(map(int, input[idx:idx+C]))
        idx += C
        P.append(row)

    S = []
    for _ in range(R):
        row = list(map(int, input[idx:idx+C]))
        idx += C
        S.append(row)

    # Initialize Q and E
    Q = [[0.5 for _ in range(C)] for __ in range(R)]
    E = [[P[i][j] / 100.0 for j in range(C)] for i in range(R)]

    threshold = 1e-9
    max_iter = 100000

    for iter in range(max_iter):
        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):
                # Determine neighbors and their p values
                p_front = 0.0
                if i > 0:
                    ni, nj = i - 1, j
                    p_front = E[ni][nj] * Q[ni][nj]

                p_left = 0.0
                if j > 0:
                    ni, nj = i, j - 1
                    p_left = E[ni][nj] * Q[ni][nj]

                p_right = 0.0
                if j < C - 1:
                    ni, nj = i, j + 1
                    p_right = E[ni][nj] * Q[ni][nj]

                s_ij = S[i][j]
                total = 0.0

                # Enumerate all 8 possible cases
                for y1 in [0, 1]:
                    for y2 in [0, 1]:
                        for y3 in [0, 1]:
                            prob = 1.0
                            if y1 == 1:
                                prob *= p_front
                            else:
                                prob *= (1 - p_front)

                            if y2 == 1:
                                prob *= p_left
                            else:
                                prob *= (1 - p_left)

                            if y3 == 1:
                                prob *= p_right
                            else:
                                prob *= (1 - p_right)

                            if (y1 + y2 + y3) >= s_ij:
                                total += prob

                new_Q[i][j] = total
                diff = abs(new_Q[i][j] - Q[i][j])
                if diff > max_diff:
                    max_diff = diff

        # Update Q
        for i in range(R):
            for j in range(C):
                Q[i][j] = new_Q[i][j]

        if max_diff < threshold:
            break

    # Compute the total expected value
    total = 0.0
    for i in range(R):
        for j in range(C):
            total += E[i][j] * Q[i][j]

    print("{0:.10f}".format(total))

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