結果

問題 No.309 シャイな人たち (1)
ユーザー gew1fw
提出日時 2025-06-12 20:17:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,183 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,672 KB
実行使用メモリ 77,312 KB
最終ジャッジ日時 2025-06-12 20:18:47
合計ジャッジ時間 2,212 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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)
    
    # Convert P to probabilities
    for i in range(R):
        for j in range(C):
            P[i][j] /= 100.0
    
    x_prev = [[0.0 for _ in range(C)] for __ in range(R)]
    epsilon = 1e-9
    max_iterations = 10000

    for _ in range(max_iterations):
        x_new = [[0.0 for _ in range(C)] for __ in range(R)]
        for i in range(R):
            for j in range(C):
                adj = []
                if i > 0:
                    adj.append((i-1, j))
                if j > 0:
                    adj.append((i, j-1))
                if j < C - 1:
                    adj.append((i, j+1))
                m = len(adj)
                x_adj = [x_prev[ni][nj] for (ni, nj) in adj]
                
                # Case 1: K_ij = 1
                p_know = P[i][j]
                s_ij = S[i][j]
                t_case1 = s_ij
                if t_case1 > m:
                    P_case1 = 0.0
                else:
                    sum_p = 0.0
                    for mask in range(1 << m):
                        bits = bin(mask).count('1')
                        if bits >= t_case1:
                            prob = 1.0
                            for k in range(m):
                                if (mask >> k) & 1:
                                    prob *= x_adj[k]
                                else:
                                    prob *= (1 - x_adj[k])
                            sum_p += prob
                    P_case1 = sum_p
                
                # Case 2: K_ij = 0
                t_case2 = 4
                if t_case2 > m:
                    P_case2 = 0.0
                else:
                    sum_p = 0.0
                    for mask in range(1 << m):
                        bits = bin(mask).count('1')
                        if bits >= t_case2:
                            prob = 1.0
                            for k in range(m):
                                if (mask >> k) & 1:
                                    prob *= x_adj[k]
                                else:
                                    prob *= (1 - x_adj[k])
                            sum_p += prob
                    P_case2 = sum_p
                
                x_new[i][j] = p_know * P_case1 + (1 - p_know) * P_case2
        
        # Check convergence
        max_diff = 0.0
        for i in range(R):
            for j in range(C):
                diff = abs(x_prev[i][j] - x_new[i][j])
                if diff > max_diff:
                    max_diff = diff
        if max_diff < epsilon:
            break
        x_prev = x_new
    
    expected = 0.0
    for i in range(R):
        for j in range(C):
            expected += x_prev[i][j]
    
    print("{0:.10f}".format(expected))

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