結果

問題 No.1151 チャレンジゲーム
ユーザー mkawa2
提出日時 2021-06-10 16:22:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 547 ms / 2,000 ms
コード長 2,906 bytes
コンパイル時間 418 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 90,880 KB
最終ジャッジ日時 2024-11-30 01:48:55
合計ジャッジ時間 19,429 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

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