読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

AOJ 2631 Clique Coloring

AOJ 2631でもClique Coloringでも解説がヒットしなかったので書いた。

概要

めっちゃ短いので読んでください(三行。
Clique Coloring | Aizu Online Judge

解法

なんか頑張って場合分けすれば解けそうだけど難しすぎる。
2^n個の集合を考えるとそれぞれにその操作で選んだかどうかを割り当てることができる。
同じ色で塗られた辺がないということは、
操作の任意のペアi,jに対して、iにもjにも属している頂点はたかだか1つになるということだとわかる。
つまり、頂点数が2以上の部分集合に含まれている頂点はそれぞれ高々1つになるので、bitで管理できる。
また、それぞれの集合に対して含まれる操作の数-1つだけ必要な頂点数が減るのでmを求めることができる。
あとは遷移していって条件を満たしているかどうかを確かめればいい。
O((2^k)*n^2)くらい。(k:=要素数が2以上の部分集合の数)
状態数が多いのでsetに突っ込んで同じ状態は見ないようにする。
n<=5と小さいので2^(2^n)が整数型に収まりそうな感じがするのでそれで状態を持った。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int ans=0,sum=0;
int a[5];
set<int> si;
void dfs(int b){
  if(si.count(b)) return;
  si.insert(b);
  for(int i=0;i<n;i++){
    int tmp=0;
    for(int j=0;j<(1LL<<n);j++){
      if(((j>>i)&1LL)&&((b>>j)&1LL)) tmp++;
    }
    if(tmp>a[i]) return;
    for(int j=i+1LL;j<n;j++){
      tmp=0;
      for(int k=0;k<(1LL<<n);k++){
	if(((k>>i)&1LL)&&((k>>j)&1LL)&&((b>>k)&1LL)) tmp++;
      }
      if(tmp>1LL) return;
    }
  }
  int tmp=0;
  for(int i=0;i<(1LL<<n);i++){
    if((b>>i)&1) tmp+=__builtin_popcountll(i)-1LL;
  }
  ans=min(ans,sum-tmp);
  
  for(int i=0;i<(1LL<<n);i++){
    if((b>>i)&1) continue;
    if(__builtin_popcountll(i)<=1) continue;
    dfs(b+(1LL<<i));
  }
  
}
signed main(){
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) sum+=a[i];
  ans=sum;
  dfs(0);
  cout<<ans<<endl;
  return 0;
}
感想

ans=min(ans,sum-tmp);を ans=min(ans,sum-__builtin_popcountll(b));としていて無限にハマった。
これ想定なんだろうか(場合分けの方が結局楽な気がする)。
日本語難しすぎる。(よくわかんないことをノリと気合いで書いたのでア