AtCoder Grand Contest 005 B - Minimum Sum

問題

　長さ $N$ の順列が与えられるので $\sum_{l = 1}^{N} \sum_{r = 1}^{N} \min(a_l, a_{l + 1}, ..., a_{r})$ を求めよ。

思考過程

　まず制約を見て、 $N$ が大きいので $O(N)$ とか $O(N\log{N})$ でないとダメだなというのを把握。

　順列というのが気になるところで、要素の値をベースに考えるということが頭をよぎる。ある要素が最終的に何回足されるかを考えると左右に自分より小さい値がいくつ並ぶかがわかればだいたい計算できそうだと思う。しかしここからが長かった。

　1から順番に考えていくことで上手くやれそうだと考えたけど、次の2が1の右側に来るのか左側に来るのかで全然話が違うため上手く左右の境界だけ持つというわけにはいかない。さらに3が1と2の間だったり両方の右だったりとかパターンがどんどん増えてしまう。

　一瞬はセグメント木を使って解けたりするのかなとか考えたりしつつ、しかしわからないし400点問題でそれはないだろうというようなメタ読みを挟みながら考えていくと、毎回 $O(log{N})$ は時間かけて大丈夫なのだから、2分木を使ってなんとかならないかなと考える。しばらく考えて原理的には2分木を上手く使えばできるはずだとわかったけど、自前で実装しなきゃいけないのかなーと悩む。実装したくないよーとstd::setのリファレンスを見たらlower_boundというメソッドがあるのを発見して勝ち。1時間くらいかかった。

　他の人の実装を見ていると左右の幅を持っておいて1から徐々に広げていったりunion-findを使ったり分割統治的にやったりなど様々な解法があるっぽい。うーん、これを考察部分で思いつきたかったなぁ。

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

int main() {
    ll N;
    cin >> N;
    vector<ll> a(N), pos(N + 2, -1);
    for (ll i = 0; i < N; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }

    ll ans = 0;

    set<ll> st;
    st.insert(-1);
    st.insert(N);
    for (ll i = 1; i <= N; i++) {
        auto itr = st.lower_bound(pos[i]);
        ll r_value = *itr;
        itr--;
        ll l_value = *itr;

        ans += i * (pos[i] - l_value) * (r_value - pos[i]);

        st.insert(pos[i]);
    }

    cout << ans << endl;
}

水たまり

AtCoder Grand Contest 005 B - Minimum Sum

問題

解答

思考過程