python勉強一週間目

学生のころから軽ーくプログラミングで創作をしていたのである程度は初めての言語も吸収していけると思っておりますが（気のせい）

アプリとかシェルとかで満足してた理想の低い人間だったのでアルゴリズムとか処理速度とかそういうのにあまり気を使ったことはなかったわけで......

そういう弱みに綺麗にストレートを叩き込まれたのがこの問題
Atcoder Contest 141 D問題

N個の値段のバラバラの商品があってそれをM枚の5割引券を使って最安値で全部買おうぜっていう問題。値引きじゃなくて割引券なのでやはり高い商品に使う方がお得。

なのでプログラム的には「Aのリストの最大値を選んで2で割る」をM回繰り返せばいい。てな感じで愚直に書いたのがこちら(端々の拙さをお許しあれ)

余裕やんと思って提出したらたくさんのTLE(実行時間制限超過)の文字。

初めはもう完全にpythonのせいだと思い、処理をnumpyにさせたりといろいろしたけど変わらず(本番じゃなくてよかった)
これは絶対処理の方法が悪いんだと思って色々調べてたどり着いたのが

優先度付きキューですた。

もちろんキューは知ってた。先入れ先出し。
はじめにストローに吸い込まれたタピオカは最初に口に入る。
優先度付きキューは聞いたことがなかった。
これはキューの値に何らかの優先度をつけてそれに従って要素を入れたり、取り出すことができるアルゴリズムだそう。一口に優先度付きキューといってもいろんなアルゴリズムがあるみたい。
値であれば大小や、特定の値との比較によって優先度付けされる。
しかもこのアルゴリズム結構高速だそう、、、
すくなくとも上で自分が書いた愚コードよりははるかに早く、、、

これを使えば、新たに値をぶち込もうが削除しようが変更しようが常に最初に最大値or最小値を取り出してくれる最高の機能を実現できる!
今回はそのような神アルゴリズムの中からヒープを用いた優先度付きキューのpythonライブラリーheapqを用いて実装した。

最初のループで価格をすべてぶち込む!
ここで大事なのはheapqアルゴリズムはデフォだと最小値を取り出すようになっているため負数に変換してぶち込む!
そして次のループでは先ほどの神機能を使い、最大値を取り出して2で割ってまたぶち込む!　という動作を割引券の枚数分行う
なお問題で小数は切り捨てと書かれていたので端々で切り捨てる
最後にすべての要素を足して完成、、、

優先度付きキュー......おみごと!!

こーゆー処理速度とかアルゴリズムは自分の趣味の範囲でアプリ作ったりしてるだけじゃなかなか考えたりしないのでそれに気づけただけでもAtCoderやった甲斐があるなあとしみじみ。

最後に,,,Noteってどうやって色付きでコード書けるん,,,,,,