torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 572, Division 2, Level 2 : NextOrPrev

概要

英小文字からなる文字列に対する操作として、次の二つが許される。

  • 'z' 以外の一文字について、文字列中にある全てのその文字をアルファベット順で一つ後ろの文字に変える
  • 'a' 以外の一文字について、文字列中にある全てのその文字をアルファベット順で一つ前の文字に変える

それぞれの操作にかかるコストと、文字列 start および goal が与えられる。
start と goal はそれぞれ、同一の文字は一つしかない。
start を goal に変換するのにかかるコストの最小値を求めよ。
変換が不可能な場合は -1 を返せ。

解法

変換の過程で同一文字が二つ以上になってしまうと、もう分離できないので goal に変換することはできません。
例えば "ae" -> "cb" のとき、'a' -> 'c' では 'b' を、'e' -> 'b' では 'c' をまたぐときに同一文字になってしまいます。
これは、「文字列中に於ける順序関係は変更できない」と言い換えることができます。
従って、これを満たさない場合は解無しとなります。
解が存在するとすれば、変換順序さえうまくすれば、ある文字を一度逆方向に変換してから戻す操作は必要ありません。
従って、各インデクスについて目標の文字まで直接的に変換する場合のコストの総和が答えになります。

コード

typedef vector<int> VI;

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

class NextOrPrev
{
public:
	int getMinimum( int nextCost, int prevCost, string start, string goal )
	{
		VI ranks1( compRanks( start ) ), ranks2( compRanks( goal ) );

		if ( ranks1 != ranks2 )
		{
			return -1;
		}

		int res = 0;
		REP( i, 0, start.size() )
		{
			if ( start[i] < goal[i] )
			{
				res += ( goal[i] - start[i] ) * nextCost;
			}
			else
			{
				res += ( start[i] - goal[i] ) * prevCost;
			}
		}
		return res;
	}

	VI compRanks( string str )
	{
		string sorted( str );
		sort( ALL( sorted ) );

		VI res;
		REP( i, 0, str.size() )
		{
			res.PB( find( ALL( sorted ), str[i] ) - sorted.begin() );
		}
		return res;
	}
};