TopCoder SRM 677 Div1 Easy DoubleOrOneEasy

本番無駄に長いコード書いてWAするし散々。
https://community.topcoder.com/stat?c=problem_statement&pm=14101

問題

２つの整数(A,B)がある。それぞれ以下の動作を行うことを考える。

• 両者に１加える
• 両者を２倍にする

上記動作を繰り返し、(A,B)を(newA,newB)に遷移させることができるか。
できるなら最小動作回数を求めよ。

解法

２倍を行う回数は30回以下である。
そこで２倍を行う回数を総当たりしよう。

1回２倍を行うと、AとBの差は２倍になる。
よってk回２倍するとき、(B-A)*2^k == (newB-newA)ならそのようなkがありうる。

kが決まったら、あとは２倍をどこで行うか考える。
当然A,Bが大きくなってくる後半に２倍を行うとよい。
逆に考えると、半減及びデクリメントでnewAをAにすると考えれば、できるだけ早い段階で半減を使うのが良い。
この考察をもとに、newAをAにする最小回数を求めよう。

A!=Bの時kは一意に決まるが、A==Bの時はそうでもない。
ただkは小さいので総当たりしても計算時間は問題ない。

class DoubleOrOneEasy {
	public:
	int minimalSteps(int a, int b, int newA, int newB) {
		int mi=1<<30,i;
		
		for(int k=0;k<=30;k++) {
			if((ll)(b-a)<<k==(newB-newA)) {
				int x=newA, t=0;
				FOR(i,k) {
					if(x%2) x--, t++;
					x/=2, t++;
				}
				if(x>=a) mi=min(mi,t+x-a);
			}
		}
		
		
		if(mi>=1<<30) return -1;
		return mi;
	}
}

まとめ

これもうちょいストーリーつけられそうだけどな。