SRM 205 DIV1 Hard LongPipes

問題 Editorial

問題

数列segmentsが与えられる。何個かを組み合わせて、和を特定の数desiredLengthにしたい。
組み合わせる数を最小にせよ。

• 1<=|segments|<=38
• 1<=segments[i]<=10^12
• 1<=desiredLength<=38*10^12

解答

Exact-Knapsack。半分全列挙する。
2^(N/2)*N/2でできる。
このやり方は最初は意味不明だったが、しっかり考えればわかった。

コメント

最初、このやり方の「同じ重さの所はまとめる」というところがよくわかってなくてFailedしてしまった。今はわかったと思う。良かった

コード

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll; typedef vector<long long> vl; typedef long double ld;

struct LongPipes {
	int fewestWelds(vector <string> segments, string desiredLength) {
		vl s; ll d;
		each(i, segments) {
			stringstream ss(*i);
			ld x; ss >> x;
			s.pb((ll)(x * 1000 + .5));
		}
		{
			stringstream ss(desiredLength);
			ld x; ss >> x;
			d = (ll)(x * 1000 + .5);
		}
		int n = s.size();
		int m = n/2;
		static pair<ll,int> q[1<<19]; int qn = 0;
		//まず半分の組み合わせを全部列挙して計算して
		rep(i, 1<<m) {
			ll w = 0; int p = 0;
			rep(j, m) if((i >> j)&1) w += s[j], p ++;
			q[qn++] = mp(w, -p);
		}
		//(Length, -Count) となっている
		//Lengthでソート
		sort(q, q+qn);
		//同じLengthなのにCountが違うやつは後の二分探索時に面倒なので、
		//ここでまとめて、同じLengthならCountを一番小さいやつに合わせる
		//ソート時の順序・forの順番に注意。ここでミスってFailedした
		//マイナス付けずにforを前からやってminでも同じだしそのほうが簡潔だね。普通のナップサックではvalueが大きいほうがいいからそれに合ってるだけ
		for(int i = qn-1; i > 0; i --) {
			if(q[i-1].first == q[i].first) {
				q[i-1].second = max(q[i-1].second, q[i].second);
			}
		}
		int r = INF;
		//残り半分を全列挙
		rep(i, 1<<(n-m)) {
			ll w = 0; int p = 0;
			rep(j, n-m) if((i >> j)&1) w += s[m+j], p ++;
			//二分探索なので、範囲にないなら最初にcontinueしておく
			//だけれども、今回はExactで最後に判定するので、これは必要なかったかな
			if(q[qn-1].first + w < d) continue;
			int l = 0, u = qn;
			//ちょうど長さが(d - w)になる、最初の半分の組み合わせを二分探索
			while(u - l > 1) {
				int mid = (l + u) / 2;
				if(q[mid].first + w <= d) l = mid;
				else u = mid;
			}
			//ちゃんと合ってるか？(見つけられたか？)
			if(q[l].first + w == d) {
				r = min(r, p + -q[l].second);
			}
		}
		return r == INF ? -1 : r-1;
	}
};