けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2013-12-01から1ヶ月間の記事一覧

O(2^n)から計算量を減らす問題

この記事は、Competitive Programming Advent Calendar Div2013の22日目の記事として書きました。今年は「ナイーブにやるとO(2^n)になりそうな問題の計算量を落とす系の問題」を集めました。例えば、区間スケジューリング問題は、ナイーブに全探索しようと思…