TopCoder SRM 667 Div1 Easy OrderOfOperations、Div2 Medium OrderOfOperationsDiv2

Mediumが難しかったこともあり、Easy早解きで良順位に付けたがChallengeでだいぶ捲られてレートちょっと増。
http://community.topcoder.com/stat?c=problem_statement&pm=13987
http://community.topcoder.com/stat?c=problem_statement&pm=13988

問題

M個のメモリセルからなる計算機でN個のプログラムを任意の順で実行する。
各プログラムは実行中どのメモリセルにアクセスするかが与えられる。
各プログラムを実行する際、前にどのプログラムもアクセスしていないセルをk個アクセスする場合、k^2の時間がかかる。

プログラムの実行順を最適にした場合、かかる時間を最小化せよ。

解法

Nは50と大きいが、Mは20以下と小さい。
よって各セルがアクセス済みかどうかをBitmaskで表現してDPしていけば良い。

その他ダイクストラ法の要領でBitmaskを探索しても良い。
未アクセスセルの少ない順に行うのは危険で、"11100","01011","00111"のケースでは、最初に2番目または3番目のプログラムを選ばないと失敗する。

int cost[1<<21];

class OrderOfOperations {
	public:
	int minTime(vector <string> s) {
		int val[51]={},tot=0;
		int N=s.size();
		int M=s[0].size();
		int i,j,k;
		FOR(i,N) {
			FOR(j,M) if(s[i][j]=='1') val[i] |= 1<<j;
			tot |= val[i];
		}
		FOR(i,1<<M) cost[i]=1<<20;
		cost[0]=0;
		
		for(int mask=0;mask<tot;mask++) if(cost[mask]<1<<20) {
			int cur=__builtin_popcount(mask);
			FOR(i,N) {
				int mask2=mask | val[i];
				if(mask!=mask2) {
					int tar=__builtin_popcount(mask2);
					cost[mask2]=min(cost[mask2],cost[mask]+(tar-cur)*(tar-cur));
				}
			}
			
		}
		return cost[tot];
	}
}

まとめ

Mが20だからBitDP!と何も考えず実行したが無事成功。
こんな正答率低い問題とは思わなかった。