ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2631 - Clique Coloring

問題
提出コード

解法

それぞれの頂点について、i回目に選ばれたか選ばれてないか、について考えると、2^{n}パターンあります。
これらをビットで表すと、\sum (立っているビットの数-1)だけ、全体から1つ頂点を減らすことができます。
また、i回目とj回目に同時に選ばれる頂点が2つ以上あることはありません。
つまり、2つ以上ビットが立っているパターンについては、そのような頂点があるか、ないかの2択になります。
2つ以上ビットが立っているパターンは、2^{n} - n - 1通り(1つもビットが立ってないのが1通り、1つのみビットが立っているのがn通り)ありますが、この値をXとして、2^{X}通りのパターンについて枝刈り全探索をすればよいです。
i,jが同時に立っているビットを既に選択したかどうか、次にどのパターンを選択するか、そして現在いくつの頂点を削減できたか、の情報を引数にもち、再帰でDFSをしました。
今見ているパターンを選択する場合は、引数にあるi,jが同時に立っているビットの情報を更新(矛盾すればその場で打ち切り)、それぞれの立っているビットについて選ばれた回数を計算(a_{i}を超えることはできません)し、再帰をします。

感想

数週間考えました…
このタイプは苦手です。