mayoko’s diary

プロコンとかいろいろ。

SRM 540 div1 easy: ImportantSequence

問題

TopCoder Statistics - Problem Statement

n 個の要素からなる数列 B と, n 個のオペレータ(+ か -)の列 ops が与えられる。
数列 A は正整数から構成され, A[i] `ops[i]` A[i+1] = B[i] を満たすように構成しなければならない。この条件を満たす数列 A は何通り考えられるか。

解法

A[0] さえ決めれば, 他の要素も決定します。そこで, A[0] = 1 の時の数列 A を求めておきます。
また, A[0] の値を 1 上昇させた際の A[i] の変化量(+1 か -1)もわかります。これらの情報が分かれば, 「A[i] を正の値にするためには, A[0] の値は 1 から最低いくつ上昇させないとダメで, これ以上上昇させてはダメ」という下限と上限がわかります。

上限の最小値 - 下限の最大値 + 1 が答えです。

下のコードはこれをめっちゃ愚直に書いてますが, A[0] の値を 1 上昇させた際の A[i] の変化量が +1 か -1 であることが分かっていればもっと簡単に書けます。

const ll INF = 1ll<<55;

class ImportantSequence {
public:
    int getCount(vector <int> B, string ops) {
        int n = B.size();
        bool inf = true;
        for (int i = 0; i < n; i++) inf &= ops[i] == '-';
        if (inf) return -1;
        vector<ll> A(n+1), trans(n+1);
        A[0] = 1;
        trans[0] = 1;
        for (int i = 0; i < n; i++) {
            if (ops[i] == '+') {
                A[i+1] = B[i]-A[i];
                trans[i+1] = -trans[i];
            } else {
                A[i+1] = A[i]-B[i];
                trans[i+1] = trans[i];
            }
        }
        vector<ll> mini(n+1), maxi(n+1);
        for (int i = 0; i <= n; i++) {
            if (trans[i] == 0) {
                if (A[i] <= 0) return 0;
                else mini[i] = 0, maxi[i] = INF;
            } else if (trans[i] > 0) {
                maxi[i] = INF;
                if (A[i] > 0) mini[i] = 0;
                else {
                    ll need = 1-A[i];
                    mini[i] = need/trans[i] + !!(need%trans[i]);
                }
            } else {
                mini[i] = 0;
                if (A[i] <= 0) return 0;
                else {
                    maxi[i] = (A[i]-1) / (-trans[i]);
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            maxi[0] = min(maxi[0], maxi[i]);
            mini[0] = max(mini[0], mini[i]);
        }
        if (maxi[0] < mini[0]) return 0;
        else return maxi[0]-mini[0]+1;
    }
};