torus711 のアレ

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

TopCoder SRM 591, Division 2, Level 2 : ConvertibleStrings

概要

長さが等しい二つの文字列 X, Y が次の条件を満たすとき、「変換可能」であるとする。

  • アルファベットの順列を一つ選び P とする
  • X[ i ] を P[ X[ i ] ] で置き換えたものが X と等しい

'A' 〜 'I' のアルファベットから成る二つの文字列 A, B が与えられる。
この二つの文字列に対し、次の操作ができる。

  • インデックスを一つ選び、二つの文字列からその位置の文字を削除する

A, B を変換可能にするために必要な操作回数の最小値を求めよ。

解法

アルファベットが 9 種類しか無いことを利用します。
9! = 362,880 なので、アルファベットの順列を全通り試すことができます。
順列 P が決まったとき、P[ A[ i ] ] \neq B[ i ] なる i の数が、削除しなければならない数です。
そのような値の内、最小のものが問題の答えです。

コード

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()

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

		VI mapping( 9 );
		iota( ALL( mapping ), 0 );

		int res = INT_MAX;
		do
		{
			int tmp = 0;
			REP( i, 0, L )
			{
				tmp += mapping[ A[i] - 'A' ] != B[i] - 'A';
			}
			res = min( res, tmp );
		}
		while ( next_permutation( ALL( mapping ) ) );

		return res;
	}
};