結果

問題 No.1151 チャレンジゲーム
ユーザー mkawa2mkawa2
提出日時 2021-06-10 16:22:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 556 ms / 2,000 ms
コード長 2,906 bytes
コンパイル時間 507 ms
コンパイル使用メモリ 87,052 KB
実行使用メモリ 91,676 KB
最終ジャッジ日時 2023-08-20 02:30:12
合計ジャッジ時間 20,707 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
71,284 KB
testcase_01 AC 66 ms
71,316 KB
testcase_02 AC 75 ms
76,052 KB
testcase_03 AC 63 ms
71,532 KB
testcase_04 AC 65 ms
71,384 KB
testcase_05 AC 64 ms
71,352 KB
testcase_06 AC 65 ms
71,476 KB
testcase_07 AC 65 ms
71,212 KB
testcase_08 AC 65 ms
71,588 KB
testcase_09 AC 66 ms
71,316 KB
testcase_10 AC 69 ms
71,280 KB
testcase_11 AC 73 ms
76,004 KB
testcase_12 AC 77 ms
75,992 KB
testcase_13 AC 241 ms
81,300 KB
testcase_14 AC 233 ms
80,920 KB
testcase_15 AC 232 ms
81,084 KB
testcase_16 AC 257 ms
81,560 KB
testcase_17 AC 232 ms
80,908 KB
testcase_18 AC 240 ms
81,568 KB
testcase_19 AC 245 ms
81,192 KB
testcase_20 AC 242 ms
81,424 KB
testcase_21 AC 241 ms
81,144 KB
testcase_22 AC 260 ms
81,012 KB
testcase_23 AC 249 ms
81,552 KB
testcase_24 AC 243 ms
81,060 KB
testcase_25 AC 241 ms
81,768 KB
testcase_26 AC 233 ms
81,180 KB
testcase_27 AC 230 ms
81,480 KB
testcase_28 AC 527 ms
91,628 KB
testcase_29 AC 499 ms
90,072 KB
testcase_30 AC 507 ms
91,232 KB
testcase_31 AC 515 ms
91,312 KB
testcase_32 AC 520 ms
91,296 KB
testcase_33 AC 503 ms
90,844 KB
testcase_34 AC 503 ms
91,012 KB
testcase_35 AC 513 ms
91,100 KB
testcase_36 AC 526 ms
91,312 KB
testcase_37 AC 510 ms
91,140 KB
testcase_38 AC 509 ms
91,060 KB
testcase_39 AC 509 ms
90,984 KB
testcase_40 AC 515 ms
90,952 KB
testcase_41 AC 535 ms
90,252 KB
testcase_42 AC 556 ms
91,200 KB
testcase_43 AC 498 ms
89,764 KB
testcase_44 AC 499 ms
90,292 KB
testcase_45 AC 509 ms
90,212 KB
testcase_46 AC 523 ms
91,380 KB
testcase_47 AC 509 ms
91,112 KB
testcase_48 AC 460 ms
90,804 KB
testcase_49 AC 511 ms
90,236 KB
testcase_50 AC 505 ms
91,676 KB
testcase_51 AC 502 ms
90,904 KB
testcase_52 AC 535 ms
91,112 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