AtCoder ARC 085 F - NRE (赤色, 1000 点)

実家なんだと思うけど...意外とはまりやすい問題な気 がします

問題へのリンク

問題概要

マスの値が最初はすべて 0 に固定されている。以下の 種類の操作の中からいくつか選んで操作する。その結果と、 とのハミング距離の最小値を求めよ。

• 番目の操作では、区間 [ ] の値をすべて 1 に置き換える

制約

• 

考えたこと

この手の問題、整理して考えるのが大変。区間に対して順に操作する問題というのは、多くの場合、以下のような形の DP でできる。

• dp[ i ] := 区間 [0, i) までについて、その区間内に終点をもつ区間についてはどのように操作するかを決定したときの、区間 [0, i) についての最小値

この手の DP に落とすには、通常、区間の終端でソートしておく。それで上手くいくことが多い。でも、区間の始点でソートした方がよい問題もある。この両者を上手に区別する方法ってなにかないものかな...

それとも、終端ソートでも上手くいくのかな...

恐れずに二次元にする

この手の DP は、多くの場合

• chmin( dp[ i ], dp[ j ] + f(i, j) )

みたいな形になって、このままだと なのでセグ木とかで高速化する...みたいなのが多い気がする。でももう 1 つパターンがある。それが in-place DP とよばれているやつだ！！in-place DP では、

• dp[ i ][ j ] := 区間 [0, i) 内に始点をもつ区間については操作をどうするかを決定したときの、区間 [i, j) については〜〜〜な状態 (そして j マス目で状態が変わる) となっているようなものについての、最小値

みたいな DP を立てて、添字 i に関する変化は i -> i + 1 のみを考えればよく、それにともなう j の部分の変化の大部分が実は in-place にできて、それによって計算量が落とせるというタイプの DP。今回まさにそういう DP みたい。

結局の DP

• dp[ i ][ j ] := 区間 [0, i) 内に始点をもつ区間については操作をどのようにするかを決定して、区間 [i, j) についてはすべて「1」となって、マス j については 0 となるような場合についての、区間 [0, i) についてのハミング距離の最小値

とする。そして、集める DP で遷移を考える。とりあえず遷移を作ってみる。関数 f( i ) をマス i に対しては操作したときに発生するコストとする (何もしないときはコストが発生しないように offset をもっておく)

そうすると、以下のような感じになる。

一般の場合: j >= i に対して

• chmin(dp[ i ][ j ], dp[ i - 1 ][ j ] + f( i - 1 ))

j == i の場合に対して

• chmin(dp[ i ][ i ], dp[ i - 1 ][ i - 1 ])

区間 [i, r) に対して

• chmin(dp[ i ][ r ], min_(i <= k <= r)dp[ i - 1 ][ k ] + f( i - 1 ))

さらにもう一工夫

上の DP では、特にこの式

• chmin(dp[ i ][ j ], dp[ i - 1 ][ j ] + f( i - 1 )

この式で +f(i - 1) というのをなくしたい。そこで offset の取り方を変えることにする。ちゃんと整理して考えると

• b[ i ] == 0 のとき、変えないペナは 0、変えるペナは 1
• b[ i ] == 1 のとき、変えないペナは 1、変えるペナは 0

これを、変えるときを 0 に揃える。そうすると、offset = (0 の個数) として、

• b[ i ] == 0 のとき、変えないペナは -1、変えるペナは 0
• b[ i ] == 1 のとき、変えないペナは 1、変えるペナは 0

という風に考えることができる。最後に offset を足せばよい。改めて、関数 f をこのように定義し直すと、以下のようになる。これで in-place DP しやすい形になった。

一般の場合: j >= i に対して

• chmin(dp[ i ][ j ], dp[ i - 1 ][ j ])

j == i の場合に対して

• chmin(dp[ i ][ i ], dp[ i - 1 ][ i - 1 ] + f( i - 1 ))

区間 [i, r) に対して

• chmin(dp[ i ][ r ], min_(i <= k <= r)dp[ i - 1 ][ k ])

#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]);
    }

    void chmin(int a, const Monoid &v) {
        long long pv = get(a, a+1).first;
        if (pv <= v) return;
        update(a, v);
    }
    
    /* 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;
using pint = pair<int,int>;

int N, Q;
vector<int> b;
vector<vector<int>> rs;

long long f(int i) { return b[i] == 0 ? -1 : 1; }
long long solve() {
    long long offset = 0;
    for (int i = 0; i < N; ++i) if (b[i] == 0) ++offset;

    RMQ<long long> dp(N+2, INF);
    dp.update(0, 0);
    for (auto r : rs[0]) dp.update(r, 0);
    for (int i = 1; i <= N; ++i) {
        for (auto r : rs[i]) {
            long long mi = dp.get(i, r+1).first;
            dp.chmin(r, mi);
            dp.chmin(r, dp.get(i-1, i).first + f(i-1));
        }
        dp.chmin(i, dp.get(i-1, i).first + f(i-1));
    }
    return dp.get(N, N+1).first + offset;
}

int main() {
    cin >> N; b.resize(N);
    for (int i = 0; i < N; ++i) cin >> b[i];
    rs.assign(N+1, vector<int>());
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int l, r; cin >> l >> r; --l;
        rs[l].push_back(r);
    }
    for (int l = 0; l <= N; ++l)
        sort(rs[l].begin(), rs[l].end(), greater<int>());
    cout << solve() << endl;
}