AOJ 2430 - Longest Increasing Sequence

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2430

解法

やり方は2通りあるんですが、片方はちょっとメモリが厳しかった（通ったけど）。

メモリが厳しいほう

　dp[i][j] := i 個目までみて最大長さが j であるときの右端の min
と定義。各 i に対して、最初に dp[i] の j が大きい方から累積 min を取る。
遷移は、j = i + 1, ... に対して、区間 [i, j] の和 S を持ちながら dp[i] において S 以上となる最大位置 L を二分探索で求めて dp[j][L] を更新する。
復元テーブルは適当に (idx, len) を持てば可能。

計算量は O(N^2logN) だが、dp テーブルの要素が long long であること、N <= 4000 であること、復元テーブルも必要なのも合わせて、適当に書くと MLE する。
DP テーブルで明らかに不要なサイズなどを持っておかないようにすると、ギリギリ (150MB ぐらい？）で通った。

ましにする

　dp[i][j] := i 個目までみて右端の値が j であるときの最大長さ
と定義。j が sum なので map で管理する。
ぶっちゃけさっきのを key と value を入れ替えて map にしただけ。
map のデータは、任意の (ki, vi), (kj, vj) in map に対して ki < kj => vi < vj を満たすように持っておく。
すると、さっきの遷移で、今の和 S に対してどれを使えばいいか二分探索できる。
これも O(N^2logN) で動作し、かなり省メモリになる。

ソースコード

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

using ll = long long;
using pii = pair<int, int>;

constexpr ll inf = 1e18;

int main() {
    int n; cin >> n;
    vector<ll> a(n);
    for(auto& aa : a) cin >> aa;

    vector<map<ll, int>> dp(n + 1);
    vector<map<ll, pair<ll, int>>> pre(n + 1);
    dp[0][-inf] = 0;
    for(int i = 0; i < n; ++i) {
        ll sum = 0;
        for(int j = i + 1; j <= n; ++j) {
            sum += a[j - 1];
            auto it = dp[i].lower_bound(sum);
            if(it == dp[i].begin()) continue;
            it = prev(it);
            { // update
                auto nit = dp[j].lower_bound(sum);
                while(nit != end(dp[j]) && nit->second <= it->second + 1) {
                    pre[j].erase(nit->first);
                    nit = dp[j].erase(nit);
                }
                if(nit == begin(dp[j]) || prev(nit)->second < it->second + 1) {
                    dp[j][sum] = it->second + 1;
                    pre[j][sum] = {it->first, i};
                }
            }
        }
    }

    int max_len = 0;
    ll cur_sum = 0, cur_idx = n;
    for(auto const& p : dp[n]) {
        if(max_len < p.second) {
            max_len = p.second;
            cur_sum = p.first;
        }
    }
    vector<int> ans;
    while(pre[cur_idx].count(cur_sum)) {
        const auto p = pre[cur_idx][cur_sum];
        ans.push_back(p.second);
        cur_sum = p.first, cur_idx = p.second;
    }
    ans.pop_back();
    reverse(begin(ans), end(ans));

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

感想

復元パートもっとうまくできる気がするんだけど、楽なのはこれだと思うんだよなあ。
というかなんでこんなに MLE きついんだろう。もっと賢く解けってこと？