kmjp's blog

競技プログラミング参加記です

Codeforces #683 Div1 C. Xor Tree

なかなか面白い問題。
https://codeforces.com/contest/1446/problem/C

問題

distinctな非負整数列Bに対し、以下のようにグラフを作る。
Bの各要素iに対応する頂点を作る。
各iに対し、B[i] xor B[j]が最小となるi以外のjを求め、i-j間に辺を張る。

今ここでdistinctな非負整数列Aが与えられる。
Aの部分文字列のうち、上記手段でできるグラフが木になるようにしたい。
Aから最小いくつ要素を削ればよいか求めよ。

解法

(整数値, 連結頂点数)のPairの集合を考える。
最下位ビットから、以下を順次行う。
今k bit目を見ているとする。
k bit目だけが異なる2つのPairが存在している場合、それらが上記手順で連結になるためには、片方の連結要素内の頂点数が1でなければならない。
そこで、要素数が少ない方を1つだけ残して削ろう。

上記処理を順次行うと、最終的に1つの連結成分になる。

int N;
vector<pair<int,int>> A;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		A.push_back({x,1});
	}
	sort(ALL(A));
	int num=0;
	while(A.size()>1) {
		vector<pair<int,int>> B;
		FOR(i,A.size()) {
			if(i<A.size()-1&&(A[i].first^1)==A[i+1].first) {
				x=A[i].second;
				y=A[i+1].second;
				int n=max(x,y)+1;
				num+=x+y-n;
				B.push_back({A[i].first/2,n});
				i++;
			}
			else {
				B.push_back({A[i].first/2,A[i].second});
			}
		}
		swap(A,B);
		
	}
	cout<<num<<endl;
	
	
	
}

まとめ

コードも短いし、なかなか解き味も良かった。