http://codeforces.com/contest/875/problem/E
ならし計算決めるアレです。
とりあえず距離kのとき行けるかどうかを判定する。
setでi番目まで処理し終わったとき、もう一人がどこにいるかを管理する。
i+1番目を考えて、もう一人の候補の座標としてありうるものを更新する。
一見O(N^2logN)だが、一度候補から外れると、もう候補となることはないのでならし計算量O(NlogN)となる。
結局全部値を持ってdpするだけですね。一見よくない戦略に見えて、すべての要素についてsetにぶち込まれる回数は定数倍回なのでならし計算量がうまくきまるという原理です。
よくよく考えてみるとstackやqueueを使う問題も同じです。単調性があってそのまま要素を末尾から足せばいいだけの場合はこれらを使ってO(N)とかにできます。
こういうパターンを僕は「愚直に値を持つdp」ということにします。
区間を扱う問題で単調性があったりするとこのパターンが利用できるかも?
dp高速化とかも愚直に全部値もってみて、初めてsegtreeなどデータ構造を使えることに気づくので発想は同じです。
ただしdp高速化は更新を高速にするだけで、データはすべて持ちます。「愚直に値をもつdp」はとりうる状態が限られていることを利用して計算量を減らします。
最初考察したとき二次元plotしたんですが、それは悪手でした。今回は2人を区別する必要がないからです。2つ値を持つからってxy-plotはさすがに頭が悪かった。使ってみて見通しよくなかったらすぐ切り替えましょう。
N=10^5だと貪欲だと思いがちなので、dpにも頭を働かせるようにしましょう。
int N, S1, S2; int A[MAX_N]; bool C(int m) { if(abs(S1 - S2) > m) return false; set<int> s; s.insert(S1); s.insert(S2); rep(i, 0, N) { while(!s.empty() && abs(*s.begin() - A[i]) > m) s.erase(s.begin()); while(!s.empty() && abs(*s.rbegin() - A[i]) > m) s.erase(*s.rbegin()); if(i != 0 && abs(A[i - 1] - A[i]) <= m) { s.insert(A[i - 1]); } if(s.empty()) return false; } return true; } void solve() { cin >> N >> S1 >> S2; rep(i, 0, N) cin >> A[i]; int lv = -1, rv = 1000000000; while(rv - lv > 1) { int m = (lv + rv) / 2; if(C(m)) rv = m; else lv = m; } cout << rv << "\n"; }
