問題概要
特殊なコンピュータがあり，コンピュータにはサイズ $M $ のメモリが積まれている．
このコンピュータ上で $N$ 個の命令を実行したい．各命令は，コンピュータ上のメモリの内いくつかを利用する．命令が実行される順番は決められておらず自由に決めることができるが，全ての命令は丁度 1 回ずつ実行されなければならない．
このコンピュータはキャッシュ戦略により，過去に一度でも使われたメモリの利用にはコストがかからない．しかし，実行しようとしている命令が，一度も使われていないメモリにアクセスするときにはコストが発生する．発生するコストは，新たに使われるメモリの数を $k$ として $k^2$ である．
命令に関する情報は '0', '1' からなる文字列の配列 $s$ であたえられ，$s_{ ij }$ が '1' のとき，$i$ 番目の命令が $j$ 番目のメモリにアクセスすることを表す．
メモリアクセスのコストを最小化する順序で命令を実行したときの，コストの総和を求めよ．
$N, M \leq 20$
解法
Division 1, Level 1 の制約緩和バージョンです．この制約なら $N$ を $2$ の肩に乗せられるので，既に実行した命令の集合をパラメータとする bit DP をすることができます．これは順序を最適化したいときの常套手段です．
以下のように状態をとります．
- dp[ 既に実行した命令を表す集合（を整数にエンコードしたもの）] := それらを実行するための最小コスト
初期化は基本的に INF で，dp[0] のみ 0 とします．
dp[ S ] からの遷移は，次に実行する命令を全て試すことになります．次の命令を全通り試す前に，この時点で使われたメモリがどれであるかを求めます．これは，$s$ を走査して必要なものを抜き出せば求められます．その後で，まだ実行していない命令それぞれに対して，新たにアクセスされるメモリの数 d を求めて，dp[ S | i ] を dp[ S ] + d * d で更新します（i は次に実行する命令のインデックス）．
DP の更新が完了したあと，dp[ ( 1 << N ) - 1 ] に答えが求まっています．
この解法では，DP の状態数が $O\!\left( 2^N \right)$ で，これに各状態での処理時間がかかります．各状態では，前処理で $s$ を走査するのに $O( NM )$ 時間かかり，更新の処理は $O( N )$ 個ある命令に対してサイズ $M $ のメモリの内新たに使われるものを探すのでこちらも $O( NM )$ 時間かかります．従って，全体では $O\!\left( 2^N NM \right)$ 時間となります．
コード
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 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[ 1 << 20 ]; class OrderOfOperationsDiv2 { public: int minTime( vector <string> S ) { const int N = SZ( S ), M = SZ( S[0] ); fill( AALL( dp, int ), INF ); dp[0] = 0; REP( s, 1 << N ) { VI used( M ); REP( i, N ) { if ( !( s & 1 << i ) ) { continue; } REP( j, M ) { used[j] |= S[i][j] == '1'; } } REP( i, N ) { if ( s & 1 << i ) { continue; } int delta = 0; REP( j, M ) { delta += !used[j] && S[i][j] == '1'; } dp[ s | 1 << i ] = min( dp[ s | 1 << i ], dp[s] + delta * delta ); } } return dp[ ( 1 << N ) - 1 ]; } };
