TopCoder, Single Round Match 667, Division 1, Level 1 : OrderOfOperations

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13987&rd=16547

問題概要

　問題設定は Division 2, Level 2 と同一だが制約が異なる．
　$1 \leq N \leq 50$
　$1 \leq M \leq 20$

解法

　Div.2 Edition と比べて $N$ の制約が大きくなっています．こうなると Div.2 での $\Omega( 2^N )$ の解法は TLE するので別の方法を考えます．

　まず，$N$ は $2$ の肩に乗りませんが $M $ ならば乗せられるということに気が付きます．そこで，「実行済みの命令の集合」ではなく「使用済みメモリの集合」に対して答えを記録することを考えます．つまり，次のような状態数 $O( 2^M )$ の動的計画法をできそうな気持ちになります．

• dp[ 使用済みメモリの集合（を整数にエンコードしたもの） ] := ここに至る最小コスト

　初期状態は基本 INF で，dp[ 0 ] のみ 0 です．
　dp[ b ] からの遷移は，次に実行する命令を全て試すことになります．$i$ 番目の命令を実行する場合を試すとして，その命令が使うメモリ集合のビット表現が t であるとします．このとき，実行後の使用済みメモリ ns は b との bitwise OR となるので，ns = b | t です．このときに掛かるコストは新たに使われるメモリの数の 2 乗ですが，s から ns への増分は ns ^ s なので，ns ^ s で立っているビットの数が新たに使われるメモリの数 d となります．従ってこのときの遷移は

• dp[ ns ] を dp[ s ] + d * d で更新

となります．
　題意より，欲しい答えは全ての命令を実行し終わった状態へ至る最小コストです．全ての命令を実行し終わったときのメモリの状態は，$s$ の各要素のビット表現全ての bitwise OR を取った状態に一致するので，dp[ $s$ 各要素のビット表現全ての bitwise OR ] に答えが求まります．
　$s$ の要素ををビット表現にエンコードしたものを度々使っていますが，これを DP のループ中で毎回求めてしまうとオーダーレベルで遅くなるので注意が必要です（わたしは TLE しました）．$s$ の要素のビット表現は不変なので，事前に求めておけます．

　この DP は状態数が $O( 2^M )$ で，各状態からの $O( N )$ 通りの遷移を総当りしています．OR 及び OXR 演算と __builtin_popcount() が定数時間だと仮定すると（一応，ビット数を固定すれば定数時間と言える），全体の計算量は $O( 2^M N )$ 時間となります．

コード

using VI = vector< int >;
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 FOR( e, c ) for ( auto &e : c )
#define ALL( c ) begin( c ), end( c )

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

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

int dp[ 1 << 20 ];

class OrderOfOperations
{
public:
	int minTime( vector <string> S )
	{
		const int N = SZ( S ), M = SZ( S[0] );

		VI bits;
		transform( ALL( S ), BI( bits ), [=]( const string &s ){
			int res = 0;
			REP( i, M )
			{
				res <<= 1;
				res |= s[i] - '0';
			}
			return res; } );


		fill( ALL( dp ), INF );
		dp[0] = 0;

		REP( s, 1 << M )
		{
			FOR( t, bits )
			{
				const int ns = s | t;
				if ( ns == s )
				{
					continue;
				}

				const int d = __builtin_popcount( ns ^ s );
				dp[ ns ] = min( dp[ ns ], dp[s] + d * d );
			}
		}

		const int ends = accumulate( ALL( bits ), 0, bit_or< int >() );
		return dp[ ends ];
	}
};