結果

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

ソースコード

diff # 

def main():
    import sys
    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)

    P_known = [[p / 100.0 for p in row] for row in P]
    s_initial_list = [[4 - s for s in row] for row in S]

    E_prev = [[0.0 for _ in range(C)] for _ in range(R)]
    E = [[0.0 for _ in range(C)] for _ in range(R)]

    iteration = 0
    while True:
        max_diff = 0.0
        for i in range(R):
            for j in range(C):
                p_front = E_prev[i-1][j] if i > 0 else 0.0
                p_left = E_prev[i][j-1] if j > 0 else 0.0
                p_right = E_prev[i][j+1] if j < C-1 else 0.0

                sum_prob_known = 0.0
                sum_prob_unknown = 0.0

                has_front = i > 0
                has_left = j > 0
                has_right = j < C-1

                front_values = [0, 1] if has_front else [0]
                left_values = [0, 1] if has_left else [0]
                right_values = [0, 1] if has_right else [0]

                for front in front_values:
                    for left in left_values:
                        for right in right_values:
                            prob_front = (p_front if front else (1 - p_front)) if has_front else 1.0
                            prob_left = (p_left if left else (1 - p_left)) if has_left else 1.0
                            prob_right = (p_right if right else (1 - p_right)) if has_right else 1.0

                            prob = prob_front * prob_left * prob_right

                            k = front + left + right

                            s_k = s_initial_list[i][j]
                            if s_k + k >= 4:
                                sum_prob_known += prob

                            if 0 + k >= 4:
                                sum_prob_unknown += prob

                s_k = s_initial_list[i][j]
                if s_k >= 4:
                    term_known = 1.0
                else:
                    term_known = sum_prob_known

                contribution_known = P_known[i][j] * term_known
                contribution_unknown = (1 - P_known[i][j]) * sum_prob_unknown
                new_e = contribution_known + contribution_unknown

                diff = abs(new_e - E_prev[i][j])
                if diff > max_diff:
                    max_diff = diff
                E[i][j] = new_e

        if max_diff < 1e-12:
            break

        for i in range(R):
            for j in range(C):
                E_prev[i][j] = E[i][j]

        iteration += 1
        if iteration > 1000:
            break

    total = sum(sum(row) for row in E)
    print("{0:.12f}".format(total))

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