TopCoder SRM 588, Division 1, Level 1 : GUMIAndSongsDiv1

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12706&rd=15700

概要

ほぼ Divisin 2, level 2 と同一で、N <= 50

解法

こちらは N が大きいので、bit DP を用いることができません。
「既に歌った曲の集合」を考慮しなくて済むようにする必要があります。

tone について考察します。
同じ tone の曲が複数あった場合、それらを歌うとすれば連続して歌った方が所要時間が短くなります。
また、tone を変える場合も、できるだけ差が小さくなるように変えた方が所要時間が短くなります。
従って、tone をキーとしてソートしておくことで、tone に関して最適な順序が分かります。

あとは、この順序からどの曲を歌うかを決めればよいことになりますが、曲ごとに歌うか歌わないかで分岐すると 2^N になるのでだめです。
しかし、「考慮した曲の数」と「歌った曲の数」と「最後に歌った曲の tone 」が同一の状態のうち、所要時間が最短でないものは必要無いので、次のような DP を考えることができます。
　dp[ i 曲考慮して ][ j 曲歌った ][ 最後に歌った曲の tone が k ] := 最短の所要時間
ただし、これだけだと tone の値の範囲が広くて状態数が肥大しています。
N <= 50 であることから、実際に現れる tone の種類は高々 50 であることを利用して tone を座標圧縮することで状態数を N^3 程度に抑える事ができ、これなら大丈夫です。
各状態からの遷移は、次の曲を歌うか歌わないかでの分岐なので、dp[ i ][ j ][ k ] から dp[ i + 1 ][ j + 1 ][ 次の曲の tone ] と dp[ i + 1 ][ j ][ k ] を更新すればよいです。
最短の所要時間が T 以下の状態の内、最大の j が答えになります。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
typedef vector<PII> VPII;

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

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

const int INF = INT_MAX / 2;

class GUMIAndSongsDiv1
{
public:	
	int maxSongs( vector <int> duration, vector <int> tone, int T )
	{
		const int N = duration.size();

		VPII songs;
		VI tones;
		REP( i, 0, N )
		{
			songs.PB( MP( tone[i], duration[i] ) );
			tones.PB( tone[i] );
		}
		sort( ALL( songs ) );
		sort( ALL( tones ) );
		// song := ( tone, duration )

		vector<VVI> dp( N + 1, VVI( N + 2, VI( tones.size(), INF ) ) );
		fill( ALL( dp[0][0] ), 0 );

		REP( i, 0, N )
		{
			REP( j, 0, N + 1 )
			{
				REP( k, 0, tones.size() )
				{
					{
						int &next = dp[ i + 1 ][ j + 1 ][ lower_bound( ALL( tones ), songs[i].fst ) - tones.begin() ];
						next = min( next, dp[i][j][k] + abs( tones[k] - songs[i].fst ) + songs[i].snd );
					}
					dp[ i + 1 ][j][k] = min( dp[ i + 1 ][j][k], dp[i][j][k] );
				}
			}
		}

		int res = 0;
		REP( j, 0, N + 1 )
		{
			REP( k, 0, tones.size() )
			{
				if ( dp.back()[j][k] <= T )
				{
					res = max( res, j );
				}
			}
		}

		return res;
	}
};