結果

問題 No.1151 チャレンジゲーム
ユーザー 👑 rin204rin204
提出日時 2024-09-14 17:29:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 647 ms / 2,000 ms
コード長 1,887 bytes
コンパイル時間 828 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 84,236 KB
最終ジャッジ日時 2024-09-14 17:29:51
合計ジャッジ時間 22,494 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
51,968 KB
testcase_01 AC 45 ms
53,248 KB
testcase_02 AC 75 ms
70,016 KB
testcase_03 AC 39 ms
52,352 KB
testcase_04 AC 39 ms
52,352 KB
testcase_05 AC 39 ms
52,352 KB
testcase_06 AC 39 ms
52,340 KB
testcase_07 AC 40 ms
52,608 KB
testcase_08 AC 40 ms
52,736 KB
testcase_09 AC 44 ms
53,120 KB
testcase_10 AC 43 ms
53,616 KB
testcase_11 AC 66 ms
69,888 KB
testcase_12 AC 61 ms
68,224 KB
testcase_13 AC 366 ms
80,632 KB
testcase_14 AC 363 ms
79,760 KB
testcase_15 AC 339 ms
79,512 KB
testcase_16 AC 364 ms
80,148 KB
testcase_17 AC 390 ms
80,752 KB
testcase_18 AC 361 ms
80,020 KB
testcase_19 AC 360 ms
80,176 KB
testcase_20 AC 325 ms
79,508 KB
testcase_21 AC 340 ms
80,164 KB
testcase_22 AC 328 ms
79,636 KB
testcase_23 AC 339 ms
79,768 KB
testcase_24 AC 378 ms
80,392 KB
testcase_25 AC 342 ms
79,712 KB
testcase_26 AC 358 ms
80,920 KB
testcase_27 AC 377 ms
79,092 KB
testcase_28 AC 588 ms
83,756 KB
testcase_29 AC 568 ms
83,248 KB
testcase_30 AC 611 ms
83,404 KB
testcase_31 AC 521 ms
81,224 KB
testcase_32 AC 619 ms
83,076 KB
testcase_33 AC 605 ms
83,256 KB
testcase_34 AC 604 ms
83,080 KB
testcase_35 AC 591 ms
83,712 KB
testcase_36 AC 617 ms
83,720 KB
testcase_37 AC 598 ms
83,260 KB
testcase_38 AC 565 ms
81,740 KB
testcase_39 AC 525 ms
82,452 KB
testcase_40 AC 639 ms
84,048 KB
testcase_41 AC 509 ms
81,868 KB
testcase_42 AC 597 ms
83,348 KB
testcase_43 AC 526 ms
82,716 KB
testcase_44 AC 528 ms
82,220 KB
testcase_45 AC 595 ms
82,984 KB
testcase_46 AC 647 ms
84,236 KB
testcase_47 AC 563 ms
82,376 KB
testcase_48 AC 237 ms
78,504 KB
testcase_49 AC 263 ms
78,152 KB
testcase_50 AC 513 ms
81,976 KB
testcase_51 AC 603 ms
84,160 KB
testcase_52 AC 609 ms
84,228 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
A = list(map(int, input().split()))

memo = [{} for _ in range(1 << n)]


def dfs(bit, total, t):
    if bit == 0:
        if total > 0:
            return 1
        else:
            return 0

    if 2 * total + t in memo[bit]:
        return memo[bit][2 * total + t]

    inds = [i for i in range(n) if (bit >> i) & 1]

    ii = -1
    ret = -1
    for i in inds:
        mi = 1.0
        for j in inds:
            p1 = 1 / A[i]
            p2 = (1 - 1 / A[i]) / A[j]
            p = p1 + p2
            p1 /= p
            p2 /= p
            tmp = 0
            tmp += dfs(bit ^ (1 << i), total + A[i], 1) * p1
            tmp += dfs(bit ^ (1 << j), total - A[j], 0) * p2
            mi = min(mi, tmp)
        if mi > ret:
            ii = i
            ret = mi

    jj = -1
    ret = 2
    for j in inds:
        ma = 0.0
        for i in inds:
            p2 = 1 / A[j]
            p1 = (1 - 1 / A[j]) / A[i]
            p = p1 + p2
            p1 /= p
            p2 /= p
            tmp = 0
            tmp += dfs(bit ^ (1 << i), total + A[i], 1) * p1
            tmp += dfs(bit ^ (1 << j), total - A[j], 0) * p2
            ma = max(ma, tmp)
        if ma < ret:
            jj = j
            ret = ma

    i = ii
    j = jj
    if t == 0:
        p1 = 1 / A[i]
        p2 = (1 - 1 / A[i]) / A[j]
        p = p1 + p2
        p1 /= p
        p2 /= p
        tmp = 0
        tmp += dfs(bit ^ (1 << i), total + A[i], 1) * p1
        tmp += dfs(bit ^ (1 << j), total - A[j], 0) * p2
        ret = tmp
    else:
        p2 = 1 / A[j]
        p1 = (1 - 1 / A[j]) / A[i]
        p = p1 + p2
        p1 /= p
        p2 /= p
        tmp = 0
        tmp += dfs(bit ^ (1 << i), total + A[i], 1) * p1
        tmp += dfs(bit ^ (1 << j), total - A[j], 0) * p2
        ret = tmp

    memo[bit][2 * total + t] = ret
    return ret


ans = dfs((1 << n) - 1, 0, 0)
print(ans)
0