Codeforces #798 : Div2 E. ANDfinity

この回途中で抜けちゃったけど、だいぶ簡単だったっぽい？
https://codeforces.com/contest/1689/problem/E

問題

N要素の整数列Aが与えられる。
N頂点の無向グラフにおいて、A[i]とA[j]のbitwise-andが正の場合、i番とj番の頂点に辺を張ることにする。

Aの任意要素を、非負整数の範囲でインクリメント・デクリメントできる場合、グラフが連結となるには最小何回インクリメント・デクリメントすればよいか。
構成例を示せ。

解法

A[i]が0のものは、まずインクリメントしておこう。
それ以降、インクリメント・デクリメントは実は高々2回で済む。
1回のケースは、総当たりで試そう。

以下2回のケースを示す。
Aのうち、最下位のビットが最も大きいものを選び、デクリメントすれば、それ未満のビットはすべて立つ。
もし最下位のビットが最も大きいものが2個以上あれば、2つ目をインクリメントすればよい。

int T,N;
int ret;
int A[2020];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<2050> uf;

int check() {
	uf.reinit(N+30);
	int i,j;
	FOR(i,N) FOR(j,30) if(A[i]&(1<<j)) uf(i,N+j);
	FOR(i,N) if(uf[i]!=uf[0]) return 0;
	cout<<ret<<endl;
	FOR(i,N) cout<<A[i]<<" ";
	cout<<endl;
	return 1;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		ret=0;
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
			if(A[i]==0) {
				ret++;
				A[i]++;
			}
		}
		if(check()) continue;
		ret++;
		int msb=0;
		FOR(i,N) {
			msb=max(msb,(-A[i])&A[i]);
			A[i]++;
			if(check()) break;
			A[i]-=2;
			if(check()) break;
			A[i]++;
		}
		if(i<N) continue;
		ret++;
		FOR(i,N) if(((-A[i])&A[i])==msb) {
			A[i]++;
			break;
		}
		FOR(i,N) if(((-A[i])&A[i])==msb) {
			A[i]--;
			break;
		}
		check();
	}
}

まとめ

デクリメントでいっぱいビットを立てていく考え方は面白いな。