結果

問題 No.1151 チャレンジゲーム
ユーザー mkawa2mkawa2
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
51,968 KB
testcase_01 AC 42 ms
52,864 KB
testcase_02 AC 53 ms
61,184 KB
testcase_03 AC 40 ms
51,840 KB
testcase_04 AC 40 ms
51,968 KB
testcase_05 AC 39 ms
52,096 KB
testcase_06 AC 40 ms
51,840 KB
testcase_07 AC 40 ms
52,352 KB
testcase_08 AC 40 ms
51,968 KB
testcase_09 AC 43 ms
52,608 KB
testcase_10 AC 42 ms
52,480 KB
testcase_11 AC 54 ms
61,312 KB
testcase_12 AC 54 ms
60,928 KB
testcase_13 AC 240 ms
79,488 KB
testcase_14 AC 237 ms
80,128 KB
testcase_15 AC 238 ms
79,488 KB
testcase_16 AC 253 ms
79,872 KB
testcase_17 AC 240 ms
79,360 KB
testcase_18 AC 239 ms
79,872 KB
testcase_19 AC 248 ms
80,000 KB
testcase_20 AC 242 ms
79,872 KB
testcase_21 AC 243 ms
79,488 KB
testcase_22 AC 242 ms
79,360 KB
testcase_23 AC 244 ms
79,744 KB
testcase_24 AC 246 ms
79,488 KB
testcase_25 AC 252 ms
80,512 KB
testcase_26 AC 242 ms
79,616 KB
testcase_27 AC 243 ms
80,000 KB
testcase_28 AC 542 ms
88,576 KB
testcase_29 AC 521 ms
89,472 KB
testcase_30 AC 531 ms
88,576 KB
testcase_31 AC 530 ms
89,472 KB
testcase_32 AC 529 ms
88,960 KB
testcase_33 AC 531 ms
90,240 KB
testcase_34 AC 531 ms
89,472 KB
testcase_35 AC 524 ms
89,472 KB
testcase_36 AC 531 ms
89,728 KB
testcase_37 AC 533 ms
88,704 KB
testcase_38 AC 525 ms
90,880 KB
testcase_39 AC 518 ms
89,344 KB
testcase_40 AC 526 ms
89,344 KB
testcase_41 AC 536 ms
89,344 KB
testcase_42 AC 547 ms
88,832 KB
testcase_43 AC 527 ms
89,728 KB
testcase_44 AC 527 ms
90,240 KB
testcase_45 AC 544 ms
90,624 KB
testcase_46 AC 537 ms
89,984 KB
testcase_47 AC 535 ms
88,704 KB
testcase_48 AC 485 ms
88,832 KB
testcase_49 AC 511 ms
88,960 KB
testcase_50 AC 535 ms
89,216 KB
testcase_51 AC 529 ms
89,088 KB
testcase_52 AC 543 ms
90,880 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