結果
問題 | No.1151 チャレンジゲーム |
ユーザー |
👑 |
提出日時 | 2024-09-14 17:29:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 647 ms / 2,000 ms |
コード長 | 1,887 bytes |
コンパイル時間 | 828 ms |
コンパイル使用メモリ | 82,632 KB |
実行使用メモリ | 84,236 KB |
最終ジャッジ日時 | 2024-09-14 17:29:51 |
合計ジャッジ時間 | 22,494 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
n = int(input())A = list(map(int, input().split()))memo = [{} for _ in range(1 << n)]def dfs(bit, total, t):if bit == 0:if total > 0:return 1else:return 0if 2 * total + t in memo[bit]:return memo[bit][2 * total + t]inds = [i for i in range(n) if (bit >> i) & 1]ii = -1ret = -1for i in inds:mi = 1.0for j in inds:p1 = 1 / A[i]p2 = (1 - 1 / A[i]) / A[j]p = p1 + p2p1 /= pp2 /= ptmp = 0tmp += dfs(bit ^ (1 << i), total + A[i], 1) * p1tmp += dfs(bit ^ (1 << j), total - A[j], 0) * p2mi = min(mi, tmp)if mi > ret:ii = iret = mijj = -1ret = 2for j in inds:ma = 0.0for i in inds:p2 = 1 / A[j]p1 = (1 - 1 / A[j]) / A[i]p = p1 + p2p1 /= pp2 /= ptmp = 0tmp += dfs(bit ^ (1 << i), total + A[i], 1) * p1tmp += dfs(bit ^ (1 << j), total - A[j], 0) * p2ma = max(ma, tmp)if ma < ret:jj = jret = mai = iij = jjif t == 0:p1 = 1 / A[i]p2 = (1 - 1 / A[i]) / A[j]p = p1 + p2p1 /= pp2 /= ptmp = 0tmp += dfs(bit ^ (1 << i), total + A[i], 1) * p1tmp += dfs(bit ^ (1 << j), total - A[j], 0) * p2ret = tmpelse:p2 = 1 / A[j]p1 = (1 - 1 / A[j]) / A[i]p = p1 + p2p1 /= pp2 /= ptmp = 0tmp += dfs(bit ^ (1 << i), total + A[i], 1) * p1tmp += dfs(bit ^ (1 << j), total - A[j], 0) * p2ret = tmpmemo[bit][2 * total + t] = retreturn retans = dfs((1 << n) - 1, 0, 0)print(ans)