結果

問題 No.1151 チャレンジゲーム
コンテスト
ユーザー iastm
提出日時 2026-05-12 00:20:50
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,059 ms / 2,000 ms
コード長 1,624 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 229 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 91,364 KB
最終ジャッジ日時 2026-05-12 00:21:32
合計ジャッジ時間 32,199 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N = int(input())
A = [int(x) for x in input().split()]

def encode(scoreboard):
    return sum(scoreboard[i] * 3 ** i for i in range(N))
def modified(scoreboard, index, player):
    result = scoreboard[:]
    result[index] = player
    return result
def decode(id):
    result = [0] * N
    for i in range(N):
        result[i] = id % 3
        id //= 3
    return result

dp = [[-1] * (3 ** N), [1] * (3 ** N)]
for k in range(3 ** N - 1, -1, -1):
    scoreboard = decode(k)
    options = [i for i in range(N) if scoreboard[i] == 0]
    if not options:
        result = sum(A[i] if scoreboard[i] == 1 else -A[i] for i in range(N))
        if result > 0:
            dp[0][k] = dp[1][k] = 1
        else:
            dp[0][k] = dp[1][k] = 0
        continue

    dp[0][k] = 0
    for i in options:
        worst = 1
        p = 1 / A[i]
        pr_success = p * dp[1][encode(modified(scoreboard, i, 1))]
        for j in options:
            q = 1 / A[j]
            pr_opponent_success = (1 - p) * q * dp[0][encode(modified(scoreboard, j, 2))]
            worst = min(worst, (pr_success + pr_opponent_success) / (1 - (1 - p) * (1 - q)))
        dp[0][k] = max(dp[0][k], worst)

    dp[1][k] = 1
    for i in options:
        worst = 0
        p = 1 / A[i]
        pr_success = p * dp[0][encode(modified(scoreboard, i, 2))]
        for j in options:
            q = 1 / A[j]
            pr_opponent_success = (1 - p) * q * dp[1][encode(modified(scoreboard, j, 1))]
            worst = max(worst, (pr_success + pr_opponent_success) / (1 - (1 - p) * (1 - q)))
        dp[1][k] = min(dp[1][k], worst)

print(f"{dp[0][0]:.10f}")
0