CSAcademy Round #38 : E. Path Union

なんとかレート増をキープしている。
https://csacademy.com/contest/round-38/task/path-union/

問題

高さNの完全二分木がある。
ここで、根からの深さiの頂点をA[i]個選んだとする。
この時各頂点から根までの辺の和集合を考える。

和集合に含まれる辺の数が最大となるような頂点の選び方を答えよ。

解法

深い方から順に処理していく。
A[i]個選ぶ際、それらから生成される根までの辺の数が最大になるのは、頂点同士できるだけ離れているのが良い。
逆に言えば、0,1,2,3...を(i桁の２進数とみなして)bit順を反転した順に配置すればよい。

こうして深さiの点を選んだら次に深さ(i-1)について処理していく。
今度は深さiの頂点を選んだ際にそこから根までの辺でカバーされる頂点以外の点に対し、同様にbit順反転順に同様に配置していこう。

int N;
ll A[65];
vector<ll> ret;

unsigned long long bitrev(unsigned long long x,int d=64) {
	x = (((x & 0xaaaaaaaaaaaaaaaaULL) >> 1) | ((x & 0x5555555555555555ULL) << 1));
	x = (((x & 0xccccccccccccccccULL) >> 2) | ((x & 0x3333333333333333ULL) << 2));
	x = (((x & 0xf0f0f0f0f0f0f0f0ULL) >> 4) | ((x & 0x0f0f0f0f0f0f0f0fULL) << 4));
	x = (((x & 0xff00ff00ff00ff00ULL) >> 8) | ((x & 0x00ff00ff00ff00ffULL) << 8));
	x = (((x & 0xffff0000ffff0000ULL) >>16) | ((x & 0x0000ffff0000ffffULL) <<16));
	x = ((x >> 32) | (x << 32));
	
	return x>>(64-d);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	FOR(i,N) cin>>A[i+1];
	
	ll did=0;
	set<ll> skip;
	for(i=N;i>=1;i--) {
		ll cur=0;
		set<ll> skip2;
		FOR(x,A[i]) {
			while(cur<1LL<<i) {
				ll val=bitrev(cur,i);
				cur++;
				if(skip.count(val)==0) {
					skip2.insert(val);
					ret.push_back((1LL<<i)+val);
					goto next;
				}
			}
			if(cur==1LL<<i) {
				ll a=*skip.begin();
				skip.erase(a);
				skip2.insert(a);
				ret.push_back((1LL<<i)+a);
			}
			next:
			;
		}
		set<ll> ns;
		FORR(e,skip) ns.insert(e/2);
		FORR(e,skip2) ns.insert(e/2);
		swap(skip,ns);
	}
	sort(ALL(ret));
	FORR(e,ret) cout<<e<<endl;
	
}

まとめ

bit順反転をライブラリ化しておいた。