torus711 のアレ

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

TopCoder, Single Round Match 668, Division 2, Level 1 : VerySecureEncryption

問題概要

 $N$ 文字からなる文字列 $\mathit{ message }$ に対し,次の操作を考える.

  • 各位置 $i$ について,$\mathit{ message }_i$ の文字が位置 $\mathit{ key }_i$ に表れる文字列で置き換える

この操作を $K$ 回適用した結果を求めよ.
 $N \leq 10$
 $K \leq 50$

解法

 答えを求める方法が問題文で与えられているので,これをそのまま実装することで解くことができます.in-place でやろうとすると難しいので,結果を格納するための文字列を別に作っておいて,完了後に置き換えるとかするとよいと思います.
 一回の変換に $O( N )$ 時間かかり,それを $K$ 回やるので全体では $O( NK )$ 時間となります.

コード

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )

#define SZ( v ) ( (int)( v ).size() )

class VerySecureEncryption
{
public:
	string encrypt( string message, vector <int> key, int K )
	{
		if ( K == 0 )
		{
			return message;
		}

		string res( message );
		REP( i, SZ( message ) )
		{
			res[ key[i] ] = message[i];
		}
		return encrypt( res, key, K - 1 );
	}
};