ABC 127 D-Integer Card　緑コーダーですが何か？その１

緑のしいだよ。

緑コーダーですが何か？第一回目だよ。

ここでは緑コーダーならとけるはずの問題を自責も兼ねて定期的にといていくよ。

記念すべき１回目はこれ！

ABC 127 D-Integer Card

https://atcoder.jp/contests/abc127/tasks/abc127_d

ぱっとみ、M回操作して最大値を求めればいいんだね。

選ぶ枚数は０枚でもいいってなんか変な感じするけど、操作しなくていいということか

解法1

リストに2*Nのサイズになるまで（B,C）を入れてあげる。そしてリスト[:N]でソートする。

C = 10**9と書いてあるが、最終的にNの数は決まっておりCの数全部使う必要もないからである。たとえばBがAの最大値より大きく場合でもN個いれてやったらAの元の要素がすべて吐き出されるので安心である。

実装

    N,M=map(int,input().split())
    A = list(map(int,input().split()))
    l = [] 
    for i in range(M):
      tmp = list(map(int,input().split()))
      l.append([tmp[1],tmp[0]])
    l.sort(reverse=True)
    for i,j in l:
        A.extend([i]*j)
        if len(A)>2*N:break
    A.sort(reverse=True)
    print(sum(A[:N]))

解法2

リストの中で最小値のものとBの値を比較してBのほうが大きかったら最小値と入れ替える。

実装におけるポイントは

リストの中の最小値を取り出す方法
Cが１以上の対処
はheapqを使えばなんとかなりそう
はwhile でCをすべて使い切るか、リストの中の最小値のほうが大きくなったときにwhileからぬけたらいいね

ここでwhileとかでると思考一瞬止まるからつらい。。。。

実装

    import heapq
    N,M=map(int,input().split())
    A = list(map(int,input().split()))
    heapq.heapify(A)
    l = [] 
    for i in range(M):
      tmp = list(map(int,input().split()))
      l.append([tmp[1],tmp[0]])
    l.sort(reverse=True)
    
    for i,j in l:
      for I in range(j):
        Q = heapq.heappop(A)
        if Q<i :
          heapq.heappush(A,i)
        else:
          heapq.heappush(A,Q)
          break
    print(sum(A))

あとがき

実装１の考え方はかなり大事だから意識しとくべき実装も簡単だし実装２も重そうに見えるけどN回出し入れするだけなので速度は大丈夫heapqの使い方も見直さないとね

ちなみにこのコンテスト参加してたんだけどすごい実装汚いの成長見てくれるって人は見てね（笑）↓

https://atcoder.jp/contests/abc127/submissions/5608902