結果

問題 No.309 シャイな人たち (1)
ユーザー gew1fw
提出日時 2025-06-12 20:21:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,485 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 77,292 KB
最終ジャッジ日時 2025-06-12 20:21:47
合計ジャッジ時間 2,187 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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)
    
    # Precompute neighbors
    neighbors = [[[] for _ in range(C)] for __ in range(R)]
    for i in range(R):
        for j in range(C):
            if i > 0:
                neighbors[i][j].append((i-1, j))
            if j > 0:
                neighbors[i][j].append((i, j-1))
            if j < C-1:
                neighbors[i][j].append((i, j+1))
    
    # Initialize Q
    Q = [[0.5 for _ in range(C)] for __ in range(R)]
    
    tolerance = 1e-9
    max_iter = 100000
    converged = False
    
    for _ in range(max_iter):
        max_change = 0.0
        for i in range(R):
            for j in range(C):
                p = P[i][j] / 100.0
                s = S[i][j]
                m = len(neighbors[i][j])
                
                if p == 0.0:
                    new_q = 0.0
                else:
                    if m < s:
                        new_q = 0.0
                    else:
                        sum_terms = 0.0
                        for mask in range(0, 1 << m):
                            bits = bin(mask)[2:].zfill(m)
                            cnt = bits.count('1')
                            if cnt < s:
                                continue
                            term = 1.0
                            for k in range(m):
                                ni, nj = neighbors[i][j][k]
                                if bits[k] == '1':
                                    term *= Q[ni][nj]
                                else:
                                    term *= (1.0 - Q[ni][nj])
                            sum_terms += term
                        new_q = p * sum_terms
                
                change = abs(Q[i][j] - new_q)
                if change > max_change:
                    max_change = change
                Q[i][j] = new_q
        
        if max_change < tolerance:
            break
    
    # Calculate the sum
    total = 0.0
    for i in range(R):
        for j in range(C):
            total += Q[i][j]
    
    print("{0:.10f}".format(total))

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