CSAcademy Round #79 : E. Smallest Subsets

シンプルな問題設定でよかった。
https://csacademy.com/contest/round-79/task/smallest-subsets/

問題

N要素の整数のmultisetが与えられる。
べき集合2^N通りを考えたとき、要素の総和を昇順に並べた際先頭K個を答えよ。

解法

解の候補を最大K個保ちつつDPする。
まず、負の数が厄介なのでこれを消そう。
xをある正の数とする。

元の集合に-xがあったとき、これをべき集合の1要素に含むか含まないかを考えるわけだが、言い方を変えると先にxを引いて(-xを足して)おき、改めてxを足すかたさないか2通り考えるのと組み合わせの数としては一緒である。
こう考えると、結局全要素に関し非負の値を足すかたさないかを考える問題に置き換えることができる。
この状態で、全要素を昇順に並べ替えて処理していく。

multisetで[途中までのべき集合の要素に含む数の総和, 処理した要素数]の集合を管理しよう。
前者の小さい順に処理し、解に加えていく。
元の要素が昇順なので、途中から「以降の要素は何を加えても先頭K個に入りえない」という状況が出てくるので、そのようなものはmultisetから外していく。

int N,K;
vector<ll> V;
multiset<ll> R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	V.resize(N);
	ll dif=0;
	FOR(i,N) {
		cin>>V[i];
		if(V[i]<0) {
			dif+=V[i];
			V[i]=-V[i];
		}
	}
	sort(ALL(V));
	
	multiset<pair<ll,int>> M;
	R.insert(0);
	M.insert({0,0});
	while(M.size()) {
		auto a=*M.begin();
		M.erase(M.begin());
		
		if(R.size()>=K && *R.rbegin()<=a.first) break;
		if(a.second<N) {
			R.insert(a.first+V[a.second]);
			if(R.size()>K) R.erase(--R.end());
			if(R.size()<K || a.first+V[a.second]<*R.rbegin()) {
				M.insert({a.first+V[a.second],a.second+1});
				M.insert({a.first,a.second+1});
			}
		}
		
	}
	
	FORR(r,R) cout<<dif+r<<endl;
	
	
	
}

まとめ

落ち着けばさほど難しくないのだけど、パッとは思いつかないよね。