Google Code Jam 2019 Round1B : Fair Fight

問題. Fair Fight

非負整数 $K$ と2つの非負整数列 $(c_0, c_1, \ldots, c_{N - 1}), \, (d_0, d_1, \ldots, d_{N - 1})$ が与えられる．組 $(l, r) \, (0 \le l \le r \le N - 1)$ で $\left| \max(c_l, c_{l + 1}, \ldots, c_{r}) - \max(d_{l}, d_{l + 1}, \ldots, d_{r}) \right| \le K$ を満たすものがいくつあるかを求めよ．

制約： $0 \le K, N \le 10^5$ ，　 $0 \le c_i, d_i \le 10^5$

解法．二分探索＋ RMQ

解法が思いつかなかったので解説を参考にした．

任意の $i \,(0 \le i < N)$ に対して $c_i$ が最大値として選ばれて，かつ，条件を満たす区間の数を $f(i)$ とする．ただし，最大値が複数ある場合は添字が最も小さいものが選ばれるものとする．関数 $f$ が計算できると答えは $\sum_{i = 0}^{N - 1} f(i)$ となるので $f$ を求めることを考える．

$f(i)$ の値に寄与する区間を $[L, R]$ とすると， $[L, R]$ は次の条件を満たす．
　条件1. $\max(c_{L}, c_{L + 1}, \ldots, c_{i - 1}) < c_{i}$
　条件2. $\max(c_{i + 1}, c_{i + 2}, \ldots, c_{R}) \le c_{i}$
　条件3. $\max(d_L, d_{L + 1}, \cdots, d_{R}) \le c_{i} + K$
　条件4. $\max(d_L, d_{L + 1}, \cdots, d_{R}) \ge c_{i} - K$
条件1, 2は $c_i$ が最大値として選ばれているという条件で，条件2, 3は問題文にある制約の絶対値を書き直したものである．観察として，区間 $[L, R]$ の部分区間 $[L', R'] \, (L \le L' \le R' \le R)$ も $f(i)$ の値に寄与する区間である．したがって， $[L, R]$ が上の条件を満たす極大な区間のとき，
　 $f(i) = (i - L + 1) \times (R - i + 1)$
となる．

$\left|c_i - d_i \right| > K$ の場合は $f(i) = 0$ となるので $\left| c_i - d_i \right| \le K$ と仮定する．
まず初めに条件1を満たす区間の左端で最も左にあるものを求める．上の観察より，左端を $l$ としたときに条件 $\max(c_{l}, c_{l + 1}, \ldots, c_{i - 1}) < c_{i}$ を満たすかどうかという性質は単調になるので $l$ に関する二分探索を行う．各 $l$ に対する最大値関数の計算は $c$ のRange Maximum Query に答える関数 $RMQ_c (l, r) = \min(c_l, c_{l + 1}, \ldots, c_{r - 1})$ を使用する． $RMQ_c$ を区間木で実装すると，前処理に $O(N \log N)$ 時間，各クエリに $O(\log N)$ 時間かかるので，極大な左端を求めるのに全体で $O(\log^2 N)$ 時間かかる．しかし， $c$ の値は変更しないので Sparse Table で実装すると，前処理に $O(N \log N)$ 時間，各クエリに $O(1)$ 時間で全体で $O(\log N)$ 時間で計算可能である（実装では区間木のみを選択． Sparse Tableの実装を追加）．同様に条件2を満たす極大な区間の右端も $O(\log^2 N)$ 時間で求まる．

次に，条件3, 4について考える．上で求めた条件1, 2を満たす極大な区間を $[L, R]$ とする．条件3, 4を同時に満たす区間の数を数えるのは大変なので， $[L, R]$ の部分区間で次の条件を満たす極大な区間をそれぞれ求める（条件3と3'は同じ）．
　条件3'. $\max(d_l, d_{l + 1}, \cdots, d_{r}) \le c_{i} + K$
　条件4'. $\max(d_l, d_{l + 1}, \cdots, d_{r}) < c_{i} - K$
これは，上の方法と同様に $d$ の Range Maximum Query に答える関数 $RMQ_d$ を求めて $l$ と $r$ をそれぞれ別に二分探索で求めると同じ計算時間で求まる．このとき，条件3'と条件4'を満たす極大な区間をそれぞれ $[l_3, r_3], \, [l_4, r_4]$ とすると，
　 $f(i) = (i - l_3 + 1) \times (r_3 - i + 1) - (i - l_4 + 1) \times (r_4 - i + 1)$
となる．

計算時間： $O(N \log^2 N)$

区間木：ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

/*******************************************************************************************/
template<typename Monoid>
struct SegmentTree {
    using T = typename Monoid::value_type;

    std::size_t sz;
    std::vector<T> d;

    explicit SegmentTree(std::size_t n = 0) {
        for (sz = 1; sz < n; ) sz <<= 1;
        d.resize(2 * sz, Monoid::unit());
    }

    template<typename InputIterator>
    SegmentTree(InputIterator first, InputIterator last) {
        resize(first, last);
    }

    template<typename InputIterator>
    void resize(InputIterator first, InputIterator last) {
        std::size_t n = std::distance(first, last);
        for (sz = 1; sz < n; ) sz <<= 1;
        d.resize(2 * sz, Monoid::unit());
        std::copy(first, last, d.begin() + sz);
        initialize();
    }

    void fill(const T &value) {
        std::fill(d.begin() + sz, d.end(), value);
        initialize();
    }

    void initialize() {
        for (int i = sz - 1; 0 < i; --i) d[i] = Monoid::op(d[i << 1], d[i << 1 | 1]);
    }

    // d[idx] = value
    void update(std::size_t idx, const T &value) {
        for (d[idx += sz] = value; idx >>= 1; )
            d[idx] = Monoid::op(d[idx << 1], d[idx << 1 | 1]);
    }

    // d[l] * d[l + 1] * ... * d[r - 1]
    T accumulate(std::size_t l, std::size_t r) const {
        T res_l = Monoid::unit(), res_r = Monoid::unit();
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res_l = Monoid::op(res_l, d[l++]);
            if (r & 1) res_r = Monoid::op(d[--r], res_r);
        }
        return Monoid::op(res_l, res_r); // for non-commutative
    }

    // d[idx]
    T operator[](std::size_t idx) const { return d[sz + idx]; }
};

template<typename T>
struct max_commutative_monoid {
    using value_type = T;
    static constexpr T unit() { return std::numeric_limits<T>::min(); }
    static T op(const T &lhs, const T &rhs) { return std::max(lhs, rhs); }
};
/*******************************************************************************************/

class Solver {
public:
    Solver(int _n) : num_case(_n) {}

    void input() {
        cin >> N >> K;
        c.resize(N); d.resize(N);
        for (auto &c_i : c) cin >> c_i;
        for (auto &d_i : d) cin >> d_i;
    }
    void solve();
    void print() { cout << "Case #" << num_case << ": " << num_pair << '\n'; }

private:
    const int num_case;
    int N, K;
    vector<int> c, d;

    ll num_pair;
    using Seg = SegmentTree<max_commutative_monoid<int>>;
    array<Seg, 2> rmq;

    void init() {
        num_pair = 0;
        rmq[0].resize(c.begin(), c.end());
        rmq[1].resize(d.begin(), d.end());
    }

    int rangeToLeftLessEqual(const int idx, const int begin, const int end, const int UB) {
        int lb = begin - 1, ub = end;
        while (1 < ub - lb) {
            int mid = (lb + ub) / 2;
            if (rmq[idx].accumulate(mid, end + 1) <= UB) ub = mid;
            else lb = mid;
        }
        return (rmq[idx].accumulate(ub, end + 1) <= UB) ? ub : end + 1;
    }

    int rangeToRightLessEqual(const int idx, const int begin, const int end, const int UB) {
        int lb = begin, ub = end + 1;
        while (1 < ub - lb) {
            int mid = (lb + ub) / 2;
            if (rmq[idx].accumulate(begin, mid + 1) <= UB) lb = mid;
            else ub = mid;
        }
        return (rmq[idx].accumulate(begin, lb + 1) <= UB) ? lb : begin - 1;
    }
};

void Solver::solve() {
    init();

    for (int i = 0; i < N; ++i) {
        if (c[i] + K < d[i]) continue;

        int L = i, R = i;
        if (i != 0) L = rangeToLeftLessEqual(0, 0, i - 1, c[i] - 1);
        if (i != N - 1) R = rangeToRightLessEqual(0, i + 1, N - 1, c[i]);

        ll l = rangeToLeftLessEqual(1, L, i, c[i] + K);
        ll r = rangeToRightLessEqual(1, i, R, c[i] + K);
        num_pair += (i - l + 1) * (r - i + 1);

        if (d[i] < c[i] - K) {
            l = rangeToLeftLessEqual(1, L, i, c[i] - K - 1);
            r = rangeToRightLessEqual(1, i, R, c[i] - K - 1);
            num_pair -= (i - l + 1) * (r - i + 1);
        }
    }
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int T; cin >> T;

    for (int i_case = 1; i_case <= T; ++i_case) {
        Solver s(i_case);
        s.input();
        s.solve();
        s.print();
    }

    return 0;
}

計算時間： $O(N \log N)$

Sparse Table：ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

/*******************************************************************************************/
template<typename IdempotentMonoid>
struct SparseTable {
    using T = typename IdempotentMonoid::value_type;

    std::size_t sz = 0;
    std::vector<std::vector<T>> d; // d[p][i] = op(a[i], a[i + 1], ..., a[i + 2^p - 1])
    std::vector<size_t> log2; // log2[i] = floor(log_2(i))


    SparseTable() {}

    explicit SparseTable(std::size_t n) : sz(n) {
        initializeLog2();
        d.resize(log2[sz] + 1, std::vector<T>(sz, IdempotentMonoid::unit()));
        updateTable();
    }

    template<typename InputIterator>
    SparseTable(InputIterator first, InputIterator last) { resize(first, last); }

    void resize(const size_t n) {
        sz = n;
        initializeLog2();
        d.resize(log2[sz] + 1, std::vector<T>(sz, IdempotentMonoid::unit()));
        updateTable();
    }

    template<typename InputIterator>
    void resize(InputIterator first, InputIterator last) {
        sz = std::distance(first, last);
        initializeLog2();

        d.resize(log2[sz] + 1, std::vector<T>(sz, IdempotentMonoid::unit()));
        std::copy(first, last, d[0].begin());

        updateTable();
    }

    void initializeLog2() {
        log2.resize(sz + 1); // log2[0] = 1
        for (size_t i = 2; i <= sz; ++i) log2[i] = log2[i >> 1] + 1;
    }

    void updateTable() {
        for (size_t p = 1; p < d.size(); p++)
            for (size_t i = 0; i + (1 << p) <= sz; i++)
                d[p][i] = IdempotentMonoid::op(d[p - 1][i], d[p - 1][i + (1 << (p - 1))]);
    }

    T accumulate(std::size_t l, std::size_t r) const {
        const size_t p = log2[r - l];
        return IdempotentMonoid::op(d[p][l], d[p][r - (1 << p)]);
    }

    void update(std::size_t idx, const T &value) { d[0][idx] = value; }

    T operator[](std::size_t idx) const { return d[0][idx]; }
    T& operator[](std::size_t idx) { return d[0][idx]; }
};

template<typename T>
struct max_monoid {
    using value_type = T;
    static constexpr T unit() { return std::numeric_limits<T>::min(); }
    static T op(const T &lhs, const T &rhs) { return std::max(lhs, rhs); }
};
/*******************************************************************************************/

class Solver {
public:
    Solver(int _n) : num_case(_n) {}

    void input() {
        cin >> N >> K;
        c.resize(N); d.resize(N);
        for (auto &c_i : c) cin >> c_i;
        for (auto &d_i : d) cin >> d_i;
    }
    void solve();
    void print() { cout << "Case #" << num_case << ": " << num_pair << '\n'; }

private:
    const int num_case;
    int N, K;
    vector<int> c, d;

    ll num_pair;
    array<SparseTable<max_monoid<int>>, 2> rmq;

    void init() {
        num_pair = 0;
        rmq[0].resize(c.begin(), c.end());
        rmq[1].resize(d.begin(), d.end());
    }

    int rangeToLeftLessEqual(const int idx, const int begin, const int end, const int UB) {
        int lb = begin - 1, ub = end;
        while (1 < ub - lb) {
            int mid = (lb + ub) / 2;
            if (rmq[idx].accumulate(mid, end + 1) <= UB) ub = mid;
            else lb = mid;
        }
        return (rmq[idx].accumulate(ub, end + 1) <= UB) ? ub : end + 1;
    }

    int rangeToRightLessEqual(const int idx, const int begin, const int end, const int UB) {
        int lb = begin, ub = end + 1;
        while (1 < ub - lb) {
            int mid = (lb + ub) / 2;
            if (rmq[idx].accumulate(begin, mid + 1) <= UB) lb = mid;
            else ub = mid;
        }
        return (rmq[idx].accumulate(begin, lb + 1) <= UB) ? lb : begin - 1;
    }
};

void Solver::solve() {
    init();

    for (int i = 0; i < N; ++i) {
        if (c[i] + K < d[i]) continue;

        int L = i, R = i;
        if (i != 0) L = rangeToLeftLessEqual(0, 0, i - 1, c[i] - 1);
        if (i != N - 1) R = rangeToRightLessEqual(0, i + 1, N - 1, c[i]);

        ll l = rangeToLeftLessEqual(1, L, i, c[i] + K);
        ll r = rangeToRightLessEqual(1, i, R, c[i] + K);
        num_pair += (i - l + 1) * (r - i + 1);

        if (d[i] < c[i] - K) {
            l = rangeToLeftLessEqual(1, L, i, c[i] - K - 1);
            r = rangeToRightLessEqual(1, i, R, c[i] - K - 1);
            num_pair -= (i - l + 1) * (r - i + 1);
        }
    }
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int T; cin >> T;

    for (int i_case = 1; i_case <= T; ++i_case) {
        Solver s(i_case);
        s.input();
        s.solve();
        s.print();
    }

    return 0;
}

いろいろ細かいことが考えられないので大変だった．グローバル空間を汚したくないのでクラスで実装したけど，競プロだと実装時間も順位の要因になるので悩ましい．今後のGCJではテンプレートにして試してみる．
後で Sparse Table での実装をしてみる．構築に $O(n)$ 時間でできるのもあるらしいのでそれも（Range Minimum Query - Qiita）．RmQの表記を使いたかったけど Maximum だった・・・．

問題. Fair Fight

解法．二分探索 ＋ RMQ

解法．二分探索＋ RMQ