TopCoder SRM 594, Division 1, Level 1 : AstronomicalRecords

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12804&rd=15706

概要

ある惑星系にあるいくつかの惑星の大きさの比を、恒星に近いものから順に並べたものが二つ与えられる。
惑星系にある惑星の数の最小数を求めよ。

解法

A, B から一つずつ選び、それらを a, b とします。
このとき、以下のように a : b の比から任意の二惑星の大きさが等しいかどうかを求めることができます。
　
　
　
　(1) 式より、 なら と は同じ大きさ

次に、a, b を仮定した状況下で惑星の最小数を求める方法です。
　dp[ A から i 個考慮した ][ B から j 個考慮した ] := 惑星の最小数
という DP を考えることができます。
状態変化は次の三通りです。

• dp[ i ][ j ] から dp[ i + 1 ][ j ] を dp[ i ][ j ] + 1 で更新
• dp[ i ][ j ] から dp[ i ][ j + 1 ] を dp[ i ][ j ] + 1 で更新
• dp[ i ][ j ] から dp[ i + 1 ][ j + 1 ] を dp[ i ][ j ] + 1 で更新（ A[ i ] と B[ j ] の大きさが同じとき）

dp[ size( A ) ][ size( B ) ] がこのときの最適解です。

以上をまとめると、a, b を全通り試して上記の DP をし、得られた解の内の最小値が答えとなります。

コード

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;

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

const int INF = INT_MAX / 4;

class AstronomicalRecords
{
public:
	int minimalPlanets( vector <int> A_, vector <int> B_ )
	{
		const vector<LL> A( ALL( A_ ) ), B( ALL( B_ ) );
		const int N = A.size(), M = B.size();

		int res = INF;

		FOR( a, A )
		{
			FOR( b, B )
			{
				VVI dp( N + 2, VI( M + 2, INF ) );
				dp[0][0] = 0;

				REP( i, 0, N + 1 )
				{
					REP( j, 0, M + 1 )
					{
						dp[ i + 1 ][j] = min( dp[ i + 1 ][j], dp[i][j] + 1 );
						dp[i][ j + 1 ] = min( dp[i][ j + 1 ], dp[i][j] + 1 );

						if ( i < N && j < M && a * B[j] == b * A[i] )
						{
							dp[ i + 1 ][ j + 1 ] = min( dp[ i + 1 ][ j + 1 ], dp[i][j] + 1 );
						}
					}
				}
			
				res = min( res, dp[N][M] );
			}
		}

		return res;
	}
};