問題

問題概要

要素数 $n$ の配列 $a$ が与えられる。いま、配列のindexを1つ指しているポインタ $p$ があり(はじめは $p=0$ )、そのポインタに対して以下の3つの操作ができる：

$p$ を1増やす
$p$ を1減らす
$p$ が指している位置の要素を削除し、 $p$ は1つ前の要素か1つ後の要素を指すようにどちらかを選ぶ

この3番目で行う削除の順番を、non-decreasing orderで行うために必要な操作の回数の最小値を求めよ。

$1 \le n \le 10^5$
$1 \le a_i \le 10^9$

アイデア

まず、配列 $a$ の中に同じ要素がなければ、削除の順番は一意に決定するので操作は貪欲にしていけば良いことになる。この操作の一つ一つを本当にシミュレーションするとなると回数は $O(n^2)$ 回かかるので当然間に合わない(ただ、次に行くべき位置が決まってるので、移動は省けそうに見える)。

もし、 $a$ も中に同じ要素がある場合は、要素の値でグループ分けをして削除の処理をしていくことになる。この時、グループ間の削除の順番は入れ替えることが出来ないが、グループ内であれば削除の順番を入れ替えても良いことになる。

今、 $x$ 未満の値の削除が終了し、 $x$ の値のグループを削除していくという状況を考えよう。さて、上の3つの操作を見比べてみると、 $p$ が値 $x$ の位置を指しているときにするべきことは3番目の操作しかありえないということが分かる(1番目の操作や2番目の操作もその中に含んでいるし、その後の状況が良い)。ということを考えれば、このグループ内で最後に削除されることになるのは配列の左端の $x$ または右端の $x$ のどちらかということになる。

よって、次のようなDPが考えられる：

dp[x][0/1] = 値x以下は全て削除完了し、値xのグループに関しては最後に削除したのが左端(0)/右端(1)のときの(削除を伴わない移動)操作回数の最小値

xの部分については座圧することで、 $n$ 種類になる。小さい方から $i$ 番目の値であると考えることにすると、このdpを計算するのに必要なのはdp[i-1][0/1]ということになる。

dp[i][0]を計算したいと思った場合には、dp[i-1][0]とdp[i-1][1]のそれぞれからの遷移を考えるわけだが、どちらについてもやるべき最適な動作は共通で、値xの右端まで(値を削除しながら)ポインタを進めていき、折り返して左端まで行くという操作になる。その間で必要になる操作の回数はその区間にある $x$ より大きい値の個数に一致することになる。これは、dpを進めていくと同時にBITを更新することでその個数を数えることができ、全体としては $O(n log n)$ で実現出来る。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

struct BIT{
    // [1,n]
    int n; vector<ll> bit;
    // 初期化
    BIT(int _n){
        n = _n;
        bit = vector<ll>(n+1,0);
    }
    // sum of [1,i]
    ll sum(int i){
        ll s = 0;
        while(i>0){
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    // add x in i-th element
    void add(int i, ll x){
        while(i<=n){
            bit[i] += x;
            i += i & -i;
        }
    }

    ll query(int l, int r)
    {
        if(r<l) swap(l,r);
        return sum(r)-sum(l-1);
    }
};

vector<int> comp(const vector<int> &a)
{
    vector<int> s(a);
    sort(all(s));
    s.erase(unique(all(s)),s.end());

    int n = a.size();
    vector<int> ret(n);
    rep(i,n) ret[i] = lower_bound(all(s),a[i])-s.begin();

    return ret;
}

const int N = 100010;
const ll INF = LLONG_MAX/3;
vector<int> pos[N];

int main()
{
    int n;
    cin >>n;
    vector<int> a(n+1,-1);
    rep(i,n) cin >>a[i+1];

    a = comp(a);
    rep(i,n+1) pos[a[i]].pb(i);
    int M = *max_element(all(a));

    BIT bit(n+1);
    for(int i=1; i<=n; ++i) bit.add(i,1);

    ll dp[2]={};
    for(int i=1; i<=M; ++i)
    {
        for(int j:pos[i]) bit.add(j,-1);

        ll nx[2]={INF,INF};
        int p[2] = {pos[i-1].front(), pos[i-1].back()};
        int nxp[2] = {pos[i].front(), pos[i].back()};

        rep(j,2)rep(k,2)
        {
            // 移動ルート: p[j] -> nxp[k^1] -> nxp[k]
            nx[k] = min(nx[k], dp[j]+bit.query(p[j],nxp[k^1])+bit.query(nxp[k^1],nxp[k]));
        }

        rep(j,2) dp[j] = nx[j];
    }

    cout << min(dp[0],dp[1])+n << endl;
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

CS Academy #44 - Array Elimination

問題

問題概要

アイデア

実装(C++)