結果
問題 | No.174 カードゲーム(Hard) |
ユーザー | shotoyoo |
提出日時 | 2021-07-03 21:56:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 842 ms / 2,000 ms |
コード長 | 1,257 bytes |
コンパイル時間 | 1,299 ms |
コンパイル使用メモリ | 87,184 KB |
実行使用メモリ | 110,012 KB |
最終ジャッジ日時 | 2023-09-13 03:48:46 |
合計ジャッジ時間 | 8,236 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,392 KB |
testcase_01 | AC | 75 ms
71,372 KB |
testcase_02 | AC | 832 ms
109,944 KB |
testcase_03 | AC | 820 ms
109,976 KB |
testcase_04 | AC | 822 ms
109,880 KB |
testcase_05 | AC | 842 ms
109,764 KB |
testcase_06 | AC | 833 ms
109,916 KB |
testcase_07 | AC | 840 ms
110,012 KB |
testcase_08 | AC | 824 ms
109,860 KB |
testcase_09 | AC | 819 ms
109,760 KB |
testcase_10 | AC | 74 ms
71,512 KB |
testcase_11 | AC | 74 ms
71,372 KB |
ソースコード
import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(2*10**5+10) write = lambda x: sys.stdout.write(x+"\n") debug = lambda x: sys.stderr.write(x+"\n") writef = lambda x: print("{:.12f}".format(x)) n,pa,pb = input().split() n = int(n) pa = float(pa) pb = float(pb) A = list(map(int, input().split())) B = list(map(int, input().split())) A.sort() B.sort() proba = [0]*(1<<n) probb = [0]*(1<<n) proba[0] = 1 probb[0] = 1 va = [[0]*n for _ in range(n)] vb = [[0]*n for _ in range(n)] for b in range((1<<n)-1): l = [] for i in range(n): if b>>i&1==0: l.append(i) used = n - len(l) if len(l)==1: psa = [1] psb = [1] else: psa = [pa] + [(1-pa)/(len(l)-1)] * (len(l)-1) psb = [pb] + [(1-pb)/(len(l)-1)] * (len(l)-1) for ind,i in enumerate(l): vva = psa[ind]*proba[b] vvb = psb[ind]*probb[b] proba[b|(1<<i)] += vva probb[b|(1<<i)] += vvb va[used][i] += vva vb[used][i] += vvb ans = 0 for i in range(n): for j in range(n): aa = A[j] pa = va[i][j] for k in range(n): pb = vb[i][k] bb = B[k] if aa>bb: ans += (aa+bb) * pa*pb print(ans)