AOJ 2631 - Clique Coloring
解法
それぞれの頂点について、回目に選ばれたか選ばれてないか、について考えると、パターンあります。
これらをビットで表すと、だけ、全体から1つ頂点を減らすことができます。
また、回目と回目に同時に選ばれる頂点が2つ以上あることはありません。
つまり、2つ以上ビットが立っているパターンについては、そのような頂点があるか、ないかの2択になります。
2つ以上ビットが立っているパターンは、通り(1つもビットが立ってないのが1通り、1つのみビットが立っているのが通り)ありますが、この値をとして、通りのパターンについて枝刈り全探索をすればよいです。
が同時に立っているビットを既に選択したかどうか、次にどのパターンを選択するか、そして現在いくつの頂点を削減できたか、の情報を引数にもち、再帰でDFSをしました。
今見ているパターンを選択する場合は、引数にあるが同時に立っているビットの情報を更新(矛盾すればその場で打ち切り)、それぞれの立っているビットについて選ばれた回数を計算(を超えることはできません)し、再帰をします。
感想
数週間考えました…
このタイプは苦手です。