DPまとめコンテスト/U - Grouping - 競技プログラミング用 知識集積所【7/26更新】

---

問題

DP-U

必要知識

ABCのB以下レベルの内容は省略

• bitDP（未作成）
  • 動的計画法
  • bit全探索（未作成）

考え方

いわゆるbitDP（未作成）。
グループ分けの状態をbit全探索（未作成）の要領で調べていく過程で動的計画法を用いる。

採用するうさぎ一覧をbitで管理し、それらの

• 全うさぎを同じグループに入れる場合の得点
• 複数グループに分ける場合の最大得点

をDPで求めていく。
前者は、ある1体以外の場合の得点をベースに、その1体を追加したときの得点変化をaを見て求める。
後者は、ある1体に加え何体かを同じグループに入れる得点+残りを複数グループに分ける最大得点、の最大値で求める。

これで理論上は求まるが、問題は計算量。
愚直にやると2^n通りのDPテーブルそれぞれの枠で後者の計算に2^nかけると、4^n回のループになる。
n=16の場合には、約43億通りになってギリギリTLE。
そこで、定数倍の高速化を考える。

「ある1体」として番号が最大であるうさぎiを選ぶことにすると、
残りのメンバーの選び方jのループは1<<(i-1)までの2^(i-1)通りでよい。
さらに、そのうさぎと同じグループに入れるものを選ぶのに、k<jまでで打ち切ってよい。
そうすると、後者を求めるループ回数がほぼ(4^n)/6回になって、約7億通り。
kの選び方が不適切であることを超高速で判定できれば、C++ならギリギリ間に合う。

解答例

解答例

注意点

別解

O(3^n)でどうにかする方法

kの選び方が不適切であることを超高速で判定するのではなく、そもそもうまく値を飛ばしながらO(3^n)でうまく判定することができる。
kがjの部分集合でなかった場合、kに含まれてjに含まれない最上位bitより下を全て1に埋めた数までは、kがjの部分集合になることはない。
そのため、kの値をワープさせることでループ数を減らすことができる。

「kに含まれてjに含まれない最上位bitより下」とは言ったが、毎回このチェックをしている限り、そのようなbitが2つ以上ある数は全てスキップされる。
よって、bit演算（未作成）により(k&~j)の最下位bitを抽出することで簡素に実装できる。
解答例