Last Stone Weight II [LeetCode 1049]

https://leetcode.com/contest/weekly-contest-137/problems/last-stone-weight-ii/

N個の石があり、それぞれの重さがわかっている。
2つの石を選んでぶつけるという操作をできなくなるまで行う。
ぶつけると、

• 同じ重さであれば、2つとも消滅
• 差があれば、差分の石が残る

という結果になる。
最終的に残る石の重さとして最小のものを答えよ。
（残らなければ0を答える）

1≦N≦30
1≦重さ≦1000

前提知識

• 半分全列挙

解説

https://leetcode.com/contest/weekly-contest-137/submissions/detail/229837009/

今回の問題はある問題に帰着できる。
石を2グループに分けたときにそれぞれのグループの総和の差が最終的に残る石の重さになる。
よって、石を2グループに分けたときにそれぞれのグループの総和の差を最小化すればいい。
自分はもちろん未証明。
　
あとは、これをどう実現するかであるが、制約を見ると、半分全列挙が使えそうだ。
2グループで作れる総和を計算する。
グループ0で総和aを作れたとする。ここからグループ1から総和bを最適に取ってくることを考えると、
全体をtotとすると、a + b = tot/2になるべく近いほうがいい。
よって、b = tot/2-a付近の数が答えになりうるということ。
よって、グループ0で作れる総和aは全探索することにして、
グループ1での総和は二分探索をしてtot/2-a付近の数だけ検証する。
イメージし辛いなら、三分探索をしても大丈夫だ。

class Solution {
public:
	pair<set<int>, int> f(vector<int> v) {
		int n = v.size();
		set<int> s;
		rep(msk, 0, 1 << n) {
			int tot = 0;
			rep(i, 0, n) if (msk & (1 << i)) tot += v[i];
			s.insert(tot);
		}
		int sm = 0;
		rep(i, 0, n) sm += v[i];
		return { s, sm };
	}
	int lastStoneWeightII(vector<int>& stones) {
		int n = stones.size();

		vector<int> v[2];
		rep(i, 0, n) v[i % 2].push_back(stones[i]);

		auto p0 = f(v[0]);
		auto p1 = f(v[1]);
		int tot = p0.second + p1.second;

		int ans = inf;
		fore(x, p0.first) {
			int a = x;

			int opt = tot / 2 - a;
			auto optite = p1.first.lower_bound(opt);

			auto ite = optite;
			ite--;
			rep(i, 0, 5) {
				int b = *ite;
				
				int sm1 = a + b;
				int sm2 = tot - sm1;
				int d = abs(sm1 - sm2);
				chmin(ans, d);
				if (ite == p1.first.begin()) break;
				ite--;
			}

			ite = optite;
			rep(i, 0, 5) {
				if (ite == p1.first.end()) break;

				int b = *ite;

				int sm1 = a + b;
				int sm2 = tot - sm1;
				int d = abs(sm1 - sm2);
				chmin(ans, d);
				ite++;
			}
		}

		return ans;
	}
};