問題概要
$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 ); } };