問題概要
文字列 と正整数
が与えられる．
から
文字を削除して得られる文字列が与えられたとき，削除された文字の位置を一意に特定できるか否か，求めよ．
はい
前回 に引き続き，賢い解法が思い付かなかったので DP で通しました．が，こういうときに DP に逃げられるのはある種の保険になると思うので，そのまま DP 解について書きます．
解法
と書きます．
「 から
文字を削除した文字列」を「
文字の
の部分列」と言い換えて考えます．こう考えると，削除された文字の位置を特定できない場合とは，部分列に含まれるある文字を複数の場所からとることが可能な場合と言い換えられます．
部分列のある文字を複数の場所から取れる場合とはどんな場合でしょうか？ 今， からいくつかの文字を抜き出した部分列をもっているとします．
を先頭から走査して部分列に加えるか否かを試しているとすると，次に部分列に加える文字より手前に，構成途中の部分列の末尾の文字と同じ文字が
にあれば，どちらの位置から部分列に加えたのか特定できなくなります．
この事を踏まえると，次のように状態をとる動的計画法を考えることができます．
- dp[
から考慮した文字数 ][ 部分列に加えた文字数 ][ 複数の場所から取れるか否か ][ 最後に追加した文字 ] := この状態が可能か否か
状態 dp[ i ][ j ][ k ][ l ] からの遷移は，次の 3 通りになります．
- 位置
の文字を使わない -> dp[ i + 1 ][ j ][ k ][ l ] を更新
- 位置
- 部分列の末尾の文字を複数箇所からとれるようにする -> dp[ i + 1 ][ j ][ k | 1 ][ l ] を更新（ l が表す文字と
が一致している場合に限る）
各状態に対して格納されているのはその状態を作れるか否かを表す boolean なので 更新は全て，dp[ i ][ j ][ k ][ l ] との OR となります．また，初期状態は基本 false で，dp[ 0 ][ 0 ][ 0 ][ 26 ] のみ true となります．26 は，アルファベットを 0-based で数えたとき，どのアルファベットとも一致しない値です．
各状態に対して値を計算し終わったあと，dp[ N ][ L - K ][ 1 ] に 1 つでも true があれば削除されたインデックスは特定不可能で，そうでなければ特定可能です．
コード
#define REP2( i, n ) for ( int i = 0; i < ( int )( n ); ++i ) #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 AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t ) #define SZ( v ) ( (int)( v ).size() ) bool dp[ 64 ][ 64 ][ 2 ][ 32 ]; class Decipherability { public: string check( string s, int K ) { { // initialize for local test fill( AALL( dp, bool ), false ); } const int L = SZ( s ); const int M = L - K; dp[0][0][0][ 26 ] = true; REP( i, L ) { REP( j, M + 1 ) { REP( k, 2 ) { REP( l, 27 ) { // 使わない dp[ i + 1 ][j][k][l] |= dp[i][j][k][l]; // 使う dp[ i + 1 ][ j + 1 ][k][ s[i] - 'a' ] |= dp[i][j][k][l]; // 選択肢作る if ( s[i] - 'a' == l ) { dp[ i + 1 ][j][ k | 1 ][l] |= dp[i][j][k][l]; } } } } } return any_of( AALL( dp[L][M][1], bool ), bind( equal_to< bool >(), _1, true ) ) ? "Uncertain" : "Certain"; } };
