torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

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

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

 A に対する操作と B に対する操作の,両方で紙に書き下される値の個数を求めよ.
 A, B \leq 10^9

解法

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

コード

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;
	}
};