TopCoder SRM 596 Div1 Medium BitwiseAnd

TopCoder 貪欲法 グラフ理論

問題

次の性質をもつ自然数の集合Sをcoolであるとする。

  • 全ての要素は0以上2^60未満
  • 任意の異なるa, b∈Sについて(a & b) > 0　（bitwiseのand）
  • 任意の異なるa, b, c∈Sについて(a & b & c) > 0


Sの部分集合subsetが与えられる。
サイズがNであって、subsetの要素を全て含み、coolであるような辞書順最小のSを求めよ。
なければ空のベクタを返せ。

制約条件

N≦50
subsetの要素数≦50
subsetの要素は2^60未満の自然数

方針

3つ以上の異なる要素の&が0でなくてはいけないので、
Sの要素のうち、i番目のbitが1であるものは高々2つしかない。（任意のiについて）


で、任意の異なる2つの要素が&であるので、これは次のようにグラフにして考えられる。
要素を頂点として、二つの&が正であるものを辺で結んだグラフで、
辺はその二頂点の要素の&の値とする。


このグラフの全ての辺において、立っているビットは互いに素である。
（&を取ったときに0になる）


条件よりこのグラフは完全グラフでなくてはならない。
辺に使えるラベルは60種類しかないので、Nは高々11までしかありえないことがわかる。


subsetに更に頂点を追加していき、完全グラフにする。
次に追加する頂点は最小のものにしてよい。（辞書順で最小になるし、Sが作れなくなってしまうことがない）


今までの頂点とつながる必要があるので、今での頂点がもつ、接続につかわれてないビットのうち最小のものをそれぞれ集めてくる。
これから追加する残りの頂点とつながる必要があるので、
0〜60番目のビットのうち、まだ誰も使ってないビットから小さい順に、残りの頂点の個数だけ集めてくる。


これを繰り返せばよい。

ソースコード

class BitwiseAnd {
	public:
	vector<long long> lexSmallest(vector<long long> subset, int N) {
		
		const vector<long long> failed(0);
		if(N > 11) return failed;
		
		int n = subset.size();
		vector<vi> bits;
		set<int> freebits;
		
		rep(i, n) rep(j, i) if((subset[i] & subset[j]) == 0) return failed;
		rep(i, n) rep(j, i) rep(k, j) if(subset[i] & subset[j] & subset[k]) return failed;
		
		rep(i, 60) freebits.insert(i);
		
		rep(i, n){
			ll b = subset[i];
			vi v;
			
			rep(j, n) if(i != j) b &= ~subset[j];
			rep(j, 60) if(b >> j & 1) v.pb(j);
			rep(j, 60) if(subset[i] >> j & 1) freebits.erase(j);
			
			bits.pb(v);
		}
		
		for(int i = n; i <= N - 1; i++){
			
			vi next;
			ll b = 0;
			
			rep(j, i){
				if(bits[j].empty()) return failed;
				
				b |= 1ll << bits[j][0];
				bits[j].erase(bits[j].begin());
			}
			rep(j, N - i - 1){
				if(freebits.empty()) return failed;
				
				b |= 1ll << *freebits.begin();
				next.pb(*freebits.begin());
				freebits.erase(freebits.begin());
			}
			
			bits.pb(next);
			subset.pb(b);
		}
		
		sort(all(subset));
		
		return subset;
	}
};