結果

問題 No.1151 チャレンジゲーム
ユーザー 👑 rin204
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

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