結果
問題 | No.2957 Combo Deck Builder |
ユーザー |
![]() |
提出日時 | 2025-01-11 17:10:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 591 ms / 1,000 ms |
コード長 | 2,624 bytes |
コンパイル時間 | 2,045 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 145,492 KB |
最終ジャッジ日時 | 2025-01-11 17:11:21 |
合計ジャッジ時間 | 20,944 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#yukicoder2957 Combo Deck Builder#入力受取・assertN = int(input())cards = [tuple(map(int, input().split())) for _ in range(N)]assert 1 <= N <= 2 * 10 ** 5for Ci, Xi, Yi in cards:assert 0 <= Ci <= Nassert 1 <= Xi <= 10 ** 9 and 1 <= Yi <= 10 ** 9#愚直解from itertools import permutationsdef brute(N, cards):ans = 0for u in range(N + 1):for S in permutations( range(N), r = u ):cnt = 0for d, i in enumerate(S):Ci, Xi, Yi = cards[i]cnt += Xi if Ci <= d else Yians = max(ans, cnt)return ans#貪欲法import heapqdef solve(N, cards):#問題を読み替える#Ciターン未満ならYiダメージ Ciターン以降ならXiダメージを与える#カードを (Yiを優先したい / Xiを優先したい) の2つの束に分割するA, B = [], []for Ci, Xi, Yi in cards:if Xi < Yi:A.append((Ci, Xi, Yi))else:B.append((N - Ci, Yi, Xi))#カードの順序は A(Yi優先 左に置きたい) → B(Xi優先 右置き) と決め打って差し支えない#以降はA, B内の適切な並び順を決めればよいdef calc(A):#以下の部分問題を解け:#Ciターン未満ならYiダメージ、以降ならXiダメージ の条件配列Aを与える。#適切な割り振りを行ったときの最大ダメージを計算せよ。#貪欲法で解く: sum(Xi) + max( 条件を満たす Yi - Xi )として計算する。#Ci - 1ターン目にYi → Xi ターンの切り替えが行われるので、Yi - Xiをバケットソートn = len(A)E = [[] for _ in range(n)]ans = 0for Ci, Xi, Yi in A:ans += Xiif Ci == 0: #Yiダメージは出せない → 無視continueE[ min( n - 1, Ci - 1 ) ].append( Yi - Xi )#日付の降順に貪欲: 割り振れるなら、最大のYi - Xiを割り振るQ = []for d in range(n - 1, -1, -1):for x in E[d]:heapq.heappush(Q, - x) #maxheapなので正負反転するif Q:ans += - heapq.heappop(Q)return ansreturn calc(A) + calc(B)#実行print( solve(N, cards) )#ランダムテストdef test( time = 10000 ):from random import randintfor _ in range(time):n = randint(1, 6)c = [(randint(0, n), randint(1, 1000), randint(1, 1000)) for _ in range(n)]assert brute(n, c) == solve(n, c)