結果

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

ソースコード

diff #
raw source code 

def bitcount(x):
    """
    立っているbitの数
    """
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f)
    x = (x & 0x00ff00ff00ff00ff) + (x >> 8 & 0x00ff00ff00ff00ff)
    x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff)
    return (x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff)


def calc(i, j, s, C):
    """
    :param i: 自分たちの行の知ってる知ってないの状態
    :param j: 前の行の挙げてる挙げてないの状態
    :param s: 自分たちの行のシャイ度
    :param C: 横幅
    :return: 自分たちがどのような挙手状態になるか
    """

    ret = 0
    p = [0] * C
    for c in range(C):
        c1 = 1 << c
        if i & c1:
            p[c] = 4 - s[c]
            if j & c1:
                p[c] += 1
            if p[c] >= 4:
                ret |= c1

    pret = 0
    while pret != ret:
        for c in range(C):
            c1 = 1 << c
            if ret & c1 and pret ^ c1:
                if c > 0:
                    p[c - 1] += 1
                    if p[c - 1] >= 4:
                        ret |= 1 << (c - 1)
                if c < C - 1:
                    p[c + 1] += 1
                    if p[c + 1] >= 4:
                        ret |= 1 << (c + 1)
        pret = ret
    # print((bin(i), bin(j), s, bin(ret)))
    return ret


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

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

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

    for r in range(R):
        yr = Y[r]

        for i in range(1 << C):
            x = 1.0
            for c in range(C):
                if i & (1 << c):
                    x *= P[r][c] / 100
                else:
                    x *= (100 - P[r][c]) / 100

            # x: 自分たちの知ってる知ってないの組み合わせが i になる確率

            for j in range(1 << C):
                if r > 0:
                    y = Y[r - 1][j]
                elif j == 0:
                    y = 1.0
                else:
                    continue

                z = calc(i, j, S[r], C)
                yr[z] += y * x

        for i in range(1 << C):
            # print((bin(i), bitcount(i), yr[i]))
            ans += bitcount(i) * yr[i]
    print(ans)


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