結果

問題 No.2957 Combo Deck Builder
コンテスト
ユーザー navel_tos
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder2957 Combo Deck Builder

#入力受取・assert
N = int(input())
cards = [tuple(map(int, input().split())) for _ in range(N)]
assert 1 <= N <= 2 * 10 ** 5
for Ci, Xi, Yi in cards:
    assert 0 <= Ci <= N
    assert 1 <= Xi <= 10 ** 9 and 1 <= Yi <= 10 ** 9

#愚直解
from itertools import permutations
def brute(N, cards):
    ans = 0
    for u in range(N + 1):
        for S in permutations( range(N), r = u ):
            cnt = 0
            for d, i in enumerate(S):
                Ci, Xi, Yi = cards[i]
                cnt += Xi if Ci <= d else Yi
            ans = max(ans, cnt)
    return ans


#貪欲法
import heapq
def 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 = 0
        for Ci, Xi, Yi in A:
            ans += Xi
            if Ci == 0:  #Yiダメージは出せない → 無視
                continue
            E[ 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 ans

    return calc(A) + calc(B)
            

#実行
print( solve(N, cards) )


#ランダムテスト
def test( time = 10000 ):
    from random import randint
    for _ 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)
0