Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、5問目を解説していきたいと思います。
問題名 【D – Powerful Discount Tickets】
入力
N : 商品の数
M : 割引券の枚数
a[i] : i番目の商品の値段
考察
割引券の枚数分だけ、任意の商品の値段を半額にすることができます。なのでM回の試行のうち、その都度値段が最大の商品を半額にすれば答えが出ます(貪欲法)
しかし、リストから最大値を取る作業は、最大でO(N)の計算量がかかるため、M回その作業をしてしまうと計算量が間に合いません。 O(M*N) > 10の7乗
ではどうするか？
事前にソートしておきましょう。
そうすればリストの末尾が最大値となるため、一回の試行につき、indexを指定すればO(1)でデータを取ってこれます。
その後、半額した値を戻すのですが、せっかくソートされているので、リストに戻す際も、ソート順になるように戻したいです。（そうしないと、毎回ソートすることになり、TLE）
なので、整列された数列に対し、その列を崩さず、値を挿入することができる bisect_insertを使います。
これで、全体の計算量がO(M*log(N))となり、間に合います
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import bisect
N,M = MI()
A = LI()
"""
sortしてから、一番大きいのをpop,bisectで挿入をくりかえす
"""
A.sort()
for i in range(M):
tmp = A.pop()
new_tmp = tmp//2
bisect.insort(A,new_tmp)
# print(A)
# print(A)
print(sum(A))
もっと考える
上記の方法でもACにはなるのですが、実はもっと早く実行できる方法があります。それは、優先度付きキューを使用することです。
優先度付きキューとは、ある数列において、従来のリストよりも計算量を抑えながら、数列の最小値のpop,新しい値のpushができる構造を持つ配列です。(詳しくは、pythonライブラリのheapのところに書いてあると思います)
なので、今回はそれを利用して、問題を解きます！優先度付きキューはライブラリもあるのですが、僕は、うにだよ様が以前解説の際に使用していた優先度付きキューを使用させていただいてます。
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import bisect
N,M = MI()
A = LI()
"""
貪欲法
現段階での最大値を求める
→priority queueを使う
"""
class PriorityQueue:
def __init__(self, a=None):
import heapq
self.heapq = heapq
self.__container = []
if a:
self.__container = a[:]
self.heapq.heapify(self.__container)
@property
def is_empty(self):
return not self.__container
def pop(self):
#最小値を取り出す
return self.heapq.heappop(self.__container)
def push(self, x):
#xをheapにpush
self.heapq.heappush(self.__container, x)
def sum(self):
#合計値を出力
return sum(self.__container)
def __len__(self):
return len(self.__container)
def __str__(self):
return str(sorted(self.__container))
def __repr__(self):
return self.__str__()
B = []
for i in range(N):
B.append(A[i]*-1)
#優先度付きキューは最小値をpopするので、正負を入れ替えている
PQ = PriorityQueue(B)
for m in range(M):
a = PQ.pop()
x = (a*-1)//2
#取り出した値は正負を入れ替得られているので、元に戻し、//2する
PQ.push(x*-1)
#再度、-1をかけてpush
print(PQ.sum()*-1)まとめ
今後、計算量がシビアな問題が多発すると思うので、今のうちから計算量を落とすテクニックや解法を覚えておきましょう！
コメント