SRM 539 DIV1 Easy Over9000Rocks

http://apps.topcoder.com/stat?c=problem_statement&pm=11855&rd=14731

回答

全列挙し、そのlowerとuppperを取り、それを[9001,∞]の範囲にする。
そのあとそれらをlowerでソートすると次のようになる。
この時、求めたいのは被覆している長さの和である。

これには、
現在の一番右端を持つ。
左がそれより大きかったら、それまでの領域から離れてるので、そこに移る。
右がそれより大きかったら、つまり今の領域からはみ出ている、ということなので、その分を結果に足して右端を移動する。
というふうにやる。

コメント

自分では解けなかった。
まずnが16な時点で指数に気づかないことが酷い。気づくのが当たり前。
この領域のやつは、極めて単純であって考えだせるレベルにも思えるが、
実際には全く思いつけなかった。考えをきちんとして、考え方を変えたり整理することが大事だ。

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <bitset>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(__typeof(o.begin()) it = o.begin; it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;

struct Over9000Rocks {
	int countPossibilities(vector <int> lb, vector <int> ub) {
		int n = lb.size();
		vpii v;
		rep(i, 1<<n){
			int l=0,u=0;
			rep(j,n)if(i&(1<<j))l+=lb[j],u+=ub[j];
			if(u>9000)v.pb(mp(max(9001, l),u));
		}
		sort(all(v));
		int r = 0;
		int R = 0;
		rep(i, v.size()) {
			if(R < v[i].first) {
				R = v[i].second;
				r += R - v[i].first + 1;
			}else if(R < v[i].second) {
				r += v[i].second - R;
				R = v[i].second;
			}
		}
		return r;
	}
};

追記: Rは-1に初期化しないと、0を位置として持つものに対応できない