yukicoder : No.2161 Black Market

これは典型かな…。
https://yukicoder.me/problems/no/2161

問題

N個のカードがあり、それぞれコストと価値が設定されている。
カードからK枚以下を選ぶとき、コストの総和がL以下で価値の総和がP以上となるのは何通りか。

解法

Nの上限が34と小さいので、半分全列挙しよう。
カード前半半分における選び方及び後半半分における選び方を、それぞれコスト順に並べておく。
また、後者においては価値の総和を座標圧縮しておく。

前者に対し、コストの大きい順に処理することを考える。
もし前半半分のコスト総和がCの時、後半半分の総和はL-C以下なら選択可能である。
また前半半分の価値の総和がDの時、後半半分の総和はP-D以上なら選択可能である。
よってそのような後半半分のカードに対し、カード枚数ごとに準備したBITを用い、総和が(P-D)以上になる組み合わせの個数を求めよう。

int N,K;
ll L,P,A[55],B[55];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt[18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>L>>P;
	FOR(i,N) cin>>A[i]>>B[i];
	int X=N/2;
	int Y=N-X;
	int mask;
	vector<ll> pat={-1LL};
	vector<pair<ll,pair<int,ll>>> C,D;
	FOR(mask,1<<X) {
		ll As=0,Bs=0;
		FOR(i,X) if(mask&(1<<i)) As+=A[i],Bs+=B[i];
		C.push_back({As,{__builtin_popcount(mask),Bs}});
		pat.push_back(Bs);
		pat.push_back(P-Bs);
	}
	FOR(mask,1<<Y) {
		ll As=0,Bs=0;
		FOR(i,Y) if(mask&(1<<i)) As+=A[i+X],Bs+=B[i+X];
		D.push_back({As,{__builtin_popcount(mask),Bs}});
		pat.push_back(Bs);
	}
	sort(ALL(pat));
	sort(ALL(C));
	reverse(ALL(C));
	sort(ALL(D));
	reverse(ALL(D));
	ll ret=0;
	FORR2(a,b,C) {
		if(a>L) continue;
		if(b.first>K) continue;
		while(D.size()&&D.back().first+a<=L) {
			x=lower_bound(ALL(pat),D.back().second.second)-pat.begin();
			bt[D.back().second.first].add(x,1);
			D.pop_back();
		}
		x=lower_bound(ALL(pat),P-b.second)-pat.begin();
		FOR(i,18) if(b.first+i<=K) ret+=bt[i]((1<<20)-1)-bt[i](x-1);
	}
	cout<<ret<<endl;
}

まとめ

やることは難しくないけど、ちょっと面倒くさい。