ARC060 E 高橋君とホテル ダブリングの気持ちになる
ARC060 E 高橋君とホテル
問題概要
リンク参照
考察
- 制約を見ると二分探索が必要な雰囲気を醸し出しているので意識する
- 一番初めに考えたのが,今いるホテルからL日以内に行ける次のホテルを二分探索で求めていくこと.でもこれはL=1とかだと確実に破滅するのでこういう考察はダメっぽい
- ん~困った,(ここで解説を見る)・・・・ダブリング(未知の言葉)
- そこで,こちらのブログを見に行く
- なるほど,今回だと今いる頂点からN回移動したときのホテルが知りたいみたいな感じに思えるとダブリングが見えてきそうなことが分かってきた
- このブログ,すごくわかりやすくて理解しやすかった(あとは類題解いて練習しておきたい)
- 700点精進,ためにはなるけど難しい・・・・
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define llong long long #define pb(a) push_back(a) using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef tuple<ll, ll, ll, ll> lltpl; /******************************************************************************************/ const ll MOD = 1e9 + 7; template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); } template<typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) { t = v; } template<typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) { for (auto& e : t) fill_v(e, v); } int dp[20][100005];//dp[i][j]:=j番目の頂点から2^i日以内に到達できる最右のホテル int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector<int> x(n); for (int i = 0; i < n; i++) { cin >> x[i]; } int L, Q; cin >> L >> Q; for (int i = 0; i < n; i++) { dp[0][i] = upper_bound(x.begin(), x.end(), x[i] + L) - x.begin() - 1; } for (int i = 0; i < 19; i++) { for (int j = 0; j < n; j++) { dp[i + 1][j] = dp[i][dp[i][j]]; } } for (int i = 0; i < Q; i++) { int a, b; cin >> a >> b; a--; b--; if (a > b) { swap(a, b); } int ans = 0; for (int i = 19; i >= 0; i--) { if (dp[i][a] < b) { a = dp[i][a]; ans += 1 << i; } } ans++; cout << ans << endl; } return 0; }