TopCoder SRM 571, Division 1, Level 1 : FoxAndMp3

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12436

概要

Division 2, Level 2 : FoxAndMp3Easy と制約以外同一。

解法

こちらの版では制約が大きいため、全列挙してソートする手法は使えません。

辞書式順序で小さい順に、min( 50, n ) 個生成することについて考えます。
ある数字を表す文字列 S があり、辞書式順序で次に大きいものは S + '0' です。
S' = S + '0' についても同様に、S' + '0' が次に大きいものとなります。
n との比較で 0 を付加できなくなったとき、次に大きいのは S + '1' です。
このように、常に可能な限り小さい数字を付加することで辞書式順序で一つ後ろになる文字列を生成できます。
ということで、DFS で探索して、条件に合うものを必要な数だけ生成すれば OK です。
言い方を変えると、文字列をノード、文字の付加をエッジとしたグラフ（これは木です）に対して、DFS をしていることになります。

コード

typedef vector<string> VS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define PB( n ) push_back( n )

class FoxAndMp3
{
public:
	int lim, n, count;
	VS res;
	
	vector <string> playList( int n )
	{
		this -> n = n;
		lim = min( 50, n );
		count = 0;
		
		res.clear();

		REP( i, 1, 10 )
		{
			dfs( i );
		}

		return res;
	}
	
	void dfs( int cur )
	{
		if ( n < cur || lim <= count )
		{
			return;
		}

		res.PB( genStr( cur ) );
		count++;

		REP( i, 0, 10 )
		{
			dfs( cur * 10 + i );
		}
		return;
	}

	string genStr( int n )
	{
		OSS oss;
		oss << n;
		return oss.str() + ".mp3";
	}
};