結果
問題 | No.309 シャイな人たち (1) |
ユーザー | maspy |
提出日時 | 2020-05-16 16:47:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 148 ms / 4,000 ms |
コード長 | 1,242 bytes |
コンパイル時間 | 421 ms |
コンパイル使用メモリ | 81,804 KB |
実行使用メモリ | 119,288 KB |
最終ジャッジ日時 | 2023-10-23 18:37:56 |
合計ジャッジ時間 | 2,950 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 124 ms
115,156 KB |
testcase_01 | AC | 130 ms
117,156 KB |
testcase_02 | AC | 114 ms
115,160 KB |
testcase_03 | AC | 123 ms
117,176 KB |
testcase_04 | AC | 53 ms
66,096 KB |
testcase_05 | AC | 72 ms
81,652 KB |
testcase_06 | AC | 122 ms
115,156 KB |
testcase_07 | AC | 111 ms
113,080 KB |
testcase_08 | AC | 123 ms
117,176 KB |
testcase_09 | AC | 127 ms
117,204 KB |
testcase_10 | AC | 148 ms
119,288 KB |
testcase_11 | AC | 145 ms
119,288 KB |
testcase_12 | AC | 139 ms
119,276 KB |
testcase_13 | AC | 37 ms
53,420 KB |
testcase_14 | AC | 38 ms
53,420 KB |
testcase_15 | AC | 69 ms
79,008 KB |
ソースコード
import sys import itertools read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines H, W = map(int, readline().split()) readline() P = [] for _ in range(H): P += [0.0] + [0.01 * int(x) for x in readline().split()] readline() S = [] for _ in range(H): S += [4] + list(map(int, readline().split())) W += 1 # (bit列, n) = (挙手の状態, リーチ目人数) に対して確率を持つ dp = [0.0] * (W * (1 << W)) dp[0] = 1.0 mask = (1 << W) - 1 answer = 0 for p, s in zip(P, S): newdp = [0.0] * (W * (1 << W)) for i in range(W * (1 << W)): if dp[i] == 0.0: continue bit, n = divmod(i, W) # 無知 bit1 = (bit << 1) & mask newdp[bit1 * W] += dp[i] * (1 - p) # 知 s1 = s - (bit & 1) - (bit >> W - 1) if s1 > 1: # 挙手しない確定 newdp[bit1 * W] += dp[i] * p elif s1 == 1: # リーチ目に 1 人追加 newdp[bit1 * W + n + 1] += dp[i] * p else: # 挙手する確定 answer += (n + 1) * dp[i] * p bit1 |= (1 << n + 1) - 1 newdp[bit1 * W] += dp[i] * p dp = newdp print(answer)