TopCoder SRM 612, Division 1, Level 1 : EmoticonsDiv1

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=10543&rd=15845

問題概要

　丁度一つの顔文字を含むテキストファイルを、次の三種類の操作によって編集する。

• 全ての文字列をクリップボードにコピーする
• クリップボードの文字列をバッファにペーストする
• バッファから顔文字を一つ削除する

それぞれの操作には 1 秒の時間が掛かる。顔文字の数を smiles にするために必要な時間の最小を求めよ。

解法

　編集途中で取り得るそれぞれの状態は、( バッファにある顔文字の数, クリップボードにある顔文字の数 ) で一意に識別できます。これを ( n, m ) とすると、それぞれの操作による状態遷移は

• コピー：( n, m ) -> ( n, n )
• ペースト：( n, m ) -> ( n + m, m )
• 削除：( n, m ) -> ( n - 1, m )

という具合にパラメータが変化します。ここで、状態を頂点、状態遷移を辺とした有向グラフを考えることができます。このグラフ上で、( 1, 0 ) から ( smiles, x ) ( x は非負の整数 ) で表されるいずれかの頂点への最短路のうち、コスト最小のもの（のコスト）が答えとなります。辺の重みは一様に 1 なので、( 1, 0 ) からの BFS で単一始点最短路問題を解くことにより、問題の解を得ることができます。バッファの顔文字の数は無限に大きくすることが可能ですが、少なくとも smiles の二倍以上あると無駄なので [ 0, smiles * 2 ) の範囲だけ計算すればよいです。

コード

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

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

const int INF = INT_MAX / 2;

class EmoticonsDiv1
{
public:
	int printSmiles( int smiles )
	{
		VVI distances( smiles * 2, VI( smiles * 2, INF ) );
		distances[1][0] = 0;

		typedef tuple<int,int,int> State;
		queue<State> que;
		que.push( State( 0, 1, 0 ) );

		while ( !que.empty() )
		{
			const int d = get<0>( que.front() );
			const int n = get<1>( que.front() );
			const int m = get<2>( que.front() );
			que.pop();

			// copy
			if ( d + 1 < distances[n][n] )
			{
				distances[n][n] = d + 1;
				que.push( State( distances[n][n], n, n ) );
			}
			// paste
			if ( n + m < smiles * 2 && d + 1 < distances[ n + m ][m] )
			{
				distances[ n + m ][m] = d + 1;
				que.push( State( distances[ n + m ][m], n + m, m ) );
			}
			// delete
			if ( 0 < n && d + 1 < distances[ n - 1 ][m] )
			{
				distances[ n - 1 ][m] = d + 1;
				que.push( State( distances[ n - 1 ][m], n - 1, m ) );
			}
		}

		return *min_element( ALL( distances[ smiles ] ) );
	};