結果
問題 | No.309 シャイな人たち (1) |
ユーザー | maspy |
提出日時 | 2020-05-16 16:46:57 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,316 ms / 4,000 ms |
コード長 | 1,242 bytes |
コンパイル時間 | 99 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,656 KB |
最終ジャッジ日時 | 2024-09-22 12:25:11 |
合計ジャッジ時間 | 14,448 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 993 ms
11,524 KB |
testcase_01 | AC | 1,163 ms
11,532 KB |
testcase_02 | AC | 756 ms
11,528 KB |
testcase_03 | AC | 1,048 ms
11,528 KB |
testcase_04 | AC | 100 ms
10,752 KB |
testcase_05 | AC | 375 ms
11,136 KB |
testcase_06 | AC | 753 ms
11,400 KB |
testcase_07 | AC | 769 ms
11,532 KB |
testcase_08 | AC | 1,077 ms
11,656 KB |
testcase_09 | AC | 1,184 ms
11,656 KB |
testcase_10 | AC | 1,316 ms
11,656 KB |
testcase_11 | AC | 1,273 ms
11,652 KB |
testcase_12 | AC | 1,112 ms
11,656 KB |
testcase_13 | AC | 29 ms
10,752 KB |
testcase_14 | AC | 29 ms
10,752 KB |
testcase_15 | AC | 303 ms
11,136 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)