結果

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

ソースコード

diff #
raw source code 

import sys
from itertools import combinations

def main():
    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 for each cell
    neighbors = [[[] for _ in range(C)] for _ in range(R)]
    for i in range(R):
        for j in range(C):
            # Check up
            if i > 0:
                neighbors[i][j].append((i-1, j))
            # Check left
            if j > 0:
                neighbors[i][j].append((i, j-1))
            # Check right
            if j < C - 1:
                neighbors[i][j].append((i, j+1))
    
    # Initialize x
    x = [[0.0 for _ in range(C)] for _ in range(R)]
    for i in range(R):
        for j in range(C):
            p = P[i][j] / 100.0
            s = S[i][j]
            initial_points = 4 - s
            t_ij = max(0, 4 - initial_points)
            if t_ij == 0:
                x[i][j] = p
    
    # Iterate until convergence
    max_iterations = 100000
    threshold = 1e-12
    for _ in range(max_iterations):
        new_x = [[0.0 for _ in range(C)] for _ in range(R)]
        for i in range(R):
            for j in range(C):
                p = P[i][j] / 100.0
                if p == 0.0:
                    new_x[i][j] = 0.0
                    continue
                s = S[i][j]
                initial_points = 4 - s
                t_ij = max(0, 4 - initial_points)
                
                # Check if initial_points is sufficient on its own
                if initial_points >= 4:
                    new_x[i][j] = p
                    continue
                
                # Get active neighbors
                act_neighbors = neighbors[i][j]
                m = len(act_neighbors)
                
                if m < t_ij:
                    prob = 0.0
                else:
                    prob = 0.0
                    # Enumerate all subsets of size >= t_ij
                    for k in range(t_ij, m + 1):
                        for subset in combinations(act_neighbors, k):
                            product = 1.0
                            for (ni, nj) in act_neighbors:
                                if (ni, nj) in subset:
                                    product *= x[ni][nj]
                                else:
                                    product *= (1.0 - x[ni][nj])
                            prob += product
                new_x[i][j] = p * prob
        
        # Check for convergence
        max_change = 0.0
        for i in range(R):
            for j in range(C):
                diff = abs(new_x[i][j] - x[i][j])
                if diff > max_change:
                    max_change = diff
        x = new_x
        if max_change < threshold:
            break
    
    # Calculate the expected value
    expected = 0.0
    for i in range(R):
        for j in range(C):
            expected += x[i][j]
    
    print("{:.10f}".format(expected))

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