Codeforces ECR #176 : D. Equalization

本番網にあっさり解いてるな。
https://codeforces.com/contest/2075/problem/D

問題

2値X,Yが与えられる。
整数kを選び、XかYのいずれかを2^kで割って小数点以下を切り捨てる、という処理を繰り返す。
その際かかるコストは2^kである。
同じkを2回以上使えない場合、X=Yにするのに必要な最小コストを求めよ。

解法

f(a,b) := Xを2^a、Yを2^b割るのにかかる最小コスト
とする。X,Yの上限は2^60以下なので、a,bは60程度までDPで求めておこう。

あとは、X,Yに対しX/(2^a)==Y/(2^b)となるa,bを総当たりし、f(a,b)の最小値を答えよう。

int T;
ll X,Y;

ll co[130][130];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(x,130) FOR(y,130) co[x][y]=1LL<<60;
	co[0][0]=0;
	FOR(x,60) {
		for(i=120;i>=0;i--) for(j=120;j>=0;j--) {
			if(i+x<=130) co[i+x][j]=min(co[i+x][j],co[i][j]+(1LL<<x));
			if(j+x<=130) co[i][j+x]=min(co[i][j+x],co[i][j]+(1LL<<x));
		}
	}

	
	
	cin>>T;
	while(T--) {
		cin>>X>>Y;
		ll ret=1LL<<60;
		FOR(x,60) FOR(y,60) if((X>>x)==(Y>>y)) ret=min(ret,co[x][y]);
		cout<<ret<<endl;
	}
}

まとめ

ECRの4問目にしては簡単かも。