kmjp's blog

競技プログラミング参加記です

Codeforces #207 Div1 D. Bags and Coins

数字の上限が珍しいな。
http://codeforces.com/contest/356/problem/D

問題

N個の袋があり、各袋には合計でA[i]個のコインが入っている。
また、全体ではS個のコインがある。
袋の中に他の袋を入れても良いため、sum(A)がSより多い場合可能性もある。

上記記述を満たすような袋の包含関係が存在するなら、それを答えよ。

解法

より多くのコインが入る袋の中に、少ないコインが入る袋を入れた場合、少ない方のコインは2重カウントを避けるため、合計のSを数えるときに含めなくてよい。
そうすると結局Aの部分集合のうち和がSになるものを求める単純なナップサック問題となる。

合計のSを数えるために含めたくないものは、より大きな袋に入れればよいことになる。
よって、袋をコイン数の大きい順にソートすることを考える。
Sに含めたいならその袋を一番外側、そうでなければ1つ大きな袋に入れてしまえばよい。

あとは単純なナップサック問題
最初のi個の袋のうちいくつかを集めて、コインj個分の袋の集合を作れるかどうかを、T(i,j)=0 or 1で表現する。
T(i,j)=T(i-1,j) or T(i-1,j-A[i])という単純な関係にある。
Tを愚直にDPするとO(NS)かかるので間に合わないが、0/1の2値しか取らない関数なのでビットをまとめこめばT(i,j)の有無が定まる。

最終的にT(N,S)=1なら条件を満たす袋の包含関係が存在する。
あとはDPを巻き戻して、包含関係を求めるだけ。

vector<int> C[70010];
int first[2200*64];
unsigned long long bm[2][2005];
int istop[70010];
int N,S,A[70005];
pair<int,int> P[70010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]>S) return _P("-1\n");
		P[i]=make_pair(-A[i],i);
	}
	sort(P,P+N);
	
	// max val must be used
	bm[1][0]=1;
	for(i=1;i<N;i++) {
		FOR(j,2000) bm[0][j]=bm[1][j];
		FOR(j,2000) {
			x=A[P[i].second]/50,y=A[P[i].second]%50;
			if(j+x>=2000) break;
			bm[1][j+x]|=bm[0][j]<<y;
			bm[1][j+x+1]|=(bm[0][j]>>(50-y)) & ((1ULL<<50)-1);
		}
		FOR(j,2000) {
			unsigned long long mm=bm[1][j]^bm[0][j];
			if(mm) FOR(x,50) if(mm&(1ULL<<x)) first[j*50+x]=P[i].second+1;
		}
	}
	
	y=S-A[P[0].second];
	if(y>0 && first[y]==0) return _P("-1\n");
	while(y>0) {
		x=first[y]-1;
		istop[x]=1;
		y-=A[x];
	}
	
	istop[P[0].second]=1;
	x=P[0].second;
	
	FOR(i,N) if(!istop[P[i].second]) {
		C[x].push_back(P[i].second);
		A[x]-=A[P[i].second];
		if(A[x]<0) return _P("-1\n");
		x=P[i].second;
	}
	
	FOR(i,N) {
		_P("%d %d",A[i],C[i].size());
		FOR(j,C[i].size()) _P(" %d",C[i][j]+1);
		_P("\n");
	}
}

まとめ

ビットのまとめこみはともかく、それ以外はシンプルな問題。
「数えたくないなら適当に中に入れてしまえ」って単純でいいね。