結果

問題 No.309 シャイな人たち (1)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:17:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,542 bytes
コンパイル時間 431 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 76,800 KB
最終ジャッジ日時 2025-06-12 20:19:18
合計ジャッジ時間 2,067 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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_grid = []
    for _ in range(R):
        row = list(map(int, input[idx:idx+C]))
        idx += C
        p_grid.append([x / 100.0 for x in row])
    
    s_grid = []
    for _ in range(R):
        row = list(map(int, input[idx:idx+C]))
        idx += C
        s_grid.append(row)
    
    # Precompute neighbors for each cell
    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))
    
    E = [[0.0 for _ in range(C)] for _ in range(R)]
    max_iterations = 100000
    tolerance = 1e-9

    for _ in range(max_iterations):
        E_new = [[0.0 for _ in range(C)] for _ in range(R)]
        for i in range(R):
            for j in range(C):
                p = p_grid[i][j]
                s = s_grid[i][j]
                m = len(neighbors[i][j])
                if m == 0:
                    if s == 0:
                        case2 = 1.0
                    else:
                        case2 = 0.0
                else:
                    total = 0.0
                    for bits in range(0, 1 << m):
                        s_count = 0
                        prob = 1.0
                        for k in range(m):
                            ni, nj = neighbors[i][j][k]
                            if (bits >> k) & 1:
                                s_count += 1
                                prob *= E[ni][nj]
                            else:
                                prob *= (1 - E[ni][nj])
                        if s_count >= s:
                            total += prob
                    case2 = total
                E_new[i][j] = p * case2
        
        # Check for convergence
        converged = True
        for i in range(R):
            for j in range(C):
                if abs(E[i][j] - E_new[i][j]) > tolerance:
                    converged = False
                    break
            if not converged:
                break
        if converged:
            break
        E = E_new
    
    # Calculate the expected value
    expected = 0.0
    for row in E:
        expected += sum(row)
    
    print("{0:.10f}".format(expected))

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