Submission #3011790

---

Source Code Expand

N, pq = input().split()
N = int(N)
p, q = map(int, pq.split('/'))

P = p / q
PError = (q - p) / q

Ass = []
for i in range(N):
    Ass.append(list(map(int, input().split())))

# numVs[i]: (v, -j): 本戦順位が(i+1)位の人は、本戦でv勝、予選で(j+1)位 
numVs = [(sum(Ass[i]), -i) for i in range(N)]
numVs.sort(reverse=True)

# prob[v][j]: 実際にはv勝した人がj勝と記録される確率
prob = {}
for v in range(numVs[-1][0], numVs[0][0] + 1):
    # dp[i][j]: i試合目まで行ったとき、j勝と記録される確率
    dp = [0] * N
    dp[v] = 1

    # 前半のv試合は、実際には勝利とする
    for i in range(0, v):
        for j in range(N):
            if dp[j] == 0: continue
            # 確率(1-P)で誤記録→勝利が敗北になる
            dp[j - 1] += dp[j] * PError
            # 確率Pで正しく記録
            dp[j] *= P

    # 後半の(N-1-v)試合は、実際には敗北とする
    for i in range(v, N - 1):
        for j in reversed(range(N)):
            if dp[j] == 0: continue
            # 確率(1-P)で誤記録→敗北が勝利になる
            dp[j + 1] += dp[j] * PError
            # 確率Pで正しく記録
            dp[j] *= P

    prob[v] = dp


# dp[i][j]: 本戦順位が(i+1)位の人が、j勝と記録される確率（順位を変えない範囲で）
dp = [[0] * N for i in range(N)]
dp[0] = prob[numVs[0][0]]
for i in range(1, N):
    accP = 0
    if numVs[i][0] == numVs[i - 1][0] or -numVs[i][1] > -numVs[i - 1][1]:
        # 本戦順位が1つ上の人に対して、本戦での勝利数が同じ、
        # または、予選順位が下ならば、記録上同じ勝利数でも順位は変わらない
        for j in reversed(range(N)):
            accP += dp[i - 1][j]
            dp[i][j] = accP * prob[numVs[i][0]][j]
    else:
        # それ以外は、勝利数が少ない場合のみ順位を保てる
        for j in reversed(range(N)):
            dp[i][j] = accP * prob[numVs[i][0]][j]
            accP += dp[i - 1][j]

print(sum(dp[N - 1]))

Submission Info

Judge Result