TopCoder, SRM 620, Division 1, Level 1 : PairGame

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13142&rd=15853

問題概要

　正整数の順序対 ( x, y ) について、( x + y , y ) または ( x, y + x ) に変化させる操作を任意回数できる。
　二つの順序対 ( a, b ), ( c, d ) を共に生成できる ( x, y ) であって、x + y が最大のものを求め、x + y の値を返せ。存在しない場合は -1 で示せ。
　

解法

　a, b, c, d の最大値を M と書きます。
　ある順序対 ( x, y ) が操作によって作られたとすれば、直前の状態として有り得るのは ( x - y, y ) か ( x, y - x ) です。しかし、正整数のみについて考えているので、x - y や y - x が 0 以下になるケースは除外できます。この内一方は必ず 0 以下なので、結局、( x, y ) の直前の順序対は一意に定まります。これは再帰的に適用できるので、( a, b, ), ( c, d ) それぞれについてそれを生成することができる順序対の集合を 時間で計算できます。また、集合の要素数は です。
　以上のようにして得られた二つの集合を c1, c2 とすれば解候補は c1, c2 の共通部分に含まれる要素です。これは std::set_intersection を用いて で計算できます。後は、共通部分の要素を総当りして x + y が最大となるものを探せば、問題を解くことができます。共通部分が空集合のとき、解が存在しないので -1 です。走査前の初期値を -1 としておくといい感じになります。
　なお、c1, c2 の要素の組み合わせを全探索して共通部分を探すと になるので多分やばいです（試してない）。std::set_intersection を使わない場合でも*1、c1 の各要素について c2 を二分探索すれば になって間に合わせることができます。

コード

using PII = pair<int,int>;
using VPII = vector< pair<int,int> >;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

#define fst first
#define snd second

class PairGame
{
public:
	int maxSum( int a, int b, int c, int d )
	{
		const VPII res1 = solve( a, b );
		const VPII res2 = solve( c, d );

		VPII intersection;
		set_intersection( ALL( res1 ), ALL( res2 ), back_inserter( intersection ) );

		int res = -1;
		FOR( p, intersection )
		{
			res = max( res, p.fst + p.snd );
		}
		return res;
	}

	VPII solve( int x, int y )
	{
		VPII res;

		while ( 0 < min( x, y ) )
		{
			res.emplace_back( x, y );

			if ( x < y )
			{
				y -= x;
			}
			else
			{
				x -= y;
			}
		}

		sort( ALL( res ) );
		return res;
	}
};

*1:残念ながらマイナーっぽいので……