数字の上限が珍しいな。
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"); } }
まとめ
ビットのまとめこみはともかく、それ以外はシンプルな問題。
「数えたくないなら適当に中に入れてしまえ」って単純でいいね。