結果

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

ソースコード

diff #
raw source code 

import sys

def compute_probability(neighbors_q, S_ij):
    m = len(neighbors_q)
    if S_ij > m:
        return 0.0
    total = 0.0
    for mask in range(0, 1 << m):
        count = bin(mask).count('1')
        if count >= S_ij:
            prob = 1.0
            for k in range(m):
                if (mask >> k) & 1:
                    prob *= neighbors_q[k]
                else:
                    prob *= (1.0 - neighbors_q[k])
            total += prob
    return total

def main():
    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)
    
    # Convert P to probabilities
    p = [[P[i][j] / 100.0 for j in range(C)] for i in range(R)]
    
    # Initialize q
    q = [[0.0 for _ in range(C)] for _ in range(R)]
    
    threshold = 1e-9
    max_iterations = 10000
    for _ in range(max_iterations):
        q_new = [[0.0 for _ in range(C)] for _ in range(R)]
        for i in range(R):
            for j in range(C):
                # Collect neighbors' q values
                neighbors_q = []
                if i > 0:
                    neighbors_q.append(q[i-1][j])
                if j > 0:
                    neighbors_q.append(q[i][j-1])
                if j < C - 1:
                    neighbors_q.append(q[i][j+1])
                
                s_ij = S[i][j]
                prob = compute_probability(neighbors_q, s_ij)
                new_q = p[i][j] * prob
                q_new[i][j] = new_q
        
        # Check for convergence
        max_diff = 0.0
        for i in range(R):
            for j in range(C):
                diff = abs(q[i][j] - q_new[i][j])
                if diff > max_diff:
                    max_diff = diff
        if max_diff < threshold:
            break
        
        q = q_new
    
    # Calculate the expected total
    expected = 0.0
    for i in range(R):
        for j in range(C):
            expected += q[i][j]
    
    print("{0:.12f}".format(expected))

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