TopCoder, Single Round Match 650, Division 2, Level 1 : TaroJiroDividing

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13672&rd=16314

問題概要

　2 つの正整数 のそれぞれに対し，次の操作を行う．
　操作対象になった値を と書くことにすると，

1. を紙に書き下す
2. が奇数ならば，操作を終了する
3. を で置き換える

　 に対する操作と に対する操作の，両方で紙に書き下される値の個数を求めよ．
　

解法

　 が大きいですが，操作に於いて値は半分になっていくので，操作のステップ数は および 回程度になります．従って，それぞれの操作をシミュレーションして，紙に書き下される数のリスト（データ構造的な意味ではなく）を求めるのは， 時間で完了します．
　あとは，2 つの配列に共通して含まれる要素の数を求めることができれば，問題を解くことができます．題意より，それぞれの配列について，その要素は相異なります．従って，それぞれの配列から要素を 1 つずつ選んで組にするパターンを全通り試す 2 重ループで数えることができます．しかし，STL には std::set_intersection という，まさにこのための関数が用意されているので，これを使うことで共通部分を取り出すことができ，その size を調べることで共通部分の要素数も知ることができます．std::set_intersection は入力範囲がソート済みであることを要求しますが，操作に於いて書き下される値は降順に生成されるので std::reverse をしておく（または std::set_intersection に適切なファンクタを渡す）だけで済みます．
　操作のシミュレートにかかる時間と，書き下される要素数はどちらも で，std::set_intersection は入力範囲の長さの和に対して線形時間で動くので，全体の実行は 時間で完了します．

コード

using VI = vector< int >;

#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define PB push_back
#define BI back_inserter

class TaroJiroDividing
{
public:
	int getNumber( int A, int B )
	{
		const VI a = play( A ), b = play( B );
		VI both;
		set_intersection( ALL( a ), ALL( b ), BI( both ) );
		return SZ( both );
	}

	VI play( int n )
	{
		VI res( 1, n );
		for ( ; n % 2 == 0; n /= 2, res.PB( n ) );
		reverse( ALL( res ) );
		return res;
	}
};