DP(特にbitDP)で思ったこと

AtCoderを解いていて手早く書くのって慣れだなぁって思って練習中。 もちろん体系的な理解も知識も足りない。

で調べていたら「bitDPはO(n!)だと大変だけどO(2^n)だと間に合う時に使えるアルゴリズムです」なる文を見かけた。 こりゃ誤解か誤記だなって思った。

簡単な問題を解いたりしてる中で感じたことをメモしておく。

• bitDPはbitを使ったDP
  • DPなので最適性の原理に従う問題に使える
  • 最適性の原理に従う問題は分割統治できる問題なので下を満たす
    • 綺麗に分割できる: 元のインスタンスがより小さいインスタンにに分割できインスタンスの関係をグラフと捉えた時にループがない
    • 統治できる: 分割されたインスタンスを統治する演算が分配則を満たす
  • bitは部分集合を表すのに便利

なので、bitDPは問題を部分集合を指標として部分問題に分割できて、それらの間にループがなければ使えるアルゴリズムです、が正しい。 部分集合の要素数は 2^n なのでそれを許容するような問題じゃないとコンテストには出てこないよ！ってことだ。順序が逆である。