Codeforces Round #305 (Div.1) B. Mike and Feet

問題文

解法1

値の大きい方から追加していって，区間やその幅をset, multiset で管理して頑張るだけ．
実装が悲しい感じになる．

ソースコード1

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
constexpr int inf = 1e9;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), as;
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        as.push_back(a[i]);
    }
    sort(begin(as), end(as));
    as.erase(unique(begin(as), end(as)), end(as));
    for(auto& h : a) {
        h = lower_bound(begin(as), end(as), h) - begin(as);
    }

    vector<vector<int>> pos(as.size());
    for(int i = 0; i < n; ++i) {
        pos[a[i]].push_back(i);
    }

    set<pii> segs;
    multiset<int> lens; // segment length
    vector<int> ans(n, -1);

    auto erase_seg = [&](pii s) {
        segs.erase(s);
        lens.erase(lens.lower_bound(s.second - s.first + 1));
    };
    auto insert_seg = [&] (pii s) {
        segs.insert(s);
        lens.insert(s.second - s.first + 1);
    };
    for(int i = as.size() - 1; i >= 0; --i) {
        for(auto& p : pos[i]) {
            if(segs.empty()) {
                insert_seg(make_pair(p, p));
                continue;
            }
            auto it = segs.lower_bound(make_pair(p, -1));
            if(end(segs) != it && begin(segs) != it) {
                auto pre = prev(it);
                if(it->first == p + 1 && pre->second + 1 == p) { // combine two seg
                    auto s1 = *pre, s2 = *it;
                    erase_seg(s1);
                    erase_seg(s2);
                    insert_seg(make_pair(s1.first, s2.second));
                } else if(it->first == p + 1) {
                    auto s = *it;
                    erase_seg(s);
                    insert_seg(make_pair(s.first - 1, s.second));
                } else if(pre->second + 1 == p) {
                    auto s = *pre;
                    erase_seg(s);
                    insert_seg(make_pair(s.first, s.second + 1));
                } else {
                    insert_seg(make_pair(p, p));
                }
            } else if(end(segs) != it) {
                auto s = *it;
                if(s.first == p + 1) {
                    erase_seg(s);
                    insert_seg(make_pair(s.first - 1, s.second));
                } else {
                    insert_seg(make_pair(p, p));
                }
            } else {
                it = prev(it);
                auto s = *it;
                if(s.second + 1 == p) {
                    erase_seg(s);
                    insert_seg(make_pair(s.first, s.second + 1));
                } else {
                    insert_seg(make_pair(p, p));
                }
            }
        }
        auto maxi_len = *prev(end(lens));
        ans[maxi_len - 1] = max(ans[maxi_len - 1], as[i]);
    }

    for(int i = n - 1; i >= 1; --i) {
        ans[i - 1] = max(ans[i - 1], ans[i]);
    }

    for(int i = 0; i < n; ++i) {
        printf("%d\n", ans[i]);
    }
}

解法2

各要素の値が効力を持つ幅が分かればいいわけで，これは stack で実装可能．
つまり，ある要素 a[i] が左にどれだけ効力を持つか，言い換えれば j < i で初めて a[j] < a[i] となる j はなにかが分かればよい．右も同様にやる．
答えを ans[i] とすると明らかに ans は単調減少なのでいい感じにマージできて，計算量は O(n)．

ソースコード2

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> st;
    vector<int> llen(n), rlen(n);
    for(int i = 0; i < n; ++i) {
        while(!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        llen[i] = (st.empty() ? i + 1 : i - st.back());
        st.push_back(i);
    }
    st.clear();
    for(int i = n - 1; i >= 0; --i) {
        while(!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        rlen[i] = (st.empty() ? n - i : st.back() - i);
        st.push_back(i);
    }

    vector<int> ans(n);
    for(int i = 0; i < n; ++i) {
        ans[llen[i] + rlen[i] - 2] = max(ans[llen[i] + rlen[i] - 2], a[i]);
    }
    for(int i = n - 1; i >= 1; --i) {
        ans[i - 1] = max(ans[i - 1], ans[i]);
    }

    for(int i = 0; i < n; ++i) {
        cout << ans[i] << " \n"[i + 1 == n];
    }
}

感想

実装担当が解法1みたいなコードを書いているようじゃだめなんだよなあ．
まあ適当にかけるという利点はあるかもしれない．