AtCoder ABC #142 : E - Get Everything

400ptでもいい気がするが。
https://atcoder.jp/contests/abc142/tasks/abc142_e

問題

N個の箱があり、それぞれ鍵がかかっている。
また、M種類のカギがあり、それぞれいくつかの箱を開けることができる。
カギは何度でも利用できる。

カギには価格が設定されている。
いくつかのカギを買い、全部の箱を開けるとき、総購入価格の最小値を求めよ。

解法

Nが小さいのでBitDPで解ける。
まず、M個のカギを開けられる箱の集合ごとに分けよう。
同じ箱の集合を開けられるなら、最安値の物だけ求めればよい。

price(mask) := maskに示すビットマスクに対する箱の集合を開けられる鍵の価格
dp(mask) := maskに示すビットマスクに対する箱の集合を開けられる鍵の価格の総和の最小値

とすると、dp(x|y) = min(dp(x) + price(y)) なので、x,yを総当たりしよう。

下記の解法は横着してO(4^N)だが、高速ゼータ変換とか使えばO(3^N)でも解ける。

int N,M;
ll mi[1<<12];
ll dp[1<<12];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,1<<N) mi[i]=dp[i]=1LL<<60;
	FOR(i,M) {
		int mask=0;
		cin>>x>>y;
		FOR(j,y) {
			cin>>r;
			mask |= 1<<(r-1);
		}
		mi[mask]=min(mi[mask],(ll)x);
	}
	
	dp[0]=0;
	FOR(x,1<<N) FOR(y,1<<N) dp[x|y]=min(dp[x|y],dp[x]+mi[y]);
	
	if(dp[(1<<N)-1]==1LL<<60) {
		cout<<-1<<endl;
	}
	else {
		cout<<dp[(1<<N)-1]<<endl;
	}
}

まとめ

500ptならNの上限は18でもいい気がするんだけどな。