2015-01-02から1日間の記事一覧
N 個の数値のうち、好きなだけ選んで合計を X にできるパターンの個数を求めるという問題で、 N が小さい値ならばそのまま全探索(O(2^N))すれば良いんですが、 N が 32 だと時間切れになります。解説を読むと、N 個の数値を半分に分割し、片方の合計を p, も…
bit DP どころか DP すら碌に書いたことが無いレベルだが、 ARC016 の C 問題で bit DP を使うことになるようなので練習しました。学んだことを記しておきます。 bit DP とは 例えば TSP (巡回セールスマン問題)で、拠点 ABCD を回ることを考える場合、既…