kmjp's blog

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

Codeforces #312 Div2 C. Amr and Chemistry

CF#312に参加。
あまり解くの早くなかったし、Dもミスったし微妙でした。
http://codeforces.com/contest/558/problem/C

問題

N要素の整数列A[i]が与えられる。

この数列に、以下の処理を繰り返す。

  • 1要素の値を倍にする。
  • 1要素の値を半分(小数切り捨て)にする。

全要素を同じ値にするのに必要な最小処理回数を求めよ。

解法

まず、全要素を2進数表記したときの共通prefixを求めよう。
解としてあり得るのは、この共通prefixに2の累乗を掛けたものである。

よって、そのような(共通prefix×2の累乗)を総当たりし、処理回数を求めればよい。

int N;
int A[101010],B[101010];
vector<int> V;

int dodo(int a,int b) {
	int num=0;
	while(b%a || ((b/a)&(b/a-1))) num++, a/=2;
	b/=a;
	while(b>1) num++, b/=2;
	return num;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		y=A[i];
		while(y%2==0) y/=2;
		V.push_back(y);
	}
	
	sort(V.begin(),V.end());
	x=1;
	while(x*2<=V[0]) x*=2;
	FOR(i,V.size()) while(V[i]>=x*2) V[i]/=2;
	
	while(1) {
		sort(V.begin(),V.end());
		V.erase(unique(ALL(V)),V.end());
		if(V.size()==1) break;
		FORR(r,V) r/=2;
	}
	
	ll mi=10101010;
	for(int v=V[0];v<=1<<20;v*=2) {
		ll tot=0;
		FOR(x,N) tot += dodo(A[x],v);
		mi=min(mi,tot);
	}
	cout<<mi<<endl;
}

まとめ

Div2Cにしては少し難しめか?