結果

問題 No.1151 チャレンジゲーム
ユーザー mkawa2mkawa2
提出日時 2021-06-10 16:22:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 526 ms / 2,000 ms
コード長 2,906 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 90,880 KB
最終ジャッジ日時 2024-05-07 10:04:41
合計ジャッジ時間 18,341 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,352 KB
testcase_01 AC 39 ms
52,992 KB
testcase_02 AC 50 ms
61,824 KB
testcase_03 AC 37 ms
51,840 KB
testcase_04 AC 37 ms
52,352 KB
testcase_05 AC 35 ms
52,480 KB
testcase_06 AC 37 ms
51,968 KB
testcase_07 AC 36 ms
53,120 KB
testcase_08 AC 40 ms
52,096 KB
testcase_09 AC 39 ms
52,864 KB
testcase_10 AC 39 ms
52,352 KB
testcase_11 AC 50 ms
61,824 KB
testcase_12 AC 50 ms
61,952 KB
testcase_13 AC 239 ms
79,932 KB
testcase_14 AC 234 ms
80,384 KB
testcase_15 AC 224 ms
79,744 KB
testcase_16 AC 239 ms
80,128 KB
testcase_17 AC 229 ms
80,008 KB
testcase_18 AC 216 ms
80,384 KB
testcase_19 AC 223 ms
80,256 KB
testcase_20 AC 215 ms
80,000 KB
testcase_21 AC 218 ms
79,836 KB
testcase_22 AC 224 ms
79,844 KB
testcase_23 AC 234 ms
80,000 KB
testcase_24 AC 226 ms
79,744 KB
testcase_25 AC 226 ms
80,144 KB
testcase_26 AC 219 ms
79,872 KB
testcase_27 AC 218 ms
80,384 KB
testcase_28 AC 526 ms
89,000 KB
testcase_29 AC 495 ms
89,444 KB
testcase_30 AC 491 ms
88,960 KB
testcase_31 AC 487 ms
89,644 KB
testcase_32 AC 489 ms
89,200 KB
testcase_33 AC 512 ms
90,496 KB
testcase_34 AC 499 ms
90,312 KB
testcase_35 AC 495 ms
89,728 KB
testcase_36 AC 508 ms
90,024 KB
testcase_37 AC 485 ms
89,472 KB
testcase_38 AC 483 ms
90,880 KB
testcase_39 AC 523 ms
89,216 KB
testcase_40 AC 490 ms
89,600 KB
testcase_41 AC 511 ms
89,392 KB
testcase_42 AC 498 ms
88,960 KB
testcase_43 AC 500 ms
89,712 KB
testcase_44 AC 486 ms
90,572 KB
testcase_45 AC 498 ms
90,676 KB
testcase_46 AC 486 ms
89,984 KB
testcase_47 AC 495 ms
88,960 KB
testcase_48 AC 469 ms
89,216 KB
testcase_49 AC 472 ms
89,636 KB
testcase_50 AC 487 ms
89,856 KB
testcase_51 AC 514 ms
89,620 KB
testcase_52 AC 499 ms
90,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

sys.setrecursionlimit(200005)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.buffer.readline())
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def LI1(): return list(map(int1, sys.stdin.buffer.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
def BI(): return sys.stdin.buffer.readline().rstrip()
def SI(): return sys.stdin.buffer.readline().rstrip().decode()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
# dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = 10**16
# md = 998244353
# md = 10**9+7

# from functools import lru_cache
#
# # nullさんの取ったカードがs、kiriさんの取ったカードがtのときに、nullさんの勝つ確率
# @lru_cache(None)
# def p(s, t):
#     used = s | t
#     # 全部取り終わった場合
#     if used == (1 << n)-1:
#         x = sum(a for i, a in enumerate(aa) if s >> i & 1)
#         y = tot-x
#         return x > y
#     res = 0
#     for i, ai in enumerate(aa):
#         if used >> i & 1: continue
#         s1 = s | 1 << i
#         p1 = 1
#         if popcnt(used) == n-1:
#             p1 = p(s | 1 << i, t)
#         else:
#             for j, aj in enumerate(aa):
#                 if j == i: continue
#                 if used >> j & 1: continue
#                 p1 = min(p1, p(s1, t | 1 << j)/aj+p(s1, t)*(aj-1)/aj)
#         cur = 1
#         for j, aj in enumerate(aa):
#             if used >> j & 1: continue
#             p2 = p(s, t | 1 << j)
#             cur = min(cur, (aj*p1-p2+ai*p2)/(ai+aj-1))
#         res = max(res, cur)
#     return res

popcnt = lambda x: bin(x).count("1")
n = II()
aa = LI()
tot = sum(aa)

dp = {}
over = (1 << n)-1
for used in range(over, -1, -1):
    s = used
    while 1:
        t = used ^ s
        if used == over:
            x = sum(a for i, a in enumerate(aa) if s >> i & 1)
            y = tot-x
            dp[s, t] = (x > y)*1
        else:
            val = 0
            for i, ai in enumerate(aa):
                if used >> i & 1: continue
                s1 = s | 1 << i
                p1 = 1
                if popcnt(used) == n-1:
                    p1 = dp[s | 1 << i, t]
                else:
                    for j, aj in enumerate(aa):
                        if j == i: continue
                        if used >> j & 1: continue
                        p1 = min(p1, dp[s1, t | 1 << j]/aj+dp[s1, t]*(aj-1)/aj)
                cur = 1
                for j, aj in enumerate(aa):
                    if used >> j & 1: continue
                    p2 = dp[s, t | 1 << j]
                    cur = min(cur, (aj*p1-p2+ai*p2)/(ai+aj-1))
                val = max(val, cur)
            dp[s, t] = val
        if s == 0: break
        s = (s-1) & used

print(dp[0, 0])
0