なかなか面白い問題。
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; }
まとめ
コードも短いし、なかなか解き味も良かった。