【ABC408】F問題 - Athletic 考察から実装(c++)まで

AtCoderBeginnerContest408の解説＆感想です。
コンテストリンク

問題一覧

• 【ABC408】A問題 - Timeout　考察から実装(c++)まで
• 【ABC408】B問題 - Compression　考察から実装(c++)まで
• 【ABC408】C問題 - Not All Covered　考察から実装(c++)まで
• 【ABC408】D問題 - Flip to Gather　考察から実装(c++)まで
• 【ABC408】E問題 - Minimum OR Path　考察から実装(c++)まで
• 【ABC408】F問題 - Athletic　考察から実装(c++)まで <- イマココ

F問題 - Athletic

問題リンク

問題概要

$N$個の足場が並んでいて、$i$番目の足場の高さは$H_i$である。
高橋くんは、足場$i$にいる時、以下の条件を満たす次の足場$j$を好きに選べる

• $H_j \le H_i-D$かつ$1 \le |i-j| \le R$

行える移動の最大回数を求めよ。

制約

• $ 2 \le N \le 5 \times 10^5 $
• $ 1 \le D,R \le N $
• $H$は$(1,2,...,N)$の順列

考察

「移動」系はゴールから見ていくのはもはや典型。
今回は特定の場所がゴールになるわけではないけど、「それ以上動けない場所」をゴールとする。たとえば$H$の中で一番低い場所は、それ以上先には動けない。$D+1$番目に低い場所になって、ようやく移動先が出てくる。

より詰めると、今見ている場所$i$が$j$番目に低い場所だった時、移動できる可能性があるのは$j-D$番目に低いところ以前のどこかであって、$i \pm R$の範囲にある中で一番移動回数が多いところ。（もしそんなところがなければ、どこにも移動できない）

つまり、足場が低い順にその先の最大移動回数を確定させていけばいい。
「$i \pm R$の範囲にある中で一番移動回数が多いところをとる」というのは「特定の区間内の最大」なので、セグ木でできそう。
$j$番目に低い足場の最大移動回数を考える時に初めて、$j-D$番目に低い足場を、移動先候補セグ木に登場させる。（それまでは$j-D$番目のスコアは別の場所に保管しとく）

計算量は、足場を低い順に並び替えるのに$O(NlogN)$、小さい順に見ていくのが$O(N)$、セグ木の更新・取得がそれぞれ$O(logN)$なので、全体で$O(NlogN)$。

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll,ll>;
using vpll = vector<pll>;

const ll inf = 1000000000000000000LL;

//コンストラクタ　関数ポインタの部分は普通に関数名書くだけでOK
//SegmentTree<T>(vector<T>&,T (*f)(T,T),T ide)
//SegmentTree<T>(int n,T (*f)(T,T),T ide)
//関数
//Change(int,T)
//get(int,int)閉区間
template<typename T>
class SegmentTree{
    int n;
    T ident;
    vector<T> array;
    T (*op)(T,T);
public:
    SegmentTree(vector<T> &v,T (*f)(T,T),T ide){
        int sz = v.size();
        this->n = 1;
        while(n < sz) n *= 2;
        this->array = vector<T>(2*this->n-1,ide);
        this->ident = ide;
        this->op = f;
        for(int i=0;i<sz;i++) change(i,v[i]);
    }
    SegmentTree(int a,T (*f)(T,T),T ide){
        this->n = 1;
        while(n < a) n*= 2;
        this->array = vector<T>(2*this->n-1,ide);
        this->ident = ide;
        this->op = f;
    }
    SegmentTree(){}
    int l_child(int i){ return i*2+1; }
    int r_child(int i){ return i*2+2; }
    int get_parent(int i){ return (i%2 == 0) ? (i/2-1):(i/2); }
    void change(int i,T v){
        int ind = this->array.size()/2+i;
        this->array[ind] = v;
        int parent = get_parent(ind);
        while(parent != -1){
            this->array[parent] = op(this->array[l_child(parent)],this->array[r_child(parent)]);
            parent = get_parent(parent); 
        }
    }
    T get(int l,int r,int k=0,int nowL=-1,int nowR=-1){
        if(k == 0){
            nowL = 0;
            nowR = this->array.size()/2;
        }
        if(r < nowL || nowR < l) return this->ident;
        if(l <= nowL && nowR <= r) return this->array[k];
        T vl = get(l,r,l_child(k),nowL,(nowL+nowR)/2);
        T vr = get(l,r,r_child(k),(nowL+nowR)/2+1,nowR);
        return op(vl,vr);
    }
};

int main(void){
    //入力
    ll N,D,R;
    cin>>N>>D>>R;
    
    vll H(N);
    for(int i=0;i<N;i++) cin>>H[i];
    
    
    //足場の低い順にインデックスを並び替え
    vll idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](ll a, ll b){ return H[a] < H[b]; });
    
    //移動先の足場候補たち
    SegmentTree<ll> st(N, [](ll a, ll b){ return max(a,b); }, -inf);
    
    //各足場から動ける最大移動回数
    vll ans(N, 0);
    
    for(int i=0;i<N;i++){
        //i-D番目に低い場所を候補セグ木に登場させる
        if(i >= D) st.change(idx[i-D], ans[idx[i-D]]);
        //プラマイRの中で最大の移動回数
        ll ma = st.get(max(0LL, idx[i]-R), min(N-1, idx[i]+R));
        ans[idx[i]] = ma==-inf?0:ma+1;
    }
    //各足場から動ける最大移動回数の中で、最大が答え
    cout<<*max_element(ans.begin(), ans.end())<<endl;
    
    return 0;
}