TopCoder SRM 597, Division 1, Level 1 ( Division 2, Level 2 ) : LittleElephantAndString

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12854&rd=15709

概要

長さが等しい二つの文字列 A, B が与えられる。
A に対して、ある文字を先頭に移動する操作のみが許容される。
A を B に変形するために必要な操作回数の最小値を求めよ。
不可能な場合は -1 で示せ。

解法

まず、それぞれの文字列に含まれる文字の（多重）集合が等しくないとき、変形は不可能です。
そうでないとき、最悪の場合でも B の逆順に文字を選んで操作をすれば B を作れるので、変形が可能です。

以下、変形が可能であることが確定した状況下で最小の操作回数を求める方法について考えます。
まず次が言えます。

• 操作が必要な要素の数 = 文字列長 - そのまま残す文字の数

操作の対象となる文字の並びは好きにできるので、問題は「 A の部分列であって、かつ B のサフィックスであるものの最長の長さを求めよ」と言い換えられます。
B のサフィックスなので、A, B を末尾方向から走査します。
上記のような A の部分列を考えたとき、B のある文字と同じ文字が複数あるとすると、使えるものの内で最も後ろにあるものを使った方がその後の自由度が高いので有利です。
従って、A を（末尾から）どこまで使ったかを保持しつつ B を末尾から走査すればよいことになります。
このとき、B の文字と A の文字が一致しなければ、一致するようになるまで A の位置を進めます。（ A を使い切ったら終了）
この操作の回数が問題の答えになります。

コード

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

class LittleElephantAndString
{
public:
	int getNumber( string A, string B )
	{
		const int L = A.size();

		if ( sorted( A ) != sorted( B ) )
		{
			return -1;
		}

		int res = 0;
		for ( int ib = L - 1, ia = ib; 0 <= ib; ib--, ia-- )
		{
			while ( 0 <= ia && A[ ia ] != B[ ib ] )
			{
				ia--;
				res++;
			}
		}
		return res;
	}

	string sorted( string s )
	{
		sort( ALL( s ) );
		return s;
	}
};