結果
問題 | No.1590 Random Shopping |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-07-09 18:23:30 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 2,867 ms / 5,000 ms |
コード長 | 2,237 bytes |
コンパイル時間 | 447 ms |
コンパイル使用メモリ | 86,944 KB |
実行使用メモリ | 271,080 KB |
最終ジャッジ日時 | 2023-09-14 06:33:56 |
合計ジャッジ時間 | 19,317 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,116 KB |
testcase_01 | AC | 72 ms
71,112 KB |
testcase_02 | AC | 72 ms
71,040 KB |
testcase_03 | AC | 72 ms
71,280 KB |
testcase_04 | AC | 73 ms
71,140 KB |
testcase_05 | AC | 73 ms
71,384 KB |
testcase_06 | AC | 82 ms
76,208 KB |
testcase_07 | AC | 87 ms
76,224 KB |
testcase_08 | AC | 105 ms
76,632 KB |
testcase_09 | AC | 110 ms
77,604 KB |
testcase_10 | AC | 118 ms
77,612 KB |
testcase_11 | AC | 157 ms
77,912 KB |
testcase_12 | AC | 293 ms
82,780 KB |
testcase_13 | AC | 838 ms
124,412 KB |
testcase_14 | AC | 2,300 ms
270,580 KB |
testcase_15 | AC | 2,323 ms
267,712 KB |
testcase_16 | AC | 2,284 ms
270,000 KB |
testcase_17 | AC | 2,248 ms
267,992 KB |
testcase_18 | AC | 72 ms
71,072 KB |
testcase_19 | AC | 2,820 ms
271,080 KB |
testcase_20 | AC | 73 ms
71,052 KB |
testcase_21 | AC | 2,867 ms
267,496 KB |
testcase_22 | AC | 70 ms
71,092 KB |
testcase_23 | AC | 135 ms
81,380 KB |
testcase_24 | AC | 136 ms
81,640 KB |
testcase_25 | AC | 72 ms
70,940 KB |
testcase_26 | AC | 72 ms
71,248 KB |
testcase_27 | AC | 73 ms
71,092 KB |
ソースコード
""" https://yukicoder.me/problems/no/1590 分からなければさっさと見ちゃおうかな 寄与を考えるよね x人目がy番目の商品を買う確率 がわかればおk x,yのペアに関して求めたい ===================== 答えを見た 出来そうなdpから結果を導出する Borderごとに dp[Border][a][b] = a日目でBorder以下がb個残っている確率 とすると、 a日目の人の購入額の期待値は 1/2 * ( dp[B0][a][0] * B0 + dp[B1][a][0] * (B1-B0) + ... ) ただし、その日の商品 A[a] < B? p[i][j] = """ from sys import stdin N = int(stdin.readline()) A = list(map(int,stdin.readline().split())) R = list(map(int,stdin.readline().split())) s = set(A) s.add(0) B = list(s) B.sort() #print (B) dp = {} ans = 0 for j in range(len(B)-1): Border = B[j] ndp = [[0] * (N+1) for i in range(N+1)] ndp[0][0] = 1 for a in range(N): na = A[a] for b in range(N+1): if na <= Border: #追加して、取る場合 ndp[a+1][b] += ndp[a][b] / 2 #追加して、取らない場合 if b != N: ndp[a+1][b+1] += ndp[a][b] / 2 else: #追加はしない、取る場合 ndp[a+1][max(0,b-1)] += ndp[a][b]/2 #追加はしない、取らない場合 ndp[a+1][b] += ndp[a][b] / 2 #dp[Border] = ndp for a in range(1,N+1): na = A[a-1] nr = R[a-1] nsum = 0 p = 0 #人aが、B[j]より大きい奴を取る確率 if na <= B[j]: p = 0 else: p = ndp[a-1][0] / 2 #print (a,B[j],p) nsum += (B[j+1]-B[j]) * p ans += nsum * nr print (ans) #print (dp) """ ans = 0 for a in range(1,N+1): na = A[a-1] nr = R[a-1] nsum = 0 for j in range(len(B)-1): p = 0 #人aが、B[j]より大きい奴を取る確率 if na <= B[j]: p = 0 else: p = dp[B[j]][a-1][0] / 2 #print (a,B[j],p) nsum += (B[j+1]-B[j]) * p ans += nsum * nr #print (nsum * nr) print (ans) """