2020-01-30

Educational Codeforces Round 81 E. Permutation Separation (R2200)

Codeforces 順列を題材とした問題操作データ構造セグメント木遅延評価 StarrySkyTree 差分更新ある量を固定して考える in-place DP DP 最小コスト CodeforcesR2200 EducationalCodeforces 遅延評価セグメント木

これを思い出して迷走してしまった (それでも通る解法には至ったけど恐ろしく煩雑なものとなってしまった)。

drken1215.hatenablog.com

なぜもっとシンプルに考えられなかったのか...

問題へのリンク

問題概要

$1, 2, \dots, N$ の順列 $p_{1}, p_{2}, \dots, p_{N}$ と、各要素 $1, 2, \dots, N$ を動かすのに必要なコスト $a_{1}, a_{2}, \dots, a_{N}$ が与えられる ( $a_{i}$ は index $i$ の要素を動かすコストではなく、要素 $i$ を動かすコスト)。

今、順列を左右に分ける。左右はそれぞれ empty ではないようにする。このとき、左の要素を選んで右に動かしたり、右の要素を選んで左に動かしたりすることで、「左側のどの要素も右側のどの要素よりも小さい」という状態を達成したい。

それに要する最小コストを求めよ。

制約

$2 \le N \le 2 \times 10^{5}$

解法

0-indexed にして考える。
まず目的を達成した状態がどうなっているのかを考えてみる。操作を終えた段階で、左側を $k$ 個、右側を $N-k$ 個としたとき、

左側の要素は $0, 1, \dots, k-1$
右側の要素は $k, k+1, \dots, N-1$

となっているはずである。よって

最初に、左側に何個がある状態にするか
最終状態で、左側に何個がある状態にするか

を決めると、コストが一意に決まることになる。こういうのはどちらかを固定して考えて、それを動かす時の遷移の部分を高速化できないかを考えるとよさそう。

具体例で

具体例として N = 5、(3, 4, 0, 1, 2) の場合を見てみる。最初は (実際は無効だけど)、「最初の段階で (0個、7個) に分ける場合」を考えてみる。

最後に (0, 5) にするコスト： 0
最後に (1, 4) にするコスト： a[0]
最後に (2, 3) にするコスト： a[0] + a[1]
最後に (3, 2) にするコスト： a[0] + a[1] + a[2]
最後に (4, 1) にするコスト： a[0] + a[1] + a[2] + a[3]
最後に (5, 0) にするコスト： a[0] + a[1] + a[2] + a[3] + a[4]

ということになる。これに対して「最初の段階で (1個、6 個) に分ける」という風になると、次のように変化する。「3」が左に移ることから次のように変化する。

最後に (0, 5) にするコスト： a[3] (3 を右に移す)
最後に (1, 4) にするコスト： a[0] + a[3]
最後に (2, 3) にするコスト： a[0] + a[1] + a[3]
最後に (3, 2) にするコスト： a[0] + a[1] + a[2]　(3 を移す必要がなくなる)
最後に (4, 1) にするコスト： a[0] + a[1] + a[2]
最後に (5, 0) にするコスト： a[0] + a[1] + a[2] + a[4]

この変化を見ると、最初の 3 つについては a[3] を加算し、残りは a[3] を減算していることがわかる。つまり

区間加算
範囲最小値

がわかればよいので、Starry Sky 木 (遅延評価セグメント木で実現できる) がちょうどいい。in-place DP / インライン DP の一種ともみなせそう。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
// Segment Tree
template<class Monoid, class Action> struct SegTree {
    using FuncMonoid = function< Monoid(Monoid, Monoid) >;
    using FuncAction = function< void(Monoid&, Action) >;
    using FuncLazy = function< void(Action&, Action) >;
    FuncMonoid FM;
    FuncAction FA;
    FuncLazy FL;
    Monoid UNITY_MONOID;
    Action UNITY_LAZY;
    int SIZE, HEIGHT;
    vector<Monoid> dat;
    vector<Action> lazy;
    
    SegTree() { }
    SegTree(int n, const FuncMonoid fm, const FuncAction fa, const FuncLazy fl,
            const Monoid &unity_monoid, const Action &unity_lazy)
    : FM(fm), FA(fa), FL(fl), UNITY_MONOID(unity_monoid), UNITY_LAZY(unity_lazy) {
        SIZE = 1; HEIGHT = 0;
        while (SIZE < n) SIZE <<= 1, ++HEIGHT;
        dat.assign(SIZE * 2, UNITY_MONOID);
        lazy.assign(SIZE * 2, UNITY_LAZY);
    }
    void init(int n, const FuncMonoid fm, const FuncAction fa, const FuncLazy fl,
              const Monoid &unity_monoid, const Action &unity_lazy) {
        FM = fm; FA = fa; FL = fl;
        UNITY_MONOID = unity_monoid; UNITY_LAZY = unity_lazy;
        SIZE = 1; HEIGHT = 0;
        while (SIZE < n) SIZE <<= 1, ++HEIGHT;
        dat.assign(SIZE * 2, UNITY_MONOID);
        lazy.assign(SIZE * 2, UNITY_LAZY);
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE] = v; }
    void build() {
        for (int k = SIZE - 1; k > 0; --k)
            dat[k] = FM(dat[k*2], dat[k*2+1]);
    }
    
    /* update [a, b) */
    inline void evaluate(int k) {
        if (lazy[k] == UNITY_LAZY) return;
        if (k < SIZE) FL(lazy[k*2], lazy[k]), FL(lazy[k*2+1], lazy[k]);
        FA(dat[k], lazy[k]);
        lazy[k] = UNITY_LAZY;
    }
    inline void update(int a, int b, const Action &v, int k, int l, int r) {
        evaluate(k);
        if (a <= l && r <= b)  FL(lazy[k], v), evaluate(k);
        else if (a < r && l < b) {
            update(a, b, v, k*2, l, (l+r)>>1), update(a, b, v, k*2+1, (l+r)>>1, r);
            dat[k] = FM(dat[k*2], dat[k*2+1]);
        }
    }
 
    inline void update(int a, int b, const Action &v) { update(a, b, v, 1, 0, SIZE); }
   
    
    /* get [a, b) */
    inline Monoid get(int a, int b, int k, int l, int r) {
        evaluate(k);
        if (a <= l && r <= b)
            return dat[k];
        else if (a < r && l < b)
            return FM(get(a, b, k*2, l, (l+r)>>1), get(a, b, k*2+1, (l+r)>>1, r));
        else
            return UNITY_MONOID;
    }
    inline Monoid get(int a, int b) { return get(a, b, 1, 0, SIZE); }
    inline Monoid operator [] (int a) { return get(a, a+1); }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE; ++i) { cout << (*this)[i]; if (i != SIZE) cout << ","; }
        cout << endl;
    }
};
const long long INF = 1LL<<55;
 
int N;
vector<int> p;
vector<long long> a;
 
long long solve() {
    long long res = min(a[p[0]], a[p.back()]);
 
    auto fm = [](long long a, long long b) { return min(a, b); };
    auto fa = [](long long &a, long long d) { a += d; };
    auto fl = [](long long &d, long long e) { d += e; };
    SegTree<long long, long long> seg(N+10, fm, fa, fl, INF, 0);
 
    vector<long long> sum(N+1, 0);
    for (int i = 0; i < N; ++i) sum[i+1] = sum[i] + a[i];
    for (int i = 0; i <= N; ++i) seg.set(i, sum[i]);
    seg.build();
       
    for (int i = 0; i < N-1; ++i) {
        seg.update(0, p[i]+1, a[p[i]]);
        seg.update(p[i]+1, N+1, -a[p[i]]);
        chmin(res, seg.get(0, N+1));
    }
    return res;
}
 
int main() {
    while (scanf("%d", &N) != EOF) {
        p.resize(N);
        a.resize(N);
        for (int i = 0; i < N; ++i) scanf("%d", &p[i]), --p[i];
        for (int i = 0; i < N; ++i) scanf("%lld", &a[p[i]]);
        printf("%lld\n", solve());
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Educational Codeforces Round 81 E. Permutation Separation (R2200)

問題概要

制約

解法

具体例で