きろく

特筆すべき記録のまとめ

AtCoder Grand Contest 029:B - Powers of two

問題

beta.atcoder.jp

解法

まず,A を大きい順に見ていく.このとき,今見ている要素が一番大きいので,もしペアにすることが出来る要素があるならば,それは1つに定まる.ここで,あえてペアにしないことは得にならない(最終的な答えが -1 になるか変わらないか)ので,ここでペアにするのが最適.よって,数が大きい要素からペアを作っていくのが最適になる.std::map を TLE しないように気を付けて実装して O(NlogN).

*こちらを参考にさせて頂きました.

betrue12.hateblo.jp

解答

beta.atcoder.jp

コンテスト中に解けなかった.一瞬貪欲を疑ったが違うだろうと根拠なく却下してしまったのは反省.実装を std::map::count() を使わずにしていたため無限ループになってしまっていた.

f:id:babcs2035:20181216151632p:plain