ポエム兼備忘録です。
悔しいので一気に書ききります。
これは問題
多分解くのは二段階
- 問題の読み替え(一番値段の高いものを取得してそれを半額って流れだと読む)
- 実装(私はここでおしまいになりました)
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のせいにしてしまうのが一番嫌だった。