Codeforces #279 Div2 D. Chocolate

色々なアプローチがありそうな問題。
http://codeforces.com/contest/490/problem/D

問題

正方形のブロックを長方形状にくっつけた形の２つのチョコレートがある。
１つ目のサイズはA1*B1、２つ目はA2*B2である。

これらのチョコレートに対し、以下の処理を行える。

• いずれかのチョコレートに対し、幅か高さが偶数なら幅か高さが半分になるように２つに割り、片方を食べる。
• いずれかのチョコレートに対し、幅か高さが３の倍数なら幅か高さが１：２になるように２つに割り、小さい方を食べる。

両方のチョコレートのサイズを同じにしたい。
チョコレートサイズを同じにできる処理回数と、その時のチョコレートのサイズを答えよ。

解法

自分の解法は、まずA1,B1に対し両処理を行って生成できる大きさを列挙し、その積からチョコレートの面積を列挙する。
同様にA2,B2に対し生成できるチョコレートの面積を列挙する。

その後両者から生成できる同じ面積のチョコレートのうち、処理回数が最小のものを求める。

他の人の解法では、両チョコレートに両処理をそれぞれ最大何回行うか求めるものがある。
その結果両チョコレートのサイズが同一ならサイズをそろえることが可能である。
例えば１つ目の処理を１つ目のチョコに最大p1回、２つ目のチョコに最大p2回行うことができるなら、p1＜p2の場合２つ目のチョコに(p2-p1)回処理を行うことでサイズをそろえることができる。

ll A[2],B[2];

map<int,int> S[4];
map<ll,pair<int,pair<ll,ll> > > M[2];

map<int,int> sp(ll v) {
	int sp2=0,sp3=0;
	map<int,int> s;
	
	while(v) {
		ll t=v;
		sp2=0;
		s[t]=sp2+sp3;
		while(t%2==0) t/=2,sp2++, s[t]=sp2+sp3;
		if(v%3!=0) break;
		sp3++;
		v=v*2/3;
	}
	return s;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A[0]>>B[0];
	cin>>A[1]>>B[1];
	
	S[0]=sp(A[0]);
	S[1]=sp(B[0]);
	ITR(it,S[0]) ITR(it2,S[1]) M[0][1LL*it->first*it2->first] = make_pair(it->second+it2->second, make_pair(it->first,it2->first));
	S[2]=sp(A[1]);
	S[3]=sp(B[1]);
	ITR(it,S[2]) ITR(it2,S[3]) M[1][1LL*it->first*it2->first] = make_pair(it->second+it2->second, make_pair(it->first,it2->first));
	
	int mi=100000;
	ll v;
	ITR(it,M[0]) {
		if(M[1].count(it->first)==0) continue;
		i=it->second.first + M[1][it->first].first;
		if(i < mi) mi=i, v=it->first;
	}
	
	if(mi==100000) {
		_P("-1\n");
	}
	else {
		_P("%d\n",mi);
		_P("%lld %lld\n",M[0][v].second.first,M[0][v].second.second);
		_P("%lld %lld\n",M[1][v].second.first,M[1][v].second.second);
	}
}

まとめ

他の人の解法の方がシンプルだったかもな。