結果
問題 | No.174 カードゲーム(Hard) |
ユーザー | maspy |
提出日時 | 2020-05-16 17:49:29 |
言語 | Python3 (3.11.6 + numpy 1.26.0 + scipy 1.11.3) |
結果 |
AC
|
実行時間 | 470 ms / 2,000 ms |
コード長 | 1,213 bytes |
コンパイル時間 | 129 ms |
コンパイル使用メモリ | 12,020 KB |
実行使用メモリ | 42,456 KB |
最終ジャッジ日時 | 2023-10-23 20:30:52 |
合計ジャッジ時間 | 7,394 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 458 ms
42,456 KB |
testcase_01 | AC | 454 ms
42,456 KB |
testcase_02 | AC | 464 ms
42,456 KB |
testcase_03 | AC | 466 ms
42,456 KB |
testcase_04 | AC | 465 ms
42,456 KB |
testcase_05 | AC | 466 ms
42,456 KB |
testcase_06 | AC | 460 ms
42,456 KB |
testcase_07 | AC | 464 ms
42,456 KB |
testcase_08 | AC | 470 ms
42,456 KB |
testcase_09 | AC | 467 ms
42,456 KB |
testcase_10 | AC | 462 ms
42,456 KB |
testcase_11 | AC | 467 ms
42,456 KB |
ソースコード
import sys import numpy as np read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines N, PA, PB = readline().split() N, PA, PB = int(N), float(PA), float(PB) A = sorted(map(int, readline().split())) B = sorted(map(int, readline().split())) def compute_prob(N, P): # dp[i,j,k] = 残り1+i枚時点で、カードjが手元にある。それは手元の中でk番目である。 dp = np.zeros((N, N, N)) for j in range(N): dp[N - 1, j, j] = 1.0 for i in range(N - 1, 0, -1): q = (1 - P) / i dp[i - 1] += q * dp[i] * np.arange(i, i - N, -1)[None, :] dp[i - 1, :, :-1] += dp[i, :, 1:] * (P + q * np.arange(N - 1))[None, :] # 提出確率に変更 for i in range(N): if i == 0: p, q = 1.0, 0.0 else: p, q = P, (1 - P) / i dp[i, :, 0] *= p dp[i, :, 1:] *= q return dp.sum(axis=2) prob_a = compute_prob(N, PA) prob_b = compute_prob(N, PB) answer = 0 for j in range(N): for k in range(N): x, y = A[j], B[k] if x <= y: continue p = np.sum(prob_a[:, j] * prob_b[:, k]) answer += p * (x + y) print(answer)