はてなブックマーク

今日の夜、会社の競プロイベント#2が開催された。バーチャルコンテスト形式で10人以上が参加してわいわいやった。途中参加だったけどめちゃくちゃ楽しかった。 問題の中で、愚直にやったらTLEするようなものがあった。計算量に気をつけないといけないやつ。 （この問題 => C - Factory） 結論から言うと、Priority Queue(優先度付きキュー)があればシュッと解けるんだけど、Rubyの組み込みライブラリにはなさそうだった。 Priority QueueはHeap(木構造が)あれば実装できるけど、それもなさそうな感じだったので書いてみた。 それがこちら。 https://gist.github.com/akht/3749fac291c527aeb043c40b12c4950a このブログでは展開されないので中身を貼っておくとこんな感じになってる。 class MinHeap def