燻ったエンジニアのブログ

コンピューター科学を専攻し、絵と音楽を趣味とするエンジニアのブログです。

2015-01-02から1日間の記事一覧

ARC017 [C]無駄なものが嫌いな人

N 個の数値のうち、好きなだけ選んで合計を X にできるパターンの個数を求めるという問題で、 N が小さい値ならばそのまま全探索(O(2^N))すれば良いんですが、 N が 32 だと時間切れになります。解説を読むと、N 個の数値を半分に分割し、片方の合計を p, も…

bit DP で TSP を解いてみた。

bit DP どころか DP すら碌に書いたことが無いレベルだが、 ARC016 の C 問題で bit DP を使うことになるようなので練習しました。学んだことを記しておきます。 bit DP とは 例えば TSP (巡回セールスマン問題)で、拠点 ABCD を回ることを考える場合、既…