torus711 のアレ

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

TopCoder, Single Round Match 650, Division 2, Level 2 : TaroFillingAStringDiv2

問題概要

 'A', 'B', '?' からなる文字列 S が与えられる.この文字列中の '?' を 'A' まては 'B' に(独立に)置き換えることを考える.
 文字列の "ugliness"(醜さ)を,文字列中で同じ文字が隣接している箇所の総数と定義する.
 ugliness を最小にするように文字を決めたとき,達成できる最小の ugliness を求めよ.
 |S| \leq 50

解法

 |S| = L と書きます.
 '?' への割り当てを全通り試そうとすると,最大 L 箇所に対してそれぞれ 2 通りの選択肢があるので,O( 2^L ) かかってしまいます.これでは当然 TLE するので,より高速な方法を考える必要があります.
 ugliness が増える条件を考えると,ある文字が影響するのは隣接する文字に対してのみです.すると,確定している部分の文字数と,その末尾の文字が同じ状態であれば,それ以降に達成できる ugliness は同じになることが分かります.従って,確定している部分の文字数と末尾の文字が同じ状態が複数あったとき,ugliness 最小のもの以外から,全体での最適解を得ることはできません.このことを踏まえると,次のような動的計画法を考えることができます.

  • dp[ 決めた文字数 ][ 決定している部分の末尾の文字(を表す数値)] := 最小の ugliness

2 つ目の次元は,末尾が 'A' ならば 0 ,'B' ならば 1 とします.初期状態では dp[ 0 ][ 2 ] を 0 として,それ以外を INF (適当に大きい値)としておきます.ここで,2 は 'A' とも 'B' とも同一視されない数値です.dp[ i ][ j ] からの遷移は 2 通りになります.

  • 次の文字を 'A' にする -> dp[ i + 1 ][ 0 ] を更新( S_i が '?' または 'A' のときのみ)
  • 次の文字を 'B' にする -> dp[ i + 1 ][ 1 ] を更新( S_i が '?' または 'B' のときのみ)

更新時,次の文字が,末尾と違う文字ならば dp[ i ][ j ] で,そうでなければ dp[ i ][ j ] + 1 で,遷移先との min で更新します.
 更新が終わったあと,dp[ L ][ 0 ] と dp[ L ][ 1 ] の内小さい方が答えです.
 状態の数は L の高々定数倍であり,各状態からの遷移の数も高々定数個であるので,O( L ) 時間で計算できます.

コード

template < typename T = int > using LIM = numeric_limits< T >;

#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 AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )

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

constexpr int INF = LIM<>::max() / 2;

int dp[ 64 ][ 4 ];

class TaroFillingAStringDiv2
{
public:
	int getNumber( string S )
	{
		{ // initialize for local test
			fill( AALL( dp, int ), INF );
		}

		const int L = SZ( S );

		dp[0][2] = 0;
		REP( i, L )
		{
			REP( j, 3 )
			{
				REP( k, 2 )
				{
					if ( S[i] != '?' && S[i] != ( 'A' + k ) )
					{
						continue;
					}
					dp[ i + 1 ][k] = min( dp[ i + 1 ][k], dp[i][j] + ( j == k ) );
				}
			}
		}

		return min( dp[L][0], dp[L][1] );
	}
};