すごく典型的な問題。
現代なら企業コンの 800 点問題とかに出そうな雰囲気だね。このころはまだあまり典型じゃなかったのかな。
問題概要
一直線上に 個の点 があってこの順に並んでいる。さらに左側に 、右側に がある。
- からスタートする
- 各座標を 1 回タッチしたあと、次にそのタッチから 秒後以降にもう一度タッチする必要がある
- 点すべてを二度タッチしてから座標 に最後に到達する
- 移動は座標 1 だけ移動するのに 1 秒かかる。
最小時間を求めよ。
制約
考えたこと
基本的には
- 最初の i 個の点まで二度タッチを終えた直後の状態 (地点 i-1 にいる) からスタートして
- 一度地点 j-1 まで行き、i まで引き返して、再び j-1 まで行く (ここできちんと二度タッチまで回収する)
というのを色んな i や j の区切り方について DP することになる。ものすごく典型的な区間ごとに分割していく DP
こういう DP はどうせ愚直にやると かかるが、それを累積 min を求めたり、セグ木に乗せたりしながら高速化する。まずは DP の遷移を書き出してみる。
2(x[ i - 1 ] - x[ j ]) >= T のとき
- chmin(dp[ i ], dp[ j ] + (x[ i - 1 ] - x[ j - 1 ]) + 2(x[ i - 1 ] - x[ j ]))
2(x[ i - 1 ] - x[ j ]) >= T のとき
- chmin(dp[ i ], dp[ j ] + (x[ i - 1 ] - x[ j - 1 ]) + T)
という感じになった。あとは、editorial によると累積 min でもできるっぽいけど、僕は以下の 2 つのセグ木を用意してやった。
- seg1: dp[ i ] - 2x[ i ] - x[ i - 1 ] の区間最小値
- seg2: dp[ i ] - x[ i - 1 ] の区間最小値
これで各ステップの更新を でできたので、全部で でできた (本当は でできるみたい)。
#include <iostream> #include <vector> #include <algorithm> using namespace std; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template<class Monoid> struct RMQ { const Monoid INF; int SIZE_R; vector<pair<Monoid,int> > dat; RMQ(int n, const Monoid &inf): INF(inf) { init(n); } void init(int n) { SIZE_R = 1; while (SIZE_R < n) SIZE_R *= 2; dat.assign(SIZE_R * 2, pair<Monoid,int>(INF, -1)); } /* set, a is 0-indexed */ void set(int a, const Monoid &v) { dat[a + SIZE_R] = make_pair(v, a); } void build() { for (int k = SIZE_R - 1; k > 0; --k) { dat[k] = min(dat[k*2], dat[k*2+1]); } } /* update, a is 0-indexed */ void update(int a, const Monoid &v) { int k = a + SIZE_R; dat[k] = make_pair(v, a); while (k >>= 1) dat[k] = min(dat[k*2], dat[k*2+1]); } /* get {min-value, min-index}, a and b are 0-indexed */ pair<Monoid,int> get(int a, int b) { pair<Monoid,int> vleft = make_pair(INF, -1), vright = make_pair(INF, -1); for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) { if (left & 1) vleft = min(vleft, dat[left++]); if (right & 1) vright = min(dat[--right], vright); } return min(vleft, vright); } inline Monoid operator [] (int a) { return dat[a + SIZE_R].first; } /* debug */ void print() { for (int i = 0; i < SIZE_R; ++i) { Monoid val = (*this)[i]; if (val < INF) cout << val; else cout << "INF"; if (i != SIZE_R-1) cout << ","; } cout << endl; } }; const long long INF = 1LL<<60; int N; long long T, E; vector<long long> x; long long solve() { vector<long long> dp(N+1, INF); RMQ<long long> r1(N+1, INF), r2(N+1, INF); dp[0] = 0; r1.update(0, -x[0] * 2); r2.update(0, 0); for (int i = 1; i <= N; ++i) { int ut = upper_bound(x.begin(), x.end(), x[i-1] - (T+1)/2) - x.begin() - 1; int lt = lower_bound(x.begin(), x.end(), x[i-1] - (T-1)/2) - x.begin(); chmin(ut, i-1); chmin(dp[i], r1.get(0, ut+1).first + x[i-1] * 3); chmin(dp[i], r2.get(lt, i).first + x[i-1] + T); r1.update(i, dp[i] - x[i] * 2 - x[i-1]); r2.update(i, dp[i] - x[i-1]); } return dp[N] + (E - x[N-1]); } int main() { cin >> N >> E >> T; x.resize(N); for (int i = 0; i < N; ++i) cin >> x[i]; cout << solve() << endl; }