RCC 2014 Warmup - Div1 B. Cunning Gena

計算量見積もりミスで失敗。
http://codeforces.com/contest/418/problem/B

問題

M問の問題があり、N人の生徒を使って全問解きたい。

各生徒には、依頼にかかる費用X[i]、必要なモニタ数K[i]、解ける問題の一覧がパラメータとして与えられる。
各生徒には必要なモニタ数を準備しておけば、X[i]払うことで生徒が解ける全問題を解いてもらうことができる。

モニタ１台購入する費用はBである。
全問正解するのに必要な最小費用を答えよ。

解法

モニタにかかる費用は、依頼した生徒のうち必要とするモニタ台数の最大値で決まる。
そこで、生徒をモニタ台数の少ない順にソートし、問題の解答済み/未回答をbitmaskで保持しながらDPすればよい。
j番目までの生徒で全問正解できたなら、そのコストは依頼した生徒kのX[k]の和とK[j]*Bの和となる。

計算量はソートでO(N*logN)、bitDPでO(N*2^M)だが、大抵後者が大きいのでO(N*2^M)。

int N,M;
ll B;
ll X[201],K[201];
int MA[201];
vector<ll> KK;
ll dpdp[2][1<<20];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>B;
	vector<pair<int,int> > VV;
	FOR(i,N) {
		cin>>X[i]>>K[i]>>k;
		VV.push_back(make_pair(K[i],i));
		FOR(x,k) cin>>y, MA[i] |= 1<<(y-1);
	}
	
	sort(VV.begin(),VV.end());
	
	ll mi=1LL<<62;
	FOR(x,1<<M) dpdp[0][x]=dpdp[1][x]=1LL<<62;
	dpdp[0][0]=dpdp[1][0]=0;
	
	FOR(i,N) {
		FOR(x,1<<M) dpdp[1][x|MA[VV[i].second]] = min(dpdp[1][x|MA[VV[i].second]],dpdp[0][x]+X[VV[i].second]);
		mi=min(mi,dpdp[1][(1<<M)-1]+VV[i].first*B);
		memmove(dpdp[0],dpdp[1],sizeof(dpdp[0]));
	}
	if(mi>=1LL<<62) _P("-1\n");
	else cout << mi << endl;
}

まとめ

本番はO(N^2*2^M)でTLEしてしまった。