結果

問題 No.309 シャイな人たち (1)
コンテスト
ユーザー しらっ亭
提出日時 2015-12-09 15:23:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,618 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 272 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 84,092 KB
最終ジャッジ日時 2024-09-15 05:51:20
合計ジャッジ時間 10,847 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

'''
O(R*C*4^C) のはずなのに通らない。泣きたい。
'''


def bitcount(x):
    """
    立っているbitの数
    """
    x = (x & 0x5555) + (x >> 1 & 0x5555)
    x = (x & 0x3333) + (x >> 2 & 0x3333)
    x = (x & 0x0f0f) + (x >> 4 & 0x0f0f)
    x = (x & 0x00ff) + (x >> 8 & 0x00ff)
    return x


def solve():
    R, C = map(int, input().split())
    P = []
    S = []

    input()
    for r in range(R):
        P.append([int(p) / 100 for p in input().split()])
    input()
    for r in range(R):
        S.append(list(map(int, input().split())))
    ans = 0

    c1 = 1 << C
    Y = [[0.0] * c1 for r in range(R)]
    # Y[r][i]: r 行目の手を挙げる挙げないの組み合わせが i になる確率

    for r in range(R):
        yr = Y[r]
        yr1 = Y[r - 1]
        pr = P[r]
        sr = S[r]

        for i in range(c1):
            # x: 自分たちの知ってる知ってないの組み合わせが i になる確率
            x = 1.0
            for c in range(C):
                if i & (1 << c):
                    x *= pr[c]
                else:
                    x *= (1 - pr[c])

            if x == 0:
                continue

            # 前の行の組み合わせ j ごとに足し合わせる
            for j in range(c1 if r else 1):
                if r > 0:
                    y = yr1[j]
                    if y == 0:
                        continue
                elif j == 0:
                    y = 1.0
                else:
                    continue

                # hand の添字は 1-indexed
                hand = 0

                for c in range(C):
                    if i & (1 << c):
                        p = 4 - sr[c]
                        if j & (1 << c):
                            p += 1
                        if p >= 4:
                            hand |= 1 << (c + 1)

                for lr in range(2):
                    for c in range(C):
                        d = (c if lr else C - 1 - c)
                        if i & (1 << d):
                            p = 4 - sr[d]
                            if hand & (1 << d):
                                p += 1
                            if hand & (1 << (d + 2)):
                                p += 1
                            if j & (1 << d):
                                p += 1
                            if p >= 4:
                                hand |= 1 << (d + 1)

                hand >>= 1
                yx = y * x
                yr[hand] += yx
                ans += bitcount(hand) * yx

    print(ans)


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