Twitterで書いた、作った問題の解答

https://twitter.com/anta_prg/status/281025745768288256

問題

今位置0に居て、ある位置[K,K+M-1](K,M≦10^10)の範囲に止まる必要がある。
カードがN(≦40)枚、それぞれに数値とコスト(≦10^9)が書かれていて{捨てる・数値だけ進む}ことができる。
コストを最小化せよ。止まれない場合は-1を返せ

解答(想定解, 合っているかは不明)

半分全列挙する。
半分全列挙した片方(移動距離, コスト)をRangeMinimumQueryに入れる。
もう半分の列挙に対して、[K - 移動距離, K - 移動距離 + M)の範囲(をlower_bound,upper_boundでインデックスにする)でRMQをクエリし、その区間最小+コストをminする

コメント

初めて問題を作ってみた。
半分の指数の問題をhttp://d.hatena.ne.jp/anta1/20121218/1355826246でやって、それでそういう問題を作ってみたいなと思って作ってみた。RMQ使えるじゃん、と思ってやってみた。
もっと簡単な解法もあるかもしれないね。
実際解答が合っているかは不明だが良い感じだと思う。
なんとなく組み合わせが簡単なので、恐らく過去に同じような問題が出されているかもしれない。
これからも理解のために、やった問題からアイデアを得て問題をどんどん作って行きたい。このブログの直前を見れば答えわかっちゃう、ということになるかもしれないけれど。
問題作るのは楽しいしね。でもテストケースとか作ってないし大変なことはしてないわけだからなーとか

コード

#include <vector>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi;
typedef long long ll;  typedef pair<long long,long long> pll;

struct RMQ {
	int n;
	ll d[2097152];
	void init(int nmin) {
		for(n = 1; n < nmin; n *= 2);
		memset(d, INF, 2 * n);
	}
	void update(int i, ll x) {
		d[n+i] = x;
		for(int k = (n+i)/2; k > 0; k >>= 1) 
			d[k] = min(d[k * 2], d[k * 2 + 1]);
	}
	ll get(int l, int r) const {
		ll m = INFL;
		for(; l && l + (l&-l) <= r; l += l&-l)
			m = min(m, d[(n+l) / (l&-l)]);
		for(; l < r; r -= r&-r)
			m = min(m, d[(n+r) / (r&-r) - 1]);
		return m;
	}
};

RMQ rmq;
ll minCost(vi xs, vi costs, ll K, ll M) {
	int n = xs.size();
	int m = n/2;
	vector<pll> v;
	rep(i, 1<<m) {
		ll cost = 0, advance = 0;
		rep(j, m) if((i >> j) & 1) advance += xs[j], cost += costs[j];
		v.pb(mp(advance, cost));
	}
	sort(all(v));
	rmq.init(v.size());
	rep(i, v.size()) rmq.update(i, v[i].second);
	int m2 = n - m;
	ll r = INFL;
	rep(i, 1<<m2) {
		ll cost = 0, advance = 0;
		rep(j, m2) if((i >> j) & 1) advance += xs[m+j], cost += costs[m+j];
		int l = lower_bound(all(v), mp(K     - advance, -INFL)) - v.begin();
		int u = upper_bound(all(v), mp(K + M - advance, -INFL)) - v.begin();
		cost += rmq.get(l, u);
		r = min(r, cost);
	}
	return r == INFL ? -1 : r;
}