Codeforces #272, Division 1, C ( Division 2, E ) : Dreamoon and Strings

問題文

　http://codeforces.com/contest/477/problem/C

問題概要

　二つの文字列 が与えられる。 から 文字を消去したとき、 が に重複しない部分文字列として表れる個数の最大値を全ての について求めよ。
　
　

解法

　消す位置を全て試すようなことは当然できないので、何らかの手段で時間計算量を削減する必要があります。貪欲法が脳裏をよぎりますが、先頭から貪欲にマッチさせると上手くいかないケースがあるので、貪欲法で解くことはできません。
　とりあえず、次のような動的計画法を考えてみます。

• dp[ i 文字考慮した ][ j 文字消去した ][ の k 文字目までマッチしている ] := マッチの最大数

このままだと状態数が になってまだ TLE します（ついでに MLE も）。
　ここで、部分的に貪欲法を適用します。貪欲法で解くことはできないと上で書きましたが、ある位置以降で にマッチさせようとした場合、できるだけ手前でマッチを完了させた方が後で使える文字が増えて得になることは言えるはずです。また、上記の DP に於いて、マッチの数が変わるのは k == になる遷移をしたときだけです。この二点を踏まえると、各状態から マッチ数が増える遷移は一通りに定まります。従って、 へのマッチを一文字ずつ行うのではなく、 文字分まとめて処理することで最後の次元を削ることができます。この改良を加えると、DP の状態の取り方は次のようになります。

• dp[ i 文字考慮した ][ j 文字消去した ] := マッチの最大数

各位置からのマッチ完了位置の最適位置とそのときの消去文字数をそれぞれ jump_to, del という配列に格納したとすると dp[ i ][ j ] からの状態遷移は

• dp[ i + 1 ][j] を dp[ i ][ j ] で更新（着目している文字を残す）
• dp[ i + 1 ][ j + 1 ] を dp[ i ][ j ] で更新（着目している文字を消す）
• dp[ jump_to[i] ][ j + del[i] ] を dp[ i ][ j ] + 1 で更新（ を作る）

となります。また、このようにすると全ての に対する答えをまとめて計算できるので、後は順に出力するだけで問題を解くことができます。
　このアルゴリズムの計算量ですが、マッチ位置の前計算に 時間かかり、DP 本体には 時間かかるので、全体では 時間で走ります。

コード

using VI = vector<int>; using VVI = vector<VI>;
using PII = pair<int,int>; using VPII = vector< pair<int,int> >;
template < typename T = int > using LIM = numeric_limits<T>;

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

#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

constexpr int INF = LIM<>::max() / 2;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	string s, p;
	cin >> s >> p;

	const int L  = s.size(), M = p.size();

	VPII jump_to( L, MP( -1, -1 ) );

	REP( i, 0, L )
	{
		int j, k;
		for ( j = i, k = 0; j < L && k < M; j++ )
		{
			if ( s[j] == p[k] )
			{
				k++;
			}
		}

		if ( k == M )
		{
			jump_to[i] = MP( j, j - i - M );
		}
	}

	VVI dp( L + 1, VI( L + 2, -INF ) );
	dp[0][0] = 0;

	REP( i, 0, L )
	{
		REP( j, 0, L + 1 )
		{
			dp[ i + 1 ][j] = max( dp[ i + 1 ][j], dp[i][j] );
			dp[ i + 1 ][ j + 1 ] = max( dp[ i + 1 ][ j + 1 ], dp[i][j] );

			if ( jump_to[i].fst != -1 && j + jump_to[i].snd <= L )
			{
				int &next = dp[ jump_to[i].fst ][ j + jump_to[i].snd ];
				next = max( next, dp[i][j] + 1 );
			}
		}
	}

	REP( i, 0, L + 1 )
	{
		cout << ( i ? " " : "" ) << dp[L][i];
	}
	cout << endl;

	return 0;
}