IOI2007 Day1-3 帆 (Sails)

問題文

https://www.ioi-jp.org/ioi/2007/problem/day1/sails-prob-j.pdf
https://oj.uz/problem/view/IOI07_sails

船に

$N$ 本の柱が立っていて、

$i$ 本目の柱の高さは

$H_i$ です。
柱は

$H_i$ 個の区間に分かれていて、そのうち

$K_i$ 個を選んで、帆を張ります。
ある帆の非効率さを その帆と同じ高さで、かつ前にある帆の数とします。
帆の非効率さの総和の最小値を求めてください。

$N\le 100000$

考察

コストが

$\mathrm{\Theta }($帆の数

${}^2)$ なので、帆の数は平坦にしたほうがいい。
また、柱の順番は関係ないので、ソートしていい感じにできて、

$H$ の昇順にすると、帆の数が少ないところに貪欲に入れることになる。

よって、次ができれば良い。

空の multiset があります
以下のクエリを処理した後の multiset を答えてください

• $0$ を追加する
• 小さい方から
  $K_i$ 個選び、
  $1$ 増やす

これは要素の挿入・削除と区間和ができる平衡二分木を自作して、
cnt[i] := (multiset 内の i の個数) とすれば

$O(N\log N)$ でできる。
自作平衡二分木はやりたくないので、挿入と削除のできる __gnu_cxx::rope を頑張って使う。
区間和は累積和を持てばできる。

実装

__gnu_cxx::rope のリファレンスがないのでかなり苦戦した。
__gnu_cxx::rope< pair<T, U> > を使うと CE になるという罠がある。

$O(N(\log N{)}^2)$　637ms / 1000ms
https://oj.uz/submission/212762

ところで

__gnu_cxx::rope はGCC拡張だし、平衡二分木の自作はシラバス外なので、もっとうまい方法があることになる。
しかし、自作平衡二分木を使わないと配列をずらすのはむずかしい。

空の multiset があります
以下のクエリを処理した後の multiset を答えてください

• $0$ を追加する
• 小さい方から
  $K_i$ 個選び、
  $1$ 増やす

multiset 内は常に降順に並んでいると考えて、小さいほうから

$K_i$ 個を選んで

$1$ を足すと、値の境界はほとんど変わらないことがわかる。
そこで、 std::multiset<int> に値の境界を持たせて、

$i$ 番目に大きい境界から

$i+1$ 番目に大きい境界までが

$i$ である とすると、

$K_i$ 個を選んで

$1$ を足すクエリが、境界を 1 つ追加・1 つずらす操作になって、

$O(N\log N)$ で解ける。

実装

63ms / 1000ms
https://oj.uz/submission/213054

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define all(a) begin(a), end(a)
#define each(i,a) for(auto&& i : a)
 
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<pii> a(n);
    each(i, a) cin >> i.first >> i.second;
    sort(all(a));
    multiset<int> X; // i 番目に大さい境界から i + 1 番目に大さい境界までが i である
    X.insert(0);
    each(i, a){
        auto [h, k] = i;
        X.insert(h);
        auto p = X.upper_bound(h - k), q = prev(p);
        int next = *q + *p - (h - k);
        if(q != X.begin()) X.erase(q);
        X.insert(next);
        X.erase(p);
    }
    ll ans = 0, cnt = 0;
    for(auto p = X.end(); p-- != X.begin(); cnt++) ans += cnt * *p;
    cout << ans << '\n';
}

感想

これって slope trick ってやつですか　なるほど