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; }