SRM 762 Div1 Easy LexicographicPartition

問題概要

community.topcoder.com

長さAの数列nを連続部分列に分解する。
ただし、連続部分列に含まれる要素の合計は正にならなくては行けない。
この時、Aの連続部分列を前から長さを見た数列をBとする。
辞書順最小のBを求めよ。

解法

前から貪欲するだけ。
A[i]以降を考えるとA[i] +... + A[j] > 0 かつ A[j] + ... + A[n-1] > 0となる最初のjを探索すれば良い。
これは求めるものが辞書順最小なのでj-iを最小にすることを考えると明らか。

class LexicographicPartition{
    public:
        vector <int> positiveSum(int n, vector <int> Aprefix, int seed, int Arange){
            vector<int> A(Aprefix);

            ll state = seed;
            for(int i=Aprefix.size();i<n;i++){
                state = (1103515245 * state + 12345);
                A.push_back(state % (2 * Arange + 1) - Arange);
                state = state % (1LL << 31);
            }

            vector<ll> sum(n+1,0); // sum[i] := A[0] + ... + A[i-1]
            rep(i,n){
                sum[i+1] = sum[i] + A[i];
            }

            cout << A << endl;
            cout << sum << endl;

            vector<int> ans;
            int i;
            for(i=0;i<n;){
                bool ok = false;
                for(int j=i+1;j<=n;j++){
                    // check [i,j)
                    if(sum[j] - sum[i] > 0 && (sum[n] - sum[j] > 0 || j == n)){
                        ans.push_back(j-i);
                        i = j;
                        ok = true;
                        break;
                    }
                }
                if(!ok){
                    cout << i << endl;
                    return {-1};
                }
            }

            vector<int> res;
            res.push_back(ans.size());
            if(ans.size() > 200) ans.resize(200);
            for(auto v : ans) res.push_back(v);
            return res;
        }
};
<||

* 感想
これを落としたのは反省。
落ちた理由は実装でDFSした結果計算量がO(N^2)になっていた。