TopCoder, SRM 615, Division 2, Level 3 : MergeStrings

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13095&rd=15848

問題概要

　文字列 S, A, B が与えられる。S は英大文字及び '?' からなり、A, B は英大文字からなる。二つの文字列について、'?' を（独立に）任意の文字に置き換えることで等しい文字列にできるならばその二つの文字列はマッチすると言う。
　また、文字列 C を空文字列から始めて次のように構成する。

• A, B いずれかの先頭の文字を取り除いて C に連結する操作を A, B が共に空文字列になるまで繰り返す

すなわち、C は A, B の部分列をオーバーラップせずに含む。S とマッチする C であって辞書順最小のものを求めよ。存在しない場合は空文字列で示せ。

解法

　A, B それぞれから使った文字数が等しいとき、S に於ける該当位置と以降の選択肢は等しくなります。また、辞書式順序の特性から、より手前の文字同士の比較が支配的になります。従って、それぞれから使った文字数が等しい状態が複数存在するとき、その内最適でないものから最適解を得ることはできません。そのような状態の重複を排除するために、次のような DP を考えることができます。

• dp[ A から i 文字使った ][ B から j 文字使った ] := i + j 文字の辞書順最小の文字列

　初期状態は dp[ 0 ][ 0 ] のみ空文字列で、それ以外は文字列の min 演算の単位元（ e.g. "~"）です。
　dp[ i ][ j ] からの遷移は、A, B のどちらから取るかを両方試すので、

• dp[ i + 1 ][ j ] を dp[ i ][ j ] + A[ i ] で更新（ i < N で S と A の該当位置がマッチ）
• dp[ i ][ j + 1 ] を dp[ i ][ j ] + B[ i ] で更新（ j < M で S と B の該当位置がマッチ）

の二通りです。
　テーブルを埋め終わったあと、dp[ N ][ M ] が答えです。初期状態のまま残っている場合は解無しなので、代わりに空文字列を return します。
　計算量は、A, B の長さをそれぞれ N, M とすると状態数が 、遷移時の文字列連結コストも なので、全体では です。

コード

using VS = vector<string>;
template < typename T = int > using VT = vector<T>;

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

class MergeStrings
{
public:
	string getmin( string S, string A, string B )
	{
		const int N = A.size(), M = B.size();

		VT<VS> dp( N + 1, VS( M + 1, "~" ) );
		dp[0][0] = "";

		REP( i, 0, N + 1 )
		{
			REP( j, 0, M + 1 )
			{
				if ( i < N && ( S[ i + j ] == '?' || S[ i + j ] == A[i]  ) )
				{
					dp[ i + 1 ][j] = min( dp[ i + 1 ][j], dp[i][j] + A[i] );
				}
				if ( j < M && ( S[ i + j ] == '?' || S[ i + j ] == B[j] ) )
				{
					dp[i][ j + 1 ] = min( dp[i][ j + 1 ], dp[i][j] + B[j] );
				}
			}
		}

		return dp[N][M] == "~" ? "" : dp[N][M];
	}