heapqとABC141D – Powerful Discount Ticketsと私

ポエム兼備忘録です。
悔しいので一気に書ききります。

これは問題

多分解くのは二段階

  1. 問題の読み替え(一番値段の高いものを取得してそれを半額って流れだと読む)
  2. 実装(私はここでおしまいになりました)

1は多分そんなに難しくない。問題は2

愚直実装(M,Nの二重forループとか?)だとO(MN)で間に合わない。ここはわかる。

じゃあいったんソートして、一番後ろの要素(一番値が大きい)をpop (O(1))してその要素を半分にしてbisectでぶち込めばO(MlogN)じゃん!!!

お手上げ

私は涙を流し、残り五分という短い時間を使いrocket leagueをするのだった・・・・

ABC終了後

それはそうとして解説を読んだらheapqらしい。どうやろ値の追加削除がO(logN)で最小値の取得がO(1)だとか

(えっでもそれ俺の実装と変わらなくない)

変わりました

array.Insert() がO(N)だからいくらインデックスの発見がO(logN)で挿入したら遅くなるという・・・
謝罪

ちゃんと書きました

poem

今までPythonで書いてた理由として、趣味のプログラムをPythonで書いてたのと、言語仕様を知るために活用して来たが正直もうPythonで書いてないのでC++に移行しちゃおうかなと思ってしまった

何が一番嫌って計算量の見積もりミスを(これはPythonだから遅いのでは無いのか・・・?)とPythonのせいにしてしまうのが一番嫌だった。