結果
問題 | No.309 シャイな人たち (1) |
ユーザー | maspy |
提出日時 | 2020-05-16 16:46:57 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,190 ms / 4,000 ms |
コード長 | 1,242 bytes |
コンパイル時間 | 136 ms |
コンパイル使用メモリ | 11,952 KB |
実行使用メモリ | 11,040 KB |
最終ジャッジ日時 | 2023-10-23 18:37:53 |
合計ジャッジ時間 | 13,472 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 904 ms
11,040 KB |
testcase_01 | AC | 1,042 ms
10,780 KB |
testcase_02 | AC | 687 ms
10,780 KB |
testcase_03 | AC | 957 ms
11,040 KB |
testcase_04 | AC | 95 ms
10,244 KB |
testcase_05 | AC | 348 ms
10,432 KB |
testcase_06 | AC | 683 ms
10,780 KB |
testcase_07 | AC | 711 ms
10,780 KB |
testcase_08 | AC | 963 ms
11,040 KB |
testcase_09 | AC | 1,083 ms
11,040 KB |
testcase_10 | AC | 1,190 ms
11,040 KB |
testcase_11 | AC | 1,181 ms
11,040 KB |
testcase_12 | AC | 1,047 ms
11,040 KB |
testcase_13 | AC | 29 ms
10,152 KB |
testcase_14 | AC | 29 ms
10,152 KB |
testcase_15 | AC | 287 ms
10,432 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)