【Atcoder】ABC 127 D問題

コンテスト名

AtCoder Beginner Contest 127

考えたこと

わからん。
とりあえず図を描いてみよう。

最初に5,1,4のカードがあって、3のカード2枚、5のカード1枚と交換できるわけね。

カードの合計を最大にする訳だから、まずは1を捨てて3を仲間に入れよう。

そうしたら3が1番小さいから5と交換して

...ん？

これって
[5,1,4,3,3,5]の配列から大きい順にN個抜き出せばいいだけじゃね？？？

import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
heapq.heapify(a)
l=[]

for i in range(m):
    b,c=map(int,input().split())
    l.append([b,c])
for i in range(m):
    a.extend(l[i][0]*[l[i][1]])
heapq.heapify(a)
for i in range(len(a)-n):
    heapq.heappop(a)
print(sum(a))

これで完璧！！

....と思ったが

あれ。。。？
TLEだと。。。

とりあえず調べる

for i in range(len(a)-n):
    heapq.heappop(a)

len(a)-n、すなわち追加要素の数を$B$とすると
for文で$O(B)$heappopで$O(log n)$(※1)なのでここだけで
計算量$O(Blog n)$かかる。

問題文を見ると
$1≤M≤10^5$
$1≤Bi≤N$
と書いてあるので$B$はとんでもなく大きい数字になる

ランレングス圧縮

どうやら色々調べてみたところランレングレス圧縮(※2)とやらを使うらしい

例えば「AAAABBCC」という文字列があったとして
Aが4個、Bが2個,Cが2個なので「A4B2C2」と表す圧縮方法らしい

これを応用しよう！

けんちょん様のブログを参考にさせていただきました。(※3)
先ほどは

l.append([b,c])

としていましたが色々調べたところ、どうやらタプルを使って

l.append((c,b))

とすることでcがb回連続していることを表現できるらしい。

タプルって何？配列と何が違うの？

「同じ型のものを集める場合にはリスト、違う型のもの同士を集める場合にはタプル(※4)」
らしい。
なるほど、それならランレングス圧縮にぴったりな訳か。

n,m=map(int,input().split())
a=list(map(int,input().split()))

l=[]
for i in range(n):
    l.append((a[i],1))
for i in range(m):
    b,c=map(int,input().split())
    l.append((c,b))
l.sort(reverse=True)

number_tmp=0
answer=0
for value,number in l:
    if number_tmp+number<=n:
        number_tmp+=number
        answer+=value*number
    else:
        answer+=value*(n-number_tmp)
        break
print(answer)

参考

※1 https://qiita.com/uniTM/items/9630ed9d51f62b3e35ab
※2 https://qiita.com/wihan23/items/bbdb45e7e90ba27b9b02
※3 https://drken1215.hatenablog.com/entry/2019/06/15/021000
※4 https://qiita.com/keishi04hrikzira/items/167fbfdde101029c08da